Ceros de la secuencia aleatoria de Fibonacci

Question

Dejemos que $X_n$ sea la "secuencia aleatoria de Fibonacci", definida como sigue:

$X_0 = 0, X_1 = 1$ ;

$X_n = \pm X_{n-1} \pm X_{n-2}$ donde los signos se eligen lanzando una moneda al 50% de forma independiente.

Se sabe que $|X_n|$ crece casi seguramente de forma exponencial por un teorema (mucho más general) de Furstenberg y Kesten sobre productos matriciales aleatorios: la base del exponente fue determinada explícitamente por Viswanath como $1.13\ldots$

No me enorgullece decir que todo esto lo he aprendido de la Wikipedia:

http://en.wikipedia.org/wiki/Random_Fibonacci_sequence

Lo que no aprendí de Wikipedia, ni de ninguna de las referencias que recogí de ella, fue:

Pregunta ¿Qué sabemos, si es que sabemos algo, sobre la probabilidad de que $X_n = 0$ en función de $n$ ?

Answer 1

En respuesta al comentario de Mark, es posible determinar que la probabilidad de $X_n=0$ decae exponencialmente de forma directa, y esto es de hecho más fácil que los teoremas sobre el crecimiento de estas secuencias aleatorias.

Dado que sólo nos interesa comprobar si la secuencia se hace cero, la simetría implica que también podríamos reducir al caso $X_n=|X_{n-1}\pm X_{n-2}|$ . Si ves el artículo "The random Fibonacci recurrence and the visible points of the plane" de T. Kalmar-Nagy, estas secuencias están en biyección con los paseos aleatorios sobre un grafo dirigido infinito que parece un árbol trivalente con aristas paralelas añadidas en cada nivel.

La probabilidad que pides se puede traducir en la pregunta de la probabilidad de que un paseo aleatorio en nuestra gráfica vuelva al origen después de $n$ pasos. Hay mucha maquinaria disponible para estudiar los paseos aleatorios en grafos altamente simétricos (en este caso no tenemos un grafo de Cayley, pero está muy cerca). Hice la siguiente estimación sencilla: El número de paseos de longitud $3n$ partiendo del origen es $2^{3n}$ . Para que una trayectoria de este tipo vuelva al origen, exactamente un tercio de sus aristas se dirigen hacia el suroeste (me refiero a la fig. 4 de la página 4 del artículo que he enlazado). Así que el número de trayectorias de longitud $3n$ con ambos extremos en el origen es como máximo $\binom{3n}{n}\sim (27/4)^n$ . Así que, en particular, la probabilidad de que $X_{3n}=0$ está limitada por encima por $(27/32)^n$ .

Añadido: Así es como se puede obtener un límite inferior también. No es difícil ver que los paseos de longitud $3n$ en nuestro gráfico están en biyección con las secuencias $\lbrace a_1,a_2,\dots,a_{3n}\rbrace$ que satisfacen $a_i\in \lbrace 1,-\frac{1}{2}\rbrace$ y $$a_1+\cdots+a_{3n}= 0$$ $$a_1+\cdots+a_m\geq 0$$ para todos $1\le m\le 3n$ y si $a_1+\cdots+a_m=\frac{1}{2}$ entonces $a_{m+1}=-\frac{1}{2}$ . Enumerar estas secuencias con exactitud puede ser un poco complicado, pero hay un subconjunto particularmente agradable si nos limitamos a la condición más fuerte $$a_1+\cdots+a_m > 1$$ para todos $2\le m\le 3n-3$ . Entonces podemos enumerarlas como Trayectorias de Dyck en rectángulos . La fórmula de ese hilo nos da $\frac{1}{3n-3}\binom{3n-3}{n-1}$ . Así que para resumir tenemos $$\frac{1}{(3n-3)2^{3n}}\binom{3n-3}{n-1}\le P(X_{3n}=0)\le \frac{1}{2^{3n}}\binom{3n}{n}$$ y en particular $$\lim_{n\to \infty} \sqrt[n]{P(X_{3n}=0)}=\frac{27}{32}$$ que coincide con los datos experimentales de la respuesta de jc.

Answer 2

