content_image/429653.jpg content_image/429657.jpg content_image/429655.jpg content_image/429658.jpg content_image/429656.jpg content_image/429654.jpg content_image/429652.jpg
the only solution. 

The paper is organized as follows: In section II we briefly introduce the concept of stochastic object as de- fined within the context of AIT and how it helps to under- stand our problem. In section III we find the asymptotic solutions of the equations derived from the characteri- zation provided in section II. Section IV discusses the relevance of the obtained results. 

## II. ALGORITHMIC COMPLEXITY OF STOCHASTIC SYSTEMS 

The cornerstone of our argument is an abstract charac- terization of the sequence of observations made on a given system in terms of AIT [42–45, 47, 48] -see also [49]. The key quantity of such theory is the so-called Kolmogorov complexity , which is a conceptual precursor of statistical entropy, and an indicator of the complexity (and pre- dictability) of a dynamical system [50–52]. In a nutshell, let x be a symbolic string generated by the successive observations of the system S . Its Kolmogorov Complex- ity, K ( x ) is defined as the length l ( π $^{∗}$)-in bits- of the shortest program π ∗ executed in a universal computer in order to reproduce x . This measure has been often used in statistical physics [53–55] particularly in the context of symbolic dynamics [51]. In this context, K is known to be maximal for completely disordered systems, whereas it takes intermediate values when some asymmetry on the probabilities of appearance of symbols emerges. 

Within the framework of statistical physics, a sequence of observations performed over a given system can be in- terpreted as a sequence of independent, identically dis- tributed random variables, where the specific outcomes of the observations are obtained according to a given prob- ability distribution. In mathematical terms, such a se- quence of observations defines a stochastic object . By definition, the Kolmogorov Complexity of a stochastic object, described by a binary string x = x$_{1}$, .., x$_{m}$ of length m , satisfies [56]: 

In other words, the binary representation of a stochastic object is linearly compressible. The case where µ = 1 refers to a completely random object, and the string is called incompressible . 

We can generalize the concept for non binary strings, whose elements belong to a given set Σ = { s$_{1}$, .., s$_{n}$ } , be- ing | Σ | = n . This is the case of a dice, for example, whose set of outcomes is Σ$_{dice}$ = { 1 , 2 , 3 , 4 , 5 , 6 } . If the behavior of the system is governed by the random variable X ( n ), accordingly, the successive observations of our stochas- tic system define a sequence of independent, identically p$_{n}$ -distributed random variables X$_{1}$ ( n ) , ..., X$_{m}$ ( n ) taking values over the set Σ. The so-called noiseless Coding the- orem [47, 57, 58], establishes that the minimum length, (in bits) of the string needed to code the event s$_{i}$ , l $^{∗}$( s$_{i}$ ), 

<img src='content_image/429653.jpg'>

satisfies 

(Throughout the paper, log ≡ log$_{2}$, unless the contrary is indicated). The average minimum length will corre- spond to the minimum length of the code, which is, by definition, the Kolmogorov complexity. Thus we obtain [47, 59]: 

<img src='content_image/429657.jpg'>

being H ( X ( n )) the Shannon or statistical entropy [47, 57, 58], namely: 

The complete random case is obtained when, ∀ s$_{i}$ ∈ Σ p$_{n}$ ( s$_{i}$ ) = 1 /n leading to l $^{∗}$( s$_{i}$ ) = log n + O (1). This indicates that we need ≈ log n bits to code any element from Σ. Therefore, the length in bits of the sequence of m successive observations will be approximately m · log n. the average minimum length of the code will be lower than log n . Using our previous result (3) for the binary case, it is not difficult to see that: 

<img src='content_image/429655.jpg'>

By defining h ( n ) as the normalized entropy as: 

and from eq. (5), we observe that eq. (6) can be rewritten as h ( n ) ≈ µ ; µ ∈ (0 , 1]. 

So far we have been concerned with the algorithmic characterization of stochastic systems for which the size of the configuration space is static. However, we must differentiate the properties of the systems we want to characterize from a standard stochastic object such as the ones obtained by tossing a dice or a coin. They both gen- erate a bounded number of possible outcomes -namely, 6 and 2- with an associated probability, whereas those sys- tems exhibiting power-laws lack an a priori constraint on the potential number of available outcomes. These sys- tems are open concerning the size -or dimensionality- of the configuration space. Let X ( n ) be a random variable taking values on Σ, where | Σ | = n and with associated probability distribution p$_{n}$ , where (without any loss of generality) an ordering 

is assumed. At a given time, the system satisfies eq. (6), since it is a stochastic object with a given number of avail- able states. However, we assume that the system changes 

<img src='content_image/429658.jpg'>

<img src='content_image/429656.jpg'>

<img src='content_image/429654.jpg'>

<img src='content_image/429652.jpg'>

