Secuencia aleatoria de Fibonacci

La sucesión aleatoria de Fibonacci es un análogo estocástico de la sucesión de Fibonacci , que se define mediante la fórmula recursiva :

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

donde el signo "+" o "-" se elige aleatoriamente para cada n, con igual probabilidad 1/2. De acuerdo con el teorema de Harry Kesten y Hillel Furstenberg, las secuencias aleatorias recurrentes de este tipo crecen en una determinada progresión geométrica, pero es difícil calcular su tasa de crecimiento. En 1999, Diwakar Viswanath demostró que la tasa de crecimiento de una secuencia aleatoria de Fibonacci es 1,1319882487943…, una constante matemática que más tarde se denominó constante de Wiswanath [1] [2] [3] .

Descripción

La secuencia aleatoria de Fibonacci es una secuencia aleatoria de enteros , donde los términos subsiguientes están determinados por una fórmula recursiva aleatoria: ${\ estilo de visualización \ izquierda \ {f_ {n} \ derecha \))$ ${\ estilo de visualización f_ {1} = f_ {2} = 1}$

$f_{n}={\begin{casos}f_{n-1}+f_{n-2},&{\text{con probabilidad 1/2))\\f_{n-1}-f_ {n-2},&{\text{con probabilidad 1/2}}\end{casos}}$ .

Por lo tanto, la sucesión aleatoria de Fibonacci comienza con los números 1, 1, y cada miembro subsiguiente de la sucesión es la suma de los dos miembros anteriores o su diferencia, con una probabilidad de 1/2.

Si alterna los signos: -, +, +, -, +, +, -, +, +, ..., entonces el resultado será una secuencia:

1, 1, 0, 1, 1, 0, 1, 1, 0, …

Sin embargo, en este caso, la influencia del azar desaparece. Normalmente, los miembros de una secuencia no seguirán un patrón predecible. Ejemplo de secuencia aleatoria:

1, 1, 2, 3, 1, -2, -3, -5, -2, -3...

para una secuencia de caracteres:

+, +, +, -, -, +, -, -, …

La secuencia aleatoria de Fibonacci se puede describir usando matrices:

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

donde el signo "+" o "-" se elige aleatoriamente para cada n, con igual probabilidad 1/2. Después

${\begin{pmatrix}f_{n-1}\\f_{n}\end{pmatrix}}=M_{n}M_{n-1}...M_{3}{\begin{pmatrix }f_{1}\\f_{2}\end{matrix}}$ ,

donde es una secuencia aleatoria de matrices que toman el valor A o B con probabilidad 1/2 ${\ estilo de visualización \ izquierda \ {M_ {k} \ derecha \}}$

$A={\begin{pmatrix}0&1\\1&1\end{pmatrix)),B={\begin{pmatrix}0&1\\-1&1\end{pmatrix}}$

Véase también

Notas

↑ D. Viswanath. Secuencias aleatorias de Fibonacci y el número 1.13198824... // Matemáticas de Computación. - 1999. - vol. 69 , núm. 231 . - P. 1131-1155 .
↑ JOB Oliveira, LH De Figueiredo. Cálculo de intervalos de la constante de Viswanath // Computación confiable. - 2002. - vol. 8 , núm. 2 . — Pág. 131 .
↑ E. Makover, J. McGowan. Una prueba elemental de que las secuencias aleatorias de Fibonacci crecen exponencialmente // Journal of Number Theory. - 2006. - vol. 121 . — Pág. 40 .