{'fraction_non_alphanumeric': 0.0484364983260916, 'fraction_numerical': 0.020300591210200156, 'mean_word_length': 4.176991150442478, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Weak Disorder in Fibonacci Sequences

We study how weak disorder affects the growth of the Fibonacci series. We introduce a family of stochastic sequences that grow by the normal Fibonacci recursion with probability 1-epsilon, but follow a different recursion rule with a small probability epsilon. We focus on the weak disorder limit and obtain the Lyapunov exponent, that characterizes the typical growth of the sequence elements, using perturbation theory. The limiting distribution for the ratio of consecutive sequence elements is obtained as well. A number of variations to the basic Fibonacci recursion including shift, doubling, and copying are considered.

We study how weak disorder affects the growth of the Fibonacci series. We introduce a family of stochastic sequences that grow by the normal Fibonacci recursion with probability 1 − ǫ, but follow a different recursion rule with a small probability ǫ. We focus on the weak disorder limit and obtain the Lyapunov exponent, that characterizes the typical growth of the sequence elements, using perturbation theory. The limiting distribution for the ratio of consecutive sequence elements is obtained as well. A number of variations to the basic Fibonacci recursion including shift, doubling, and copying are considered. The Fibonacci integer sequence {1, 1, 2, 3, 5, 8, . . .} has been studied extensively in number theory, applied mathematics, physics, computer science, and biology [1,2]. Fibonacci numbers are ubiquitous in nature: they govern branching in trees, spiral patterns in shells, and the arrangement of seeds in sunflowers [3,4,5,6].
The Fibonacci sequence, defined via the recursion relation with F 0 = 0 and F 1 = 1, is deterministic. However, many patterns in nature are not perfect. For example, spiral patterns in sunflowers, where Fibonacci numbers as high as 144 are observed, may very well be disordered. An empirical study of sunflowers observes the normal sequence {1, 1, 2, 3, 5, . . .} with a frequency of 95%, but altered sequences such as {2, 3, 5, 7, . . .} and {1, 3, 4, . . .} are also observed with a small frequency [4]. Motivated by this empirical observation, we study disorder in Fibonacci sequences. Specifically, we introduce the following stochastic sequence. We assume that the normal Fibonacci rule (1) is followed most of the time, but that with a small probability, ǫ ≪ 1, an "erroneous" recursion x n+1 = x n + x n−2 , involving an index shift, is followed. The stochastic recursion rule is therefore The initial elements are always x 0 = 0, and x 1 = x 2 = 1. Let us first recall a few useful facts on the Fibonacci sequence, corresponding to the limiting case ǫ = 0. The series elements are given by 2 . The series elements grow exponentially with n, F n ∼ λ n . Substituting this form into the recursion (1), the golden ratio satisfies λ 2 = λ + 1, and this allows to express polynomials of arbitrary degree in λ as linear functions of λ. Moreover, the ratio between two successive series elements, r n = x n /x n−1 , approaches the golden ratio r n → λ, as n → ∞.
Our goal is to elucidate the typical growth of the sequence elements with β ≡ β(ǫ) the Lyapunov exponent. For example, for the random Fibonacci series x n = x n−1 ± x n−2 where addition and subtraction are chosen with equal probabilities, the Lyapunov exponent is β ≈ 0.123975 [7,8,9,10,11]. In our case, however, the recursion rules (2) represent a gentle departure from the original Fibonacci rule (1) and thus, we expect a small change in the Lyapunov exponent. We focus on the weak disorder limit, ǫ → 0, and use perturbation theory to show that the Lyapunov exponent varies linearly with the disorder strength with β 0 = ln λ.
In general, the average behavior x n can be obtained analytically. From the sequence definition (2), the average satisfies the recursion relation with x 0 = 0, and x 1 = x 2 = 1. This linear relation implies the exponential growth x n ∼ µ n with the growth factor µ being the largest root of the third order polynomial Differentiating this equation with respect to ǫ and setting ǫ = 0, we find dµ/dǫ ǫ=0 , and thus, for small ǫ we have To compare with the growth of the typical sequence (4), it is useful to write x n ∼ e γn with γ = ln µ. To first order in the disorder strength ǫ, with γ 0 = β 0 and γ 1 = 1−λ λ(λ+2) . To address the typical behavior, we introduce the ratio between two successive elements in the sequence, r n = x n /x n−1 . The random recursion rule (2) implies that this ratio satisfies the random map, When there is no disorder, ǫ = 0, the ratio approaches the golden number, r n → λ as n → ∞. Thus as the number of iterations of the normal map (9) grows indefinitely, the distribution of the ratio approaches a delta function centered at the golden ratio, P (r) → δ(r − λ).
Generally, when ǫ > 0, the distribution P (r) has a richer structure, as shown below. The Lyapunov exponent can be conveniently expressed in terms of P (r). Indeed, each sequence element is given by the product With the exponential growth (4), the Lyapunov exponent simply equals the expected value of the logarithm of the ratio, β = ln r = dr P (r) ln r.
At weak disorder, with a small probability ǫ, an error occurs. That is, the map r n+1 = 1 + 1/(r n r n−1 ) is implemented. As long as no errors occur, the ratio will essentially be equal to λ. Then, when an error occurs, the ratio reduces to 1 + λ −2 . Since the expected number of iterations before another error occurs, ǫ −1 , is very large, the ratio again quickly approaches λ. This cycle continues ad-infinitum.
To characterize this process, we should understand how an error evolves under the random map (9). Thus, we consider the following scenario: (1) Initially, the ratio equals the golden number ρ 0 = λ, (2) An error occurs at the very first step, and (3) no further errors occur. Let ρ n be the value of the ratio after n iterations. Then ρ 1 = 1 + λ −2 , and using the relation λ 2 = λ + 1 we have 1+λ . At further iterations, the ratio follows the normal map ρ n+1 = 1 + 1/ρ n and therefore, By induction, at the n th iteration, the ratio can be expressed in terms of the Fibonacci numbers This series alternates around λ: ρ 2n+1 < λ while ρ 2n > λ, but both the odd and the even sub-series quickly converge to golden ratio, ρ n → λ as n → ∞. This analysis characterizes how a single error affects the ratio. To first order in the disorder strength ǫ, the probability that the value ρ n is observed equals ǫ(1 − ǫ) n−1 , reflecting the probability that one error is made and then, no errors are made in the following n − 1 iterations. Our first result is the distribution P (r) for the ratio to have the value r in the weak disorder limit ǫ → 0. The calculation of the first order correction to the Lyapunov exponent (5) is now straightforward. Substituting the leading behavior in the weak disorder limit (13) into the general formula (11) for the Lyapunov exponent we obtain The sum is evaluated as follows Performing the summation in the first term, we verify that β 0 = ln λ. Keeping only the terms proportional to ǫ in the second sum gives the leading correction in the perturbation expansion of the Lyapunov exponent (5), To perform this summation, we substitute the expression (12), and replace the upper limit with a large but finite cutoff N , and then evaluate the N → ∞ limit as follows where in the second line we used Eq. (3). Using the equality λ 2 = λ + 1, we arrive at our second main result This correction is very close, but not identical, to that corresponding to the average behavior (8). As the difference β 1 − γ 1 ≈ −0.00599897 is negative, the typical growth is slower than the average growth. This manifests the multiscaling behavior that has been reported in other stochastic sequences [12]. Generally, there is a multiscaling spectrum ζ m that characterizes the growth of the mth moments, x m n 1/m ∼ exp(nζ m ). However, there is no obvious relation between the Lyapunov exponent β and the multiscaling spectrum ζ m , e.g., β = γ ≡ ζ 1 .
We performed Monte Carlo simulations to verify these theoretical predictions. In the simulations, we followed the stochastic evolution of the variable r. This approach is advantageous for computation because the ratios are bounded, in contrast with the explosive growth in the sequence elements. The results presented here correspond to a single Monte Carlo run with 10 9 iterations.
There is a distinct but subtle difference between the typical and the average growth as characterized by β and γ, respectively (Fig. 1). The two coincide in the limiting cases ǫ = 0 and ǫ = 1 [13], and the discrepancy is maximal, a mere 0.2%, at the midpoint ǫ = 1/2.
The numerical simulations show unambiguously that as the number of iterations grows indefinitely, the ratio distribution approaches a stationary distribution P (r). On Fig. 2, we display the cumulative distribution G(r) = r 0 dr ′ P (r ′ ). The stationary distribution has a compact support, r min < r < r max . Indeed, the definition of the map (9) implies the obvious bounds r min > 1 and r max < 2. The values r min = (1 + √ 3)/2 and r max = √ 3, consistent with the numerical simulations results, are obtained from the following relations The first relation (17a) follows from the normal Fibonacci recurrence r n+1 = 1 + 1/r n . The second relation (17b) follows from the altered recurrence r n+1 = 1+1/(r n r n−1 ) combined with max(r n r n−1 ) = 1+max(r n−1 ) = 1+r max , that follows from the normal recursion r n+1 = 1+1/r n−1 . The distribution P (r) consists of a set of delta func- tions, and therefore, the cumulative distribution G(r) has a devil's staircase structure with infinitely many gaps. Generally, there is a large gap in the interval 1/2 < r < 1 + 1/ √ 3. This gap arises since the map (9) transforms (r min , r max ) into the union of two subintervals, (r min , 3/2) and (1 + 1/r max , r max ). The bounding point 3/2 is obtained using reasoning similar to that used in the previous paragraph. Restricting the map to the above subintervals one finds that they are transformed into the union of four smaller subintervals, etc. Hence the support of the invariant distribution P (r) is a Cantor-like fractal set and the cumulative distribution therefore has a devil's staircase structure with an uncountable number of singularities (Fig. 2).
Thus far, we have addressed a specific modification of the Fibonacci recurrence, namely, the one involving the index shift x n+1 = x n + x n−2 . But there are of course several other, equally natural, modifications of the basic recursion rule. For example, one may simply copy the last element x n+1 = x n or alternatively, double it x n+1 = x n + x n . These two models are analyzed along the same lines. For simplicity, we address the latter case where the recursion relation is with the initial elements x 1 = x 2 = 1. The corresponding random map is In contrast with (9), when an error occurs, the ratio r = 2 is independent of the previous element. Thus, error events effectively reset the process anew. As a result, this stochastic process is analytically tractable.
To characterize how an error propagates, we start with ρ 1 = 2 and use the recursion ρ n+1 = 1 + 1/ρ n to obtain the first few terms ρ 2 = 3/2, ρ 3 = 5/3, and ρ 4 = 8/5. In general, The ratio attains this value, r = ρ n , when an error is followed by n − 1 normal recursion steps, and this occurs with probability ǫ(1 − ǫ) n−1 . Thus, the probability distribution of the ratio is with ρ n given by (20). In contrast with the limiting distribution (13), this result is now exact, because the history prior to the most recent error event is irrelevant.
The distribution now has a countable set of singularities located at the ratios ρ n of successive Fibonacci numbers. These singularities "bunch" near the golden ratio λ. Substituting the probability distribution (21) into the Lyapunov formula (11) yields Again, the typical growth is slower than the average growth, as for example, β(1/2) ≈ 0.571357 while γ(1/2) ≈ 0.577049 [14]. The exact expression (22) can be, in principle, expanded as a power series in the disorder strength ǫ, viz. β = n≥0 β n ǫ n with β n characterizing the effect of n errors. Of course, β 0 = ln λ. The lowest order correction, which can be obtained either from Eq. (22) or from Eq. (15), is given by One can also extract the next correction from Eq. (22); the result is β 2 = m≥0 ln 1 + (−1) m λ −2m−6 .
In summary, we introduced a class of random Fibonacci sequences where with a fixed probability the classic rule is followed, but otherwise, an alternate recursion occurs. We analyzed the weak disorder limit and obtained the limiting distribution for the ratio of consecutive sequence elements as well as the Lyapunov exponent. We found that the typical growth is slower than the average growth. We also showed that the cumulative distribution of the ratio of consecutive elements has a devil's staircase structure. An exact solution for particularly simple alterations of the recursion rule was obtained as well.
The above results raise a number of questions: Can the ratio distribution and the Lyapunov exponent be obtained analytically in general? What are the locations of the singularities underlying the distribution of the ratio? What is the probability that a given integer belongs to the random Fibonacci sequence?
We have focused on the average and the typical sequence growth, but further information is encoded in fluctuations with respect to the typical behavior. Related studies on disordered systems suggest that such fluctuations should obey Gaussian statistics [15] and our preliminary numerical simulations support this. The corresponding variance may be calculated using perturbation theory in the weak disorder limit.
We are indebted to Alan Newell for stimulating our interest in imperfect sunflowers and thank Patrick Shipman for pointing out the empirical data. We acknowledge US DOE grant W-7405-ENG-36 and NSF grant CHE-0532969 for support of this work.