29 votos

¿Cuál es la probabilidad de que una caminata aleatoria en $\mathbb{Z}^2$ alcance $(1,0)$ antes que $(2,0)$?

Supongamos que tenemos un recorrido aleatorio simple de 2 dimensiones: empezamos en $(0,0)$, y en cada paso, agregamos un vector unitario aleatorio en una de las cuatro direcciones cardinales seleccionadas de forma independiente y uniforme.

Es bien sabido que con probabilidad $1$ este procedimiento llegará a golpear cada elemento de $\mathbb{Z}^2$ infinitamente veces. Por lo tanto, tiene sentido preguntar sobre la probabilidad de que dicho recorrido llegue a $(1,0)$ antes que a $(2,0)$.

Ejecutando algunas simulaciones de Monte Carlo, parece que el recorrido aterriza primero en $(1,0)$ algo así como un $70\%$ del tiempo, pero no tengo mucha confianza sobre la precisión de estas simulaciones ya que no puedo ejecutarlas todas hasta su finalización y tengo que desechar los ensayos inacabados o hacer una suposición acerca de cómo concluirán. Algunas simulaciones más precisas muestran que el recorrido llega primero a $(1,0)$ con una probabilidad de al menos $0.607$ y a $(2,0)$ con una probabilidad de al menos $0.153$.

¿Existe un valor exacto conocido para esta probabilidad, y cómo se puede calcular en general para cualquier par de puntos en la red cuadrada? También me interesa una fórmula general para la probabilidad de encontrar $n$ puntos en un orden dado.

3voto

Thibaut Demaerel Puntos 171

Aquí hay una respuesta desde un ángulo potencial-teórico. Intentaré establecerlo para el problema más general de una caminata aleatoria en $\mathbb{Z}^2$ iniciada en el origen y su probabilidad de llegar a uno de los puntos $x_1,\ldots,x_n \in \mathbb{Z}^2$ antes de visitar cualquiera de los puntos $x_{n+1},\ldots,x_m \in \mathbb{Z}^2$.

  1. La probabilidad buscada es $p(0,0)$ donde $p:\mathbb{Z}^2 \to [0,1]$ es una función armónica en $\mathbb{Z}^2\setminus \{x_1,\ldots,x_m\}$ y evalúa en $p(\{x_1,\ldots,x_n\})=\{1\}$, $p(\{x_{n+1},\ldots,x_m\})=\{0\}$.

  2. La existencia de una función $p$ que resuelve el problema de valores límite descrito anteriormente se puede inferir de la existencia de la caminata aleatoria iniciada en el origen.

  3. Con respecto a la unicidad de la solución $p$ de ese problema de valores límite (y para obtener una expresión práctica para $p$), considera la función de Green 2D $G:\mathbb{Z}^2 \to \mathbb{R}$: $$G(x):=\left(\frac{1}{2\pi}\right)^2\int_{[-\pi,\pi]^2}dk\,\frac{1-\exp(ik\cdot x)}{4-2\cos(k_1)-2\cos(k_2)},$$ (lo cual resuelve $(\Delta G)(.)= \chi_{\{(0,0)\}}(.)$, donde recordamos que el Laplaciano $\Delta$ actúa como $$(\Delta f)(x)=f(x+(1,0))+f(x+(0,1))+f(x-(1,0))+f(x-(0,1))-4f(x)\qquad).$$

  4. Luego se puede verificar que la función $h(.):=p(.)-\sum_{k=1}^m (\Delta p)(x_k) G(.-x_k)$ es armónica. Se puede ver entonces que $\sum_{k=1}^m (\Delta p)(x_k) =0$ ya que si esta suma fuera estrictamente positiva o estrictamente negativa, tendríamos que $h$ divergiría asintóticamente a $+\infty$ resp. $-\infty$ y por lo tanto $h$ violaría el principio máximo para funciones armónicas. Luego, $\sum_{k=1}^m (\Delta p)(x_k) =0$ implica que $h$ está acotado y por lo tanto el teorema de Liouville para funciones armónicas en $\mathbb{Z}^2$ implica que $h$ es una función constante. Por lo tanto, esto lleva a la conclusión de que $p$ debe ser necesariamente una combinación lineal de las funciones $\{G(.-x_k)-G(.-x_1)\}_{2\leq k \leq m}\cup \{\chi_{\mathbb{Z}^2}\}$. Los coeficientes de esta combinación lineal se pueden determinar a través del sistema de ecuaciones lineales resultante de las evaluaciones $p(\{x_1,\ldots,x_n\})=\{1\}$, $p(\{x_{n+1},\ldots,x_m\})=\{0\}.$ y por nuestro resultado de existencia del punto 2 y el resultado de unicidad recién concluido, este sistema de ecuaciones lineales tiene una solución.

  5. Para el problema específico sobre el que preguntó el OP, es claro entonces que $$p(.)=\frac{1}{2}\left(1+\frac{G(.-(1,0))-G(.-(2,0))}{G((0,0))-G((-1,0))}\right).$$ Tal vez vuelva más tarde para llevar a cabo las integrales en esta expresión.

