El paseo aleatorio de dos borrachos

Question

El problema es el siguiente: dos borrachos comienzan en cada extremo de un callejón de longitud n. Aparte de los extremos, cada uno se mueve un paso hacia delante o un paso hacia atrás de forma aleatoria. En los extremos del callejón se mueven hacia el centro con probabilidad $1$ . ¿Cuál es el número de pasos previstos antes de que se encuentren?

En el problema que busco resolver $n = 99$ aunque podría ser cualquier número de impar.

Buscamos la solución más elegante a este problema. En nuestro grupo se ha resuelto mediante Monte-Carlo y cadenas de Markov, pero quiero creer que hay una solución más sencilla que no implique $2400 \times 2400$ matrices. Intento inspirarme en la pregunta de abajo, pero la condición de contorno complica las cosas.

Probabilidad exacta de colisión de dos caminantes aleatorios independientes después de N pasos

Se aceptarán con gusto los enlaces a documentos u otras preguntas que traten este problema en particular.

Answer 1

He aquí algunas observaciones fáciles sobre la cuestión (pero no una solución). En primer lugar, si $n$ es impar las dos partículas nunca se encuentran, por razones de paridad, por lo tanto se puede asumir que $n$ está en paz.

Digamos que la partícula que parte de $0$ golpes $n$ en el momento $T_n$ . Las partículas no pueden cruzarse sin encontrarse, por lo que en el momento $T_n$ Ya se conocieron. Por lo tanto, la hora de la reunión $M_n$ es casi seguramente finito y $$E(M_n)\leqslant E(T_n)=n^2. $$ Tenga en cuenta que $M_n$ es también como máximo el tiempo de golpeo $T'_n$ de $0$ por la partícula que parte de $n$ Por lo tanto $$E(M_n)\leqslant E(\min(T_n,T'_n)),$$ donde $T'_n$ es una copia independiente de $T_n$ . A la inversa, las partículas no pueden encontrarse antes de que al menos una de ellas choque $n/2$ por lo que $$E(M_n)\geqslant E(\min(T_{n/2},T'_{n/2})). $$ Esto sugiere que podría existir algún positivo finito $\mu$ tal que $E(M_n)\sim\mu n^2$ cuando $n\to\infty$ . Si esto es así, se sabe que $\frac14\theta\leqslant\mu\leqslant\theta$ donde $\theta$ en $(0,1)$ se define por el equivalente $E(\min(T_n,T'_n))\sim\theta n^2$ .

Por último, hay que tener en cuenta que $\min(T_n,T'_n)$ es el tiempo de primer golpe de la frontera del cuadrado $[-n,n]^2$ por un paseo aleatorio en $\mathbb Z^2$ a partir de $(0,0)$ con pasos $(\pm1,\pm1)$ .