Suite de Fibonacci aléatoire

Une suite de Fibonacci aléatoire ${\displaystyle (f_{n})}$, avec ${\displaystyle f_{2}=f_{1}=1}$ est déterminée par la relation de récurrence aléatoire :

${\displaystyle f_{n}=\pm f_{n-1}\pm f_{n-2}}$.

Un tirage d'une suite de Fibonacci aléatoire commence par 1,1 ; la valeur de chaque terme suivant est déterminée par un tirage au sort équitable : pour deux éléments consécutifs de la suite, l'élément suivant est leur somme ou leur différence ou l'opposé de l'une ou de l'autre, avec la même probabilité 1/4, indépendamment des choix effectués précédemment. Si, dans la génération de la suite de Fibonacci aléatoire, c'est le signe plus qui est choisi à chaque étape, le tirage donne la suite de Fibonacci ${\displaystyle (F_{n})}$ usuelle :

${\displaystyle 1,1,2,3,5,8,13,21,34,55,\ldots }$.

Comme dans le cas déterministe, une suite de Fibonacci aléatoire peut être décrite au moyen de matrices :

${\displaystyle {f_{n-1} \choose f_{n}}={\begin{pmatrix}0&1\\\pm 1&\pm 1\end{pmatrix}}{f_{n-2} \choose f_{n-1}}}$,

où les signes sont choisis indépendamment pour les différentes valeurs de n avec la même probabilité pour + et –. On obtient

${\displaystyle {f_{n-1} \choose f_{n}}=M_{n}M_{n-1}\ldots M_{3}{f_{1} \choose f_{2}}}$,

où ${\displaystyle (M_{k})}$ est une suite de matrices indépendantes et identiquement distribuées.

Par la formule de Binet :

${\displaystyle F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}}$,

on voit que le taux de croissance des nombres de Fibonacci est égal au nombre d'or φ.

En 1960, Hillel Furstenberg et Harry Kesten ont montré que pour une classe générale de produits de n matrices aléatoires, la norme matricielle croit en λⁿ pour un certain λ. Leur résultat s'applique à une vaste classe de processus de génération de séquences aléatoires qui inclut la suite aléatoire de Fibonacci. En conséquence, la racine n-ième de ${\displaystyle |f_{n}|}$ converge presque sûrement vers une certaine valeur λ. Une valeur approchée de cette limite,

${\displaystyle \lim _{n\to \infty }{|f_{n}|}^{1/n}\approx 1{,}13198824}$,

a été calculée par Divakar Viswanath en 1999. Le calcul utilise la formule de Furstenberg pour l'exposant de Liapounov d'un produit de matrices aléatoires et l'intégration d'une certaine mesure fractale sur l'arbre de Stern-Brocot. Viswanath a calculé la valeur numérique en arithmétique en virgule flottante, validée par une analyse de l'erreur d'arrondi.

Plusieurs variantes existent, dont les versions

${\displaystyle f_{n}=f_{n-1}\pm f_{n-2}}$ ou ${\displaystyle f_{n}=\pm f_{n-1}+f_{n-2}}$

ou encore :

${\displaystyle f_{n}=f_{n-1}+f_{n-2}}$ et ${\displaystyle f_{n}=|f_{n-1}-f_{n-2}|}$ ;

dans cette dernière formulation, l'une ou l'autre des formules est choisie, avec même probabilité[4].

La constante d'Embree-Trefethen est une valeur critique dans le comportement des suites aléatoires pour la relation de récurrence

${\displaystyle f_{n}=f_{n-1}\pm \beta f_{n-2}}$

pour différentes valeurs de ${\displaystyle \beta }$.

• (en) Eric W. Weisstein, « Random Fibonacci Sequence », sur MathWorld
• Benoît Rittaud, « Les suites de Fibonacci aléatoires », Aléa 2009, Université Paris-13

• Arithmétique et théorie des nombres