1voto

Nick Guerrero Puntos 11

No es una respuesta, pero al intentarlo realmente obtuve una probabilidad de $0.73$. El código es Código de Mathematica

Una explicación es la siguiente:

$1)$ Comenzar en $t=0$ en el plano complejo

$2)$ Agregar uno de los siguientes aleatoriamente $(1,-1,i,-i)$ a $t$

$3)$ Verificar si $t=1$ o $t=2$ (si es así, detenerse y registrar este resultado)

$4)$ Verificar si la magnitud del número resultante es mayor que $100$

$5)$ Si no lo es, regresar al paso $2)$. Si lo es, entonces elegir al azar entre $t=1$ o $t=2$, registrar el resultado, y detenerse

Realizo esto $10,000$ veces y registro el resultado cada vez. La suposición clave que hice fue que para $|t|>100$ la probabilidad de obtener $t=1$ o $t=2$ primero era aproximadamente $50\%$ cada uno.


Actualización: Volví a ejecutar mi código con $\lambda=10^6$ y obtuve una probabilidad final de $P=0.726992$. Esto concuerda fuertemente con la respuesta conjeturada de $2-\frac{4}{\pi}$ ya que

$$\left|2-\frac{4}{\pi}-\frac{726992}{10^6}\right|<10^{-3}$$

1voto

psychotik Puntos 171

Esta es una respuesta comunitaria que expande el enfoque potencial-teórico de @Vergilius. ¡Siéntete libre de mejorarlo a tu gusto!

Núcleo de Potencial. Sea $\mathfrak{a} : \mathbb{Z}^2 \to \mathbb{R}$ el núcleo de potencial dado por

$$ \mathfrak{a}(x) = \frac{2}{4\pi^2} \int_{\mathbb{T}^2} \frac{1 - \cos(x\cdot k)}{2 - \cos(k_1) - \cos(k_2)} \, \mathrm{d}k, $$

donde $\mathbb{T} = \mathbb{R}/2\pi\mathbb{Z}$. Esto satisface la fórmula asintótica

$$ \mathfrak{a}(x) = g\log\|x\| + \mathcal{O}(1) $$

a medida que $\|x\| \to \infty$ con $g = \frac{2}{\pi}$ (ver [Stö49]). Además, es fácil verificar que esto resuelve la ecuación de Poisson

$$ \Delta \mathfrak{a} = 4 \delta_0, $$

donde $\Delta f(x) = \sum_{y \in \mathcal{N}(x)} (f(y) - f(x)) $ es el Laplaciano y $\mathcal{N}(x)$ es el conjunto de vecinos más cercanos de $x$ en $\mathbb{Z}^2$, y $\delta_0(x) = \mathbf{1}[x = 0]$ es el delta de Kronecker.

Probabilidades de Golpe. Sea $(S_n)$ el caminante aleatorio simple (SRW) en $\mathbb{Z}^2$. Además, sea $\mathbf{P}^x(\cdot)$ la ley de $(S_n)$ comenzando en $x$. Si

$$ \tau_W = \inf\{ n \geq 0 : S_n \in W \} $$

denota el primer tiempo de golpe del conjunto $W \subseteq \mathbb{Z}^2$, entonces la recurrencia de $(S_n)$ indica que $\tau_W < \infty$ ocurre casi seguramente con respecto a $\mathbf{P}^x$ para cualquier subconjunto no vacío $W$.

Ahora identifiquemos $\mathbb{R}^2$ con $\mathbb{C}$ por simplicidad notacional. Luego, con $W = \{1, 2\}$, estamos interesados en la función

$$ p(x) = \mathbf{P}^x( S_{\tau_W} = 1 ), $$

