Almost-sure growth rate of generalized random Fibonacci sequences
Annales de l'I.H.P. Probabilités et statistiques, Volume 46 (2010) no. 1, p. 135-158

We study the generalized random Fibonacci sequences defined by their first non-negative terms and for n≥1, Fn+2=λFn+1±Fn (linear case) and ̃Fn+2=|λ̃Fn+1±̃Fn| (non-linear case), where each ± sign is independent and either + with probability p or - with probability 1-p (0<p≤1). Our main result is that, when λ is of the form λk=2cos(π/k) for some integer k≥3, the exponential growth of Fn for 0<p≤1, and of ̃Fn for 1/k<p≤1, is almost surely positive and given by 0∞log x dνk, ρ(x), where ρ is an explicit function of p depending on the case we consider, taking values in [0, 1], and νk, ρ is an explicit probability distribution on ℝ+ defined inductively on generalized Stern-Brocot intervals. We also provide an integral formula for 0<p≤1 in the easier case λ≥2. Finally, we study the variations of the exponent as a function of p.

On considère les suites de Fibonacci aléatoires généralisées, définies par leurs deux premiers termes (positifs ou nuls) et, pour n≥1, Fn+2=λFn+1±Fn (cas linéaire) et ̃Fn+2=|λ̃Fn+1±̃Fn| (cas non-linéaire). Chaque signe ± est choisi indépendemment, + avec probabilité p ou - avec probabilité 1-p (0<p≤1). Nous montrons que, lorsque λ est de la forme λk=2cos(π/k) pour un entier k≥3, la croissance exponentielle de Fn pour 0<p≤1, et celle de ̃Fn pour 1/k<p≤1, est presque sûrement strictement positive et est donnée par 0∞log x dνk, ρ(x), où ρ est une fonction explicite de p dépendant du cas considéré, à valeurs dans [0, 1], et νk, ρ est une mesure de probabilité explicite sur ℝ+ définie inductivement sur les intervalles de Stern-Brocot généralisés. Nous donnons aussi une formule intégrale pour 0<p≤1 dans le cas, plus facile, où λ≥2. Enfin, nous étudions les variations de l'exposant en fonction de p.

DOI : https://doi.org/10.1214/09-AIHP312
Classification:  37H15,  60J05,  11J70
Keywords: random Fibonacci sequence, Rosen continued fraction, upper Lyapunov exponent, Stern-Brocot intervals, Hecke group
@article{AIHPB_2010__46_1_135_0,
     author = {Janvresse, \'Elise and Rittaud, Beno\^\i t and de la Rue, Thierry},
     title = {Almost-sure growth rate of generalized random Fibonacci sequences},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     publisher = {Gauthier-Villars},
     volume = {46},
     number = {1},
     year = {2010},
     pages = {135-158},
     doi = {10.1214/09-AIHP312},
     zbl = {1201.37091},
     mrnumber = {2641774},
     language = {en},
     url = {http://www.numdam.org/item/AIHPB_2010__46_1_135_0}
}
Janvresse, Élise; Rittaud, Benoît; de la Rue, Thierry. Almost-sure growth rate of generalized random Fibonacci sequences. Annales de l'I.H.P. Probabilités et statistiques, Volume 46 (2010) no. 1, pp. 135-158. doi : 10.1214/09-AIHP312. http://www.numdam.org/item/AIHPB_2010__46_1_135_0/

[1] A. Denjoy. Sur une fonction réelle de Minkowski. J. Math. Pures Appl. 17 (1938) 105-151. | JFM 64.0188.02

[2] M. Embree and L. N. Trefethen. Growth and decay of random Fibonacci sequences. R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 455 (1999) 2471-2485. | MR 1807827 | Zbl 0941.37038

[3] H. Furstenberg. Noncommuting random products. Trans. Amer. Math. Soc. 108 (1963) 377-428. | MR 163345 | Zbl 0203.19102

[4] Y. Guivarc'H and A. Raugi. Frontière de Furstenberg, propriétés de contraction et théorèmes de convergence. Z. Wahrsch. Verw. Gebiete 69 (1985) 187-242. | MR 779457 | Zbl 0558.60009

[5] Y. Guivarc'H and É. Le Page. Simplicité de spectres de Lyapounov et propriété d'isolation spectrale pour une famille d'opérateurs de transfert sur l'espace projectif. In Random Walks and Geometry 181-259. Walter de Gruyter, Berlin, 2004. | Zbl 1069.60005

[6] É. Janvresse, B. Rittaud and T. De La Rue. Growth rate for the expected value of a generalized random Fibonacci sequence. J. Phys. A: Math. Theory 42 (2009). | MR 2525481 | Zbl 1206.11019

[7] É. Janvresse, B. Rittaud and T. De La Rue. How do random Fibonacci sequences grow? Probab. Theory Related Fields 142 (2008) 619-648. | MR 2438703 | Zbl 1146.37035

[8] S. P. Meyn and R. L. Tweedie. Markov Chains and Stochastic Stability. Communications and Control Engineering Series. Springer, London, 1993. | MR 1287609 | Zbl 0925.60001

[9] Y. Peres. Analytic dependence of Lyapunov exponents on transition probabilities. In Lyapunov Exponents (Oberwolfach, 1990) 64-80. Lecture Notes in Math. 1486. Springer, Berlin, 1991. | MR 1178947 | Zbl 0762.60005

[10] B. Rittaud. On the average growth of random Fibonacci sequences. J. Int. Seq. 10 (2007) 1-32 (electronic). | MR 2276788 | Zbl 1127.11013

[11] D. Rosen. A class of continued fractions associated with certain properly discontinuous groups. Duke Math. J. 21 (1954) 549-563. | MR 65632 | Zbl 0056.30703

[12] C. Sire and P. L. Krapivsky. Random fibonacci sequences. J. Phys. A 34 (2001) 9065-9083. | MR 1876126 | Zbl 0996.60111

[13] D. Viswanath. Random Fibonacci sequences and the number 1.13198824… Math. Comp. 69 (2000) 1131-1155. | MR 1654010 | Zbl 0983.11007