Suite de Fibonacci aléatoire

En mathématiques, et plus particulièrement en théorie des nombres, une suite de Fibonacci aléatoire est l’analogue probabiliste de la suite de Fibonacci, définie par la relation de récurrence

$f_{n}=\pm f_{n-1}\pm f_{n-2}$,

où les signes + et − sont choisis aléatoirement avec des probabilités indépendantes 1/2 pour les indices n. Par un théorème général de Harry Kesten et Hillel Furstenberg, des suites récurrentes aléatoires de ce type ont une croissance exponentielle, mais le calcul explicite du taux de croissance est difficile. En 1999, Divakar Viswanath a montré que le taux de croissance de la suite de Fibonacci aléatoire est 1,1319882487943... (suite A078416 de l'OEIS), une constante mathématique appelée ultérieurement la constante de Viswanath.

Description

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

$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 $(F_{n})$ usuelle :

$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 :

${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

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

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

Taux de croissance

Par la formule de Binet :

$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 $|f_{n}|$ converge presque sûrement vers une certaine valeur λ. Une valeur approchée de cette limite,

$\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.

Extensions

Plusieurs variantes existent, dont les versions

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

ou encore :

$f_{n}=f_{n-1}+f_{n-2}$ et $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é.

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

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

pour différentes valeurs de $\beta$.

Application

La séquence de Fibonacci intervient aussi dans la description d'une stratégie de jeu pour la roulette.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Random Fibonacci sequence » (voir la liste des auteurs).

Liens externes

• (en) Eric W. Weisstein, « Random Fibonacci Sequence », sur MathWorld
• Benoît Rittaud, « Les suites de Fibonacci aléatoires », sur Daylymotion, Universcience