y en particular, en su valor $p(0)$ en el origen. Para esto, enumeramos las propiedades clave de $p$ a ser utilizadas:

  • Tenemos $\Delta p = 0$ en $\mathbb{Z}^2 \setminus W$. Esto se prueba fácilmente a partir de la propiedad de Markov.

  • Satisface $p(1) = 1$ y $p(2) = 0$.

  • Por simetría, tenemos $p(3-x) = 1 - p(x)$.

  • Usando la identidad anterior, podemos verificar fácilmente que se cumple $\Delta p(1) + \Delta p(2) = 0$.

Combinando Juntas. Sea $\phi : \mathbb{Z}^2 \to \mathbb{R}$ dada por

$$ \phi(x) = p(x) - c[\mathfrak{a}(x-1) - \mathfrak{a}(x-2)], $$

donde $c = \frac{1}{4}\Delta p(1) = -\frac{1}{4}\Delta p(2)$. Entonces es claro que $\Delta \phi = 0$ de forma idéntica en $\mathbb{Z}^2$. Además, las asintóticas del núcleo de potencial garantizan que $phi$ esté acotada. Por lo tanto, mediante el teorema de Liouville, $\phi$ es constante. Usando la identidad $p(3-x) + p(x) = 1$, encontramos que esta constante es precisamente $\frac{1}{2}$. Por lo tanto,

$$ p(x) = \frac{1}{2} + c [\mathfrak{a}(x-1) - \mathfrak{a}(x-2)]. $$

El valor de la constante $c$ puede determinarse sustituyendo $x = 1$ y $x = 2$, lo que da como resultado

$$ p(x) = \frac{1}{2}\left( 1 - \frac{\mathfrak{a}(x-1) - \mathfrak{a}(x-2)}{\mathfrak{a}(1)} \right). $$

(Aquí, utilizamos la simetría $\mathfrak{a}(-x) = \mathfrak{a}(x)$ y $\mathfrak{a}(0) = 0$.) Luego, al sustituir $x = 0$ en la identidad anterior, la probabilidad deseada es

$$ p(0) = \frac{\mathfrak{a}(2)}{2\mathfrak{a}(1)}. \tag{1} $$

Por lo tanto, basta con calcular $\mathfrak{a}(1)$ y $\mathfrak{a}(2)$. La primera se resuelve fácilmente utilizando la simetría:

$$ \mathfrak{a}(1) = \frac{2}{4\pi^2} \int_{\mathbb{T}^2} \frac{1 - \cos(k_1)}{2 - \cos(k_1) - \cos(k_2)} \, \mathrm{d}k = \frac{1}{4\pi^2} \int_{\mathbb{T}^2} \mathrm{d}k = 1. $$

Además, al invocar la fórmula $\frac{1}{2\pi} \int_{0}^{2\pi} \frac{\mathrm{d}\theta}{a-\cos\theta} = \frac{1}{\sqrt{a^2 - 1}}$, $a > 1$, obtenemos

\begin{align*} \mathfrak{a}(2) &= \frac{2}{4\pi^2} \int_{\mathbb{T}^2} \frac{1 - \cos(2k_1)}{2 - \cos(k_1) - \cos(k_2)} \, \mathrm{d}k \\ &= \frac{1}{\pi} \int_{\mathbb{T}} \frac{1 - \cos(2k_1)}{\sqrt{(2 - \cos(k_1))^2 - 1}} \, \mathrm{d}k_1 \\ &= \frac{4}{\pi} \int_{0}^{\pi} \frac{\sin^2(k_1)}{\sqrt{(1 - \cos(k_1))(3 - \cos(k_1))}} \, \mathrm{d}k_1 \\ &= \frac{4}{\pi} \int_{-1}^{1} \frac{\sqrt{1-t^2}}{\sqrt{(1 - t)(3 - t)}} \, \mathrm{d}t \tag{$t=\cos k_1$} \\ &= \frac{4}{\pi} \int_{-1}^{1} \sqrt{\frac{1+t}{3-t}} \, \mathrm{d}t \\ &= \frac{4}{\pi} \int_{0}^{1} \frac{4\sqrt{u}}{(1+u)^2} \, \mathrm{d}u \tag{$u = \frac{1+t}{3-t}$} \\ &= \frac{4}{\pi} (\pi - 2). \end{align*}

Al sustituir estos valores en $\text{(1)}$, se sigue entonces que

$$ p(0) = 2 - \frac{4}{\pi}. $$


[Stö49] Alfred Stöhr. Über einige lineare partielle differenzengleichungen mit konstanten koeffizienten. Mathematische Nachrichten, 3(6):330–357, 1949.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X