Secuencia aleatoria de Fibonacci

Secuencia matemática aleatoria basada en la secuencia de Fibonacci

En matemáticas , la secuencia aleatoria de Fibonacci es un análogo estocástico de la secuencia de Fibonacci definida por la relación de recurrencia , donde los signos + o − se eligen al azar con igual probabilidad , independientemente para diferentes . Por un teorema de Harry Kesten y Hillel Furstenberg , las secuencias aleatorias recurrentes de este tipo crecen a una cierta tasa exponencial , pero es difícil calcular la tasa explícitamente. En 1999, Divakar Viswanath demostró que la tasa de crecimiento de la secuencia aleatoria de Fibonacci es igual a 1,1319882487943... (secuencia A078416 en la OEIS ), una constante matemática que más tarde se denominó constante de Viswanath. ^{[1] [2] [3]} ${\displaystyle f_{n}=f_{n-1}\pm f_{n-2}}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle n}$

Descripción

Una secuencia aleatoria de Fibonacci es una secuencia aleatoria de números enteros dada por los números para los números naturales , donde y los términos subsiguientes se eligen aleatoriamente de acuerdo con la relación de recurrencia aleatoria Una instancia de la secuencia aleatoria de Fibonacci comienza con 1,1 y el valor de cada término subsiguiente se determina mediante un lanzamiento de moneda justo : dados dos elementos consecutivos de la secuencia, el siguiente elemento es su suma o su diferencia con probabilidad 1/2, independientemente de todas las elecciones realizadas anteriormente. Si en la secuencia aleatoria de Fibonacci se elige el signo más en cada paso, la instancia correspondiente es la secuencia de Fibonacci ( F _n ), Si los signos se alternan en el patrón menos-más-más-menos-más-más-..., el resultado es la secuencia ${\displaystyle f_{n}}$ ${\displaystyle n}$ ${\displaystyle f_{1}=f_{2}=1}$ $${\displaystyle f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{ with probability }}{\tfrac {1}{2}};\\f_{n-1}-f_{n-2},&{\text{ with probability }}{\tfrac {1}{2}}.\end{cases}}}$$ $${\displaystyle 1,1,2,3,5,8,13,21,34,55,\ldots .}$$ $${\displaystyle 1,1,0,1,1,0,1,1,0,1,\ldots .}$$

Sin embargo, estos patrones ocurren con una probabilidad que se desvanece en un experimento aleatorio. En una serie típica, los términos no seguirán un patrón predecible: $${\displaystyle 1,1,2,3,1,-2,-3,-5,-2,-3,\ldots {\text{ for the signs }}+,+,+,-,-,+,-,-,\ldots .}$$

De manera similar al caso determinista, la secuencia aleatoria de Fibonacci puede describirse de manera provechosa mediante matrices : $${\displaystyle {f_{n-1} \choose f_{n}}={\begin{pmatrix}0&1\\\pm 1&1\end{pmatrix}}{f_{n-2} \choose f_{n-1}},}$$

donde los signos se eligen independientemente para diferentes n con probabilidades iguales para + o −. Por lo tanto, donde ( M _k ) es una secuencia de matrices aleatorias independientes distribuidas de forma idéntica que toman valores A o B con probabilidad 1/2: $${\displaystyle {f_{n-1} \choose f_{n}}=M_{n}M_{n-1}\ldots M_{3}{f_{1} \choose f_{2}},}$$ $${\displaystyle A={\begin{pmatrix}0&1\\1&1\end{pmatrix}},\quad B={\begin{pmatrix}0&1\\-1&1\end{pmatrix}}.}$$

Índice de crecimiento

Johannes Kepler descubrió que a medida que n aumenta, la relación de los términos sucesivos de la secuencia de Fibonacci ( F _n ) se acerca a la proporción áurea , que es aproximadamente 1,61803. En 1765, Leonhard Euler publicó una fórmula explícita, conocida hoy como la fórmula de Binet , ${\displaystyle \varphi =(1+{\sqrt {5}})/2,}$ $${\displaystyle F_{n}={{\varphi ^{n}-(-1/\varphi )^{n}} \over {\sqrt {5}}}.}$$

Demuestra que los números de Fibonacci crecen a una tasa exponencial igual a la proporción áurea φ .

En 1960, Hillel Furstenberg y Harry Kesten demostraron que, para una clase general de productos matriciales aleatorios, la norma crece como λ ⁿ , donde n es el número de factores. Sus resultados se aplican a una amplia clase de procesos de generación de secuencias aleatorias que incluyen la secuencia aleatoria de Fibonacci. Como consecuencia, la raíz n de | f _n | converge a un valor constante casi con seguridad , o con probabilidad uno: $${\displaystyle {\sqrt[{n}]{|f_{n}|}}\to 1.1319882487943\dots {\text{ as }}n\to \infty .}$$

En 1999, Divakar Viswanath encontró una expresión explícita para esta constante. Utiliza la fórmula de Furstenberg para el exponente de Lyapunov de un producto matricial aleatorio y la integración sobre una determinada medida fractal en el árbol de Stern-Brocot . Además, Viswanath calculó el valor numérico anterior utilizando aritmética de punto flotante validada por un análisis del error de redondeo .

Generalización

Mark Embree y Nick Trefethen demostraron en 1999 que la secuencia $${\displaystyle f_{n}=\pm f_{n-1}\pm \beta f_{n-2}}$$

decae casi con seguridad si β es menor que un valor crítico β * ≈ 0,70258 , conocido como la constante de Embree–Trefethen, y de lo contrario crece casi con seguridad. También demostraron que la razón asintótica σ ( β ) entre términos consecutivos converge casi con seguridad para cada valor de β . El gráfico de σ ( β ) parece tener una estructura fractal , con un mínimo global cerca de β _min ≈ 0,36747 aproximadamente igual a σ ( β _min ) ≈ 0,89517 . ^[4]

Referencias

1. Viswanath, D. (1999). "Secuencias aleatorias de Fibonacci y el número 1,13198824..." Matemáticas de la computación . 69 (231): 1131–1155. doi : 10.1090/S0025-5718-99-01145-X .
2. Oliveira, JOB; De Figueiredo, LH (2002). "Cálculo de intervalos de la constante de Viswanath". Computación confiable . 8 (2): 131. doi :10.1023/A:1014702122205. S2CID  29600050.
3. Makover, E.; McGowan, J. (2006). "Una prueba elemental de que las secuencias aleatorias de Fibonacci crecen exponencialmente". Journal of Number Theory . 121 : 40–44. arXiv : math.NT/0510159 . doi :10.1016/j.jnt.2006.01.002. S2CID  119169165.
4. Embree, M. ; Trefethen, LN (1999). "Crecimiento y decaimiento de secuencias aleatorias de Fibonacci" (PDF) . Actas de la Royal Society A: Ciencias matemáticas, físicas e ingeniería . 455 (1987): 2471. Bibcode :1999RSPSA.455.2471T. doi :10.1098/rspa.1999.0412. S2CID  16404862.

Enlaces externos

• Weisstein, Eric W. "Secuencia aleatoria de Fibonacci". MathWorld .
• Secuencia OEIS A078416 (Expansión decimal de la constante de Viswanath)
• Números aleatorios de Fibonacci. Vídeo de Numberphile sobre la secuencia aleatoria de Fibonacci.