Demostrando que $1$ - y $2D$ los paseos aleatorios simétricos simples vuelven al origen con probabilidad $1$

Question

¿Cómo se demuestra que un simple (pasos de longitud $1$ en direcciones paralelas a los ejes) simétrico (cada dirección posible es igualmente probable) paseo aleatorio en $1$ o $2$ vuelve al origen con probabilidad $1$ ?

Editar : tenga en cuenta que, si bien el regreso al origen está garantizado $(p = 1)$ en $1$ y $2$ dimensiones, no está garantizada en dimensiones superiores; esto significa que algo en una justificación correcta de la $1$ - o $2D$ casos no debe extenderse a $3D$ $($ o fallan cuando la probabilidad para cada dirección baja de $\frac{1}{4}$ a $\frac{1}{6})$ .

Answer 1

Véase Durrett, Probabilidad: Teoría y ejemplos (el enlace lleva a una copia en línea de la cuarta edición; enlace original desaparecido ). En la p. 164 Durrett da una prueba de que el paseo aleatorio simple es recurrente en dos dimensiones.

Primero halle la probabilidad de que un simple paseo aleatorio en un dimensión está en $0$ después de $2n$ pasos; esto es claramente $\rho_1(2n) = \binom{2n}{n}/2^{2n}$ ya que $\binom{2n}{n}$ es el número de trayectos con $n$ pasos correctos y $n$ pasos a la izquierda.

A continuación, la probabilidad de que el simple paseo aleatorio en dos dimensiones -- llame a esto $\rho_2(2n)$ -- está en $0$ después de $2n$ pasos es el cuadrado de la probabilidad anterior. Consideremos el paseo aleatorio simple que da pasos hacia el noreste, noroeste, sureste y suroeste con igual probabilidad. Las proyecciones de este paseo sobre los ejes x e y son paseos aleatorios simples independientes en una dimensión. Girando y reescalando se obtiene el SRW "habitual" en dos dimensiones (con pasos hacia el norte, este, sur y oeste) y no cambia la probabilidad de estar en $0$ .

Así que $\rho_2(2n) = \left(\binom{2n}{n}/2^{2n}\right)^2$ . Esto es asintótico a $1/(\pi n)$ y el número esperado de vueltas al origen es el $\sum_{n \geq 1} \rho_2(2n)$ por lo que el número esperado de retornos al origen es infinito. No es difícil demostrar (y de hecho es cierto, pero la prueba es poco esclarecedora, así que se la dejaré a Durrett) que en este caso la probabilidad de volver finalmente al origen es $1$ .

Answer 2

Lo intentaré para 2D y luego podemos obtener 1D como corolario [¡ejercicio!]...

Esta es la única prueba que conozco, puede que haya una prueba más intuitiva (¡y menos liosa sin tex!) por ahí, pero me gusta esta, utiliza funciones generadoras de una manera realmente ingeniosa.

Considere la probabilidad de estar en el origen después de 2n pasos (observe que no podemos volver en un número impar de pasos):

$u_0=1$

$u_{2n} = p(n,n,0,0)+ p(n-1,n-1,1,1)+...+p(n-k,n-k,k,k)+...+p(0,0,n,n)$ (cuando $n\neq0$ )

Ici $p(u,d,l,r)$ es la probabilidad de que los 2n primeros pasos sean u arriba, d abajo, l izquierda y r derecha en cualquier orden. Cada orden tiene una probabilidad $\frac{1}{4^{2n}}$ y hay $\frac{(2n)!}{u!d!l!r!}$ órdenes distintas, dando $p(n-k,n-k,k,k)=\frac{1}{4^{2n}} \frac{(2n)!}{(n-k)!(n-k)!k!k!}$

Ahora bien, puesto que $(2n)!=n! n! \binom{2n}{n}$ tenemos $p(n-k,n-k,k,k)=\frac{1}{4^{2n}} \binom{2n}{n} \binom{n}{k}^2$ dando

$u_{2n}= \frac{1}{4^{2n}} \Sigma_k \binom{2n}{n} \binom{n}{k}^2$ que, por uno de esos tontos resultados binomiales, puede contraerse a

