Resolución de la relación de recurrencia aleatoria

Question

Estoy viendo la secuencia aleatoria $x_n$ con $x_0=x_1=1$ y \begin{equation} x_{n+1}=2x_n\pm x_{n-1} \end{equation} donde elegimos el $\pm$ signo de forma independiente con la misma probabilidad. Considerando ahora las relaciones de recurrencia $x_{n+1}=2x_n+x_{n-1}$ y $x_{n+1}=2x_n-x_{n-1}$ por separado, está claro que $x_n\rightarrow\infty$ como $n\rightarrow\infty$ . Sin embargo, la secuencia $x_n^{1/n}$ parece tender a un límite cercano a 1,91 (obtenido a partir de cálculos numéricos y algo de fuerza bruta mediante una simulación de Monte Carlo del $\pm$ signo). Así, la secuencia $x_n^{1/n}$ parece convocar casi con seguridad. Me preguntaba si alguien podría demostrar que la secuencia converge de forma casi segura y/o calcular el límite.

Gracias de antemano.

Actualización:
Este comentario demuestra que $\lim_{n\rightarrow\infty} |x_n|^{1/n}$ converge casi con seguridad. Sea $y_n=\frac{x_n}{2^n}$ entonces $2^{n+1}y_{n+1}=2^{n+1}y_n\pm 2^{n-1}y_{n-1}$ . Por lo tanto,

$y_{n+1}=y_n\pm \frac{1}{4}y_{n-1}$

Embree-Trefethen demostró que $\lim_{n\rightarrow\infty} |y_n|^{1/n}$ converge casi con seguridad. Véase Embree, M.; Trefethen, L. N. (1999), "Growth and decay of random Fibonacci sequences".

Sin embargo, encontrar el límite casi seguro de forma precisa o analítica está resultando difícil por el momento.

Answer 1

Si se sustituye el 2 por el 1 en su recurrencia, se obtiene el secuencia aleatoria de Fibonacci . Viswanath ha demostrado que la secuencia aleatoria de Fibonacci tiene casi seguramente un crecimiento exponencial (y da la constante de crecimiento). Sin embargo, no he leído detenidamente la prueba, así que no puedo comentar cómo podría adaptarse al caso que te interesa.

Kesten y Furstenberg demostró hace tiempo que el límite que dices que está en torno a 1,91 al menos existe, replanteando el problema como uno sobre multiplicación de matrices aleatorias.

Answer 2

Para empezar: la secuencia puede escribirse como \begin{equation} x_{n+1} = 2 x_{n} + e_{n+1} x_{n-1} \; [1] \end{equation}

donde $e_n$ es una secuencia de variables iid Bernoully que toma los valores $(1,-1)$ con igual probabilidad.

Ahora, tomando las expectativas, y porque $e_{n+1}$ y $x_{n-1}$ son independientes, resulta que $E(x_n) = 2^{n-1}$

Por lo tanto, yo diría que, si la secuencia $x_n^{1/n}$ converge, debería converger a 2.

\== continuación ==

Veamos si podemos calcular la varianza. Multiplicando por $x_{n+1}$ y la toma de expectativas:

\begin{equation} E(x^2_{n+1})=2E(x_n x_{n+1}) + E(e_{n+1} x_{n+1} x_{n-1}) \; [2] \end{equation}

Para calcular el primer término multiplicamos [1] por $x_{n}$

\begin{equation} E(x_n x_{n+1})= 2 E(x_n^2) + E(e_{n+1} x_{n} x_{n-1}) = 2 E(x_n^2) \; [3] \end{equation}

Para calcular el segundo término multiplicamos [1] por $e_{n+1} x_{m-1}$ y recuerda que $e_{n+1}^2 =1$

\begin{equation} E(e_{n+1} x_{n+1} x_{n-1}) = 2 E(e_{n+1} x_{n-1} x_{n}) + E(e_{n+1}^2) = E(e_{n+1}^2) \; [4] \end{equation}

Por lo tanto,

\begin{equation} E(x_{n+1}^2) = 4 E(x^2_n) + E(x^2_{n-1}) \; [5] \end{equation}

\====

Actualizado: esto no lleva a donde yo esperaba ... Pensé que la secuencia normalizada linealmente (digamos, $x_n / 2^n$ ) tendría una varianza asintóticamente evanescente, pero no parece ser así.

Answer 3

He estado probando un nuevo motor de búsqueda de matemáticas y encontré una discusión similar en el mathoverflow, hay enlace a los resultados de la búsqueda (http://uniquation.com/en/solutions.aspx?query=F\_{n%2B1}%3D2F\_n%2BF\_{n-1})