En primer lugar, es algo engañoso atribuir la afirmación relativa al crecimiento exponencial a Furstenberg y Kesten. Lo que demostraron (en 1960) es que para los productos parciales de una secuencia aleatoria estacionaria de matrices existe casi con seguridad una tasa de crecimiento exponencial. Sin embargo, no excluye la posibilidad de que esta tasa de crecimiento sea nula. Su positividad para secuencias i.i.d. fue demostrado (bajo condiciones razonables de irreductibilidad) por Furstenberg en 1963.

Ahora a su pregunta. La reducción a productos matriciales consiste en observar que $$ \left( X_{n+1} \atop X_n \right) = \left( 1 \;\pm 1 \atop1\;\;\;\;\;\ 0 \right) \left( X_n \atop X_{n-1} \right) \;, $$ de donde $$ \left( X_{n+1} \atop X_n \right) = B_n \left( 1 \atop 0 \right) \;, $$ donde $$ B_n = A_n A_{n-1} \dots A_1 $$ es el producto de matrices i.i.d. $A_i$ que son $M=\left( 1 \;1 \atop1\; 0 \right)$ o $M'=\left( 1 \;-1 \atop1\;\;\; 0 \right)$ con igual probabilidad 1/2 (como explica JSE, se puede omitir la primera $\pm$ en la relación de recurrencia). Por lo tanto, $X_n=0$ si $B_n$ es una matriz triangular superior con $\pm 1$ en la diagonal. El gráfico de Schreier del cociente de $GL(2,\mathbb Z)$ por el grupo de tales matrices triangulares es noamenable, por lo que se puede deducir el decaimiento exponencial de las probabilidades de retorno.

PS La respuesta a la pregunta de Mark es NO. La razón es que existen grupos amenables (por ejemplo, los grupos de lámparas de mayor dimensión), para los que la tasa de escape lineal del paseo aleatorio simple es estrictamente positiva (lo que es análogo a la positividad del exponente para los productos matriciales), pero sin embargo la probabilidad de volver a cero decae subexponencialmente (debido a la amenabilidad).

Answer 3

Los resultados de considerar $10^6$ pseudoaleatorio $X_n$ para $n\leq 200$ sugieren que la probabilidad de ser cero podría decaer exponencialmente:

El mejor ajuste exponencial es algo así como $e^{-1.18-0.0764n}$ . La base del crecimiento exponencial es $e^{-.0764}\approx0.926$ que es consistente con el límite superior de la respuesta de Gjergji Zaimi de $(27/32)^{1/3}\approx0.945$ .

La función de densidad de probabilidad para el número de ceros en cada secuencia también parece decaer exponencialmente (el eje y debería decir "Probabilidad de tener $z$ ceros en $\{X_i\}_{i=0}^{200}$ ", y esta trama realmente debería comenzar en $z=1$ en lugar de $z=0$ ):

El mejor ajuste exponencial es algo así como $0.618e^{-0.481z}$ .

Estos fueron producidos con el siguiente código de Mathematica (con disculpas a Página de Mathworld ):

max = 200;
max2 = 10^6;
stats = Table[m = #[[1, 1]] & /@ FoldList[Dot, IdentityMatrix[2], {{0, 1}, {1, #}} & /@ ((-1)^Table[Random[Integer], {max}])];
Flatten[Position[m, 0], 1], {max2}]; 
numstats = Tally[Table[Length[stats[[i]]], {i, max2}]];
numstats2 = Table[{numstats[[i, 1]], numstats[[i, 2]]/max2}, {i, Length[numstats]}];
ListLogPlot[numstats2, AxesLabel -> {"z", "probability of z zeros in \!\(\*SubscriptBox[\(X\), \(0\)]\) to \\!\(\*SubscriptBox[\(X\), \(200\)]\)"}]
fstats = Tally[Flatten[stats, 1]];
fstats2 = Table[{fstats[[i, 1]] - 2, fstats[[i, 2]]/max2}, {i, Length[fstats]}];
ListLogPlot[fstats2, AxesLabel -> {"n", "probability of \!\(\*SubscriptBox[\(X\), \(n\)]\) being zero"}]