$u_{2n}= \frac{1}{4^{2n}} \binom{2n}{n}^2$

Guardémonos eso en el bolsillo por ahora y consideremos en su lugar la probabilidad de primero volviendo después de 2n pasos $f_{2n}$ --- Esto es bastante difícil de abordar directamente, pero podemos hacernos una pequeña fórmula astuta que lo incluya. función generadora diversión y sellar el trato con algunos.

La fórmula en cuestión es: $u_{2n}= f_2 u_{2n-2}+ f_4 u_{2n-4} +....+f_{2n-2}u_{2} + f_{2n}$

Lo cual no demostraremos sino que explicaremos: para volver al origen después de 2n pasos (LHS) hay que volver primero después de 2 pasos y hacer un 'volver al origen en 2n-2 pasos a pie' (primer término RHS) o volver primero después de 4 pasos y hacer un 'volver al origen en 2n-4 pasos a pie' (2º término) o... o volver primero después de 2n-2 pasos y hacer un 'volver al origen en 2 pasos a pie o volver primero al origen después de 2n pasos.

Ahora modificaremos un poco nuestra fórmula para que tenga las propiedades de simetría adecuadas para lo que viene, lo haremos añadiendo $f_0=0$ y $u_0=1$ dar

$u_{2n}= f_0 u_{2n}+ f_2 u_{2n-2}+ f_4 u_{2n-4} +....+f_{2n-2}u_{2} + f_{2n}u_0$

Que es secretamente una afirmación sobre funciones generadoras (¡esta es la parte dulce!), mira las funciones generadoras de $u_n$ , $f_n$ :

$U(x)= \Sigma_m u_{2m} x^{2m}$ , $F(x)= \Sigma_m f_{2m} x^{2m}$

Ya vemos:

$U(x)= 1+ U(x)F(x)$

(donde el "1+" es para compensar el hecho de que $u_0$ no aparece en el producto) Reordenando a:

$F(x)= \frac{U(x)-1}{U(x)}$

Obsérvese que la probabilidad de retorno es $\Sigma f_n= F(1)$ que es 1 porque $U(1)$ diverge por algunos tediosos stirlings fórmula límites que olvido.

Edita: Hasta que Tex se conecte, esto es bastante ilegible, así que aquí Aquí tienes un enlace a unos apuntes que encontré con la misma demostración (y, afortunadamente, la misma notación). ¡Que aproveche!

Editar $^2$ : ¡Hurra, Tex está en línea! Que lo disfrutes.

Answer 3

Sea $X_n = 1$ si en el $n^{th}$ paso estamos de vuelta en origen otra cosa es $0$

$\mathbb{E}(X_n)$ es la probabilidad de retorno tras $n$ pasos = $P_n$

Sea $X = \displaystyle \sum_{n=1}^{\infty} X_n$ cuenta el número de devoluciones

$\mathbb{E}(X) = \displaystyle \sum_{n=1}^{\infty} \mathbb{E}(X_n)$

Número previsto de devoluciones = $\mathbb{E}(X) = \displaystyle \sum_{n=1}^{\infty} P_n$

Tenga en cuenta que $P_n = 0$ si $n$ es impar

Sea $\rho$ es la probabilidad de que el camino aleatorio vuelva (al menos una vez) a $0$

$\rho_k$ sea la probabilidad de que devolvamos exactamente $k$ veces hasta el origen

$\rho_0 = 1 -\rho$ y en general, $\rho_k = \rho^k (1- \rho)$

$\mathbb{E}(X) = \displaystyle \sum_{k=0}^{\infty} k \rho^k (1-\rho) = \frac{\rho}{1-\rho}$ si $\rho < 1$

Por lo tanto, de lo anterior vemos que,

Si $\rho < 1$ entonces $\mathbb{E}$ (Número de devoluciones) es finito, es decir $\displaystyle \sum_{n=1}^{\infty} p_n < \infty$

Si $\rho = 1$ entonces $\mathbb{E}$ (Número de vueltas) es infinito, es decir $\displaystyle \sum_{n=1}^{\infty} p_n = \infty$

