Distancia máxima del paseo aleatorio 2D

Question

Realizamos un paseo aleatorio que comienza en $(0,0)\in\mathbb{Z}^2$ y en cada paso, con probabilidad $p=1/4$ , nos movemos una unidad hacia arriba, hacia abajo, hacia la izquierda o hacia la derecha. Después de $n$ pasos, ¿cuál es el valor esperado del máximo $||\cdot||_1$ -¿distancia (taxi-distancia) que tenía el caminante al origen?

En realidad no sé si hay una fórmula cerrada para esto. Si no es así, ¿hay ideas sobre cómo encontrar límites interesantes? ¿Sería más fácil la cuestión si se consideran otras distancias?

Creo que hay un límite inferior de $\sqrt{n}$ . ¿Es esto correcto? ¿Alguna idea sobre cómo mostrar esto?

Answer 1

A continuación se indican las previsiones $L_1$ -distancia de la ubicación final después de $n$ pasos (y no la desviación máxima respecto al origen durante esos pasos).

---

Dejemos que $S_n$ denotan la posición del paseo aleatorio después de $n$ pasos. También deja que $T_n\equiv(T_{1,n},T_{2,n})$ sea $2$ paseos aleatorios simples e independientes sobre $\mathbb{R}$ . Entonces, girando $T_n$ por $45$ grados y dividiendo por $\sqrt{2}$ se obtiene $S_n$ . La distribución de $T_{j,n}$ es bien conocido : $$ p_{j,n}(d):=\mathsf{P}(T_{j,n}=d)=2^{-n}\binom{n}{(n+d)/2} $$ para $d\in \{-n,-n+2,\ldots,n-2,n\}$ y $0$ de lo contrario. Entonces $$ \mathsf{E}\|S_n\|_1=\sum_{i=-n}^n\sum_{j=-n}^n \frac{|i\cos(\theta)-j\sin(\theta)|+|i\cos(\theta)+j\sin(\theta)|}{\sqrt{2}}\cdot p_{1,n}(i)p_{2,n}(j), $$ donde $\theta\equiv 45\pi/180$ .

---

La primera $10$ valores: $$ \begin{array}{c|c} n & \mathsf{E}\|S_n\|_1 \\ \hline 1 & 1 \\ \hline 2 & 1.5 \\ \hline 3 & 1.875 \\ \hline 4 & 2.188 \\ \hline 5 & 2.461 \\ \hline 6 & 2.707 \\ \hline 7 & 2.933 \\ \hline 8 & 3.142 \\ \hline 9 & 3.339 \\ \hline 10 & 3.524 \\ \hline \end{array} $$

Answer 2

Dejemos que $e(n)$ sea la distancia histórica máxima esperada de $(0,0)$ en $n$ pasos, asumiendo una posición inicial de $(0,0)$ .

Para los números enteros $x,y$ con $0\le y\le x$ , dejemos que $f(x,y,m,n)$ sea la máxima distancia histórica esperada desde el origen, suponiendo que

• La posición inicial era $(0,0)$ . $\\[2pt]$
• La posición actual es $(x,y)$ . $\\[2pt]$
• La distancia máxima histórica de $(0,0)$ realizado hasta ahora es $m$ . $\\[2pt]$
• El número de pasos que quedan por dar es $n$ .

Tenga en cuenta que $e(n)=f(0,0,0,n)$ .

Como se muestra a continuación, $f$ se puede calcular recursivamente, lo que nos permite encontrar rápidamente (menos de un minuto) los valores de $e(n)$ para $0\le n\le 100$ .