En una dimensión tenemos $p_{2n+1} = 0$ y $p_{2n} = \frac1{2^{2n}} \binom{2n}{n}$ . Obsérvese que el coeficiente binomial medio es el mayor y por tanto $\frac1{2^{2n}} \binom{2n}{n} \geq \frac1{2n+1}$ y, por tanto, el $\displaystyle \sum_{n=1}^{\infty} p_{2n}$ diverge

O podríamos utilizar la fórmula de stirling para obtener una mejor estimación y obtener $p_{2n} \approx \frac{c}{\sqrt{n}}$ y por tanto la suma diverge

En dos dimensiones tenemos $p_{2n} = \frac1{4^{2n}} \displaystyle \sum_{k=0}^{n} \binom{2n}{k} \binom{2n-k}{k} \binom{2n-2k}{n-k} = \frac1{4^{2n}} \displaystyle \sum_{k=0}^{n} \frac{(2n)!}{k! k! (n-k)! (n-k)!}$

Tenga en cuenta que el máximo está en $k = \frac{n}{2}$ y por el Teorema Central del Límite se puede decir aproximadamente que los intervalos de longitud $\sim \sqrt{n}$ en torno a $\frac{n}{2}$ donde este es de mayor tamaño

Por lo tanto, cada $k$ contribuye $\sim \frac{\sqrt{n}}{(\sqrt{n})^4} = \frac1{n^{3/2}}$ (Por la fórmula de stirling).

Número de $k$ es del orden de $\sqrt{n}$ y por lo tanto $p_{2n} \sim \frac1{n}$ y así otra vez $p_n \rightarrow \infty$ ya que la suma armónica diverge

En general, $p_n$ es aproximadamente del tamaño $\frac{c}{n^{d/2}}$ así que $\displaystyle \sum_{n=1}^{\infty} p_n < \infty$ si $d > 2$ . Esto se debe a la convergencia y divergencia de las series p. $\displaystyle \sum \mathbb{E}(X_n) < \infty \iff \mathbb{E}(X) < \infty \iff \rho < 1 \implies$ Probabilidad(volver infinitamente a menudo) = 0

Answer 4

$P =$ probabilidad de que si estás en $1$ volverás a $0$ .

$Q =$ probabilidad de que si estás en $2$ volverás a $0$ .

Suponiendo que empiece en $0$ irá a $1$ o a $-1$ por lo que encontrar la probabilidad $P$ para $1$ es la misma que la probabilidad si vas a $-1$ .

Desde el punto $1$ hay $2$ posibilidades:

1) puede volver inmediatamente a $0$

2) puede ir a $2$ .

Así que.., $P = \frac{1}{2} +\frac{1}{2} * Q$

¿Qué es el $Q$ :

Desde el punto $2$ , tienes $2$ posibilidades:

1) Puedes ir aún más lejos.

2) Puede volver a $0$ . ¿Cuál es la probabilidad de que vuelva a 0?

Bueno, la probabilidad de que vuelvas a $1$ es $P$ porque volver a $1$ de $2$ es la misma probabilidad que volver a $0$ de $1$ . Y, tendrás que volver a $1$ antes de poder volver a $0$ .

Por lo tanto:
\begin{align} P & = \frac{1}{2} + \frac{1}{2} P^2\\ 2P & = 1+P^2\\ P^2 – 2P + 1 & = 0\\ (P – 1) (P – 1) & = 0\\ P & = 1.\end{align}

Answer 5

Haré 1D.

Los paseos 1D construyen cadenas binarias, 010101, etc.

Di seis pasos. Entonces 111111 es tan probable como 101010.

Sin embargo, ¿cuántas de las secuencias posibles tienen seis unos? 1. ¿Cuántas de las posibles secuencias tienen tres unos y tres ceros? Mucho más.

Ese número se llama multiplicidad, y crece muy rápido. En el límite, su logaritmo se convierte en la entropía de Shannon.

Las secuencias son igualmente probables, pero las combinaciones no.

En el límite las combinaciones con máxima entropía van a dominar al resto. Así que el paseo habrá dado un número igual de pasos a derecha e izquierda... casi seguro.