El problema del borracho en un valle.

Question

Consideramos una cadena de Markov en un subconjunto de enteros positivos $S =$ { $0, 1, 2, 3, .......N$ }, con probabilidades de transición definidas como sigue:

La cadena salta sólo una unidad a la izquierda o a la derecha.

$p(i, j) = 0$ si $|i - j|>1$

$p(i, i + 1) = (N - i) /N$ , para $i$ en { $1, 2, 3, ....., N-1$ }.

$p(i, i - 1) = i/N$ , para $i$ en { $1, 2, 3, ....., N-1$ }.

Suponemos que tenemos barreras absorbentes en $0$ y $N$ , por lo que tenemos $p(0, 0) = p(N, N) = 1$ .

¿Cuál es el tiempo esperado para que la cadena sea absorbida en $0$ o $N$ a partir de $i$ en { $0, 1, 2, 3, .......N$ }? Si $T_i$ es el tiempo que tarda la cadena en ser absorbida en $0$ o $N$ cuando se empieza en $i$ ¿Qué es? $E(T_i)$ ?

Esta cadena de Markov puede verse como un caso particular de una cadena de nacimiento y muerte, o como un paseo aleatorio unidimensional con 2 barreras de absorción y probabilidades que varían de un lugar a otro.

Yo lo llamaría el problema del borracho en un valle. Cuanto más se acerque a las barreras absorbentes (la cima de la colina), menos probable será que siga hacia ellas. Entonces, ¿cuál es el tiempo previsto para que el borracho llegue a la cima de las colinas que le rodean?

Pregunta principal. ¿El tiempo esperado de absorción es polinómico o exponencial (en $N$ )?

Nótese que este problema está relacionado con una clase de problemas de interés práctico.

Answer 1

Si hacemos los límites en $0$ y $N$ reflejando, en lugar de absorbiendo, entonces su paseo aleatorio es el Modelo de urna Ehrenfest . Es bien sabido que esta cadena de Markov tiene una distribución invariante $\pi_i={N\choose i}/2^N$ para $0\leq i\leq N$ .

En particular, el tiempo esperado para volver al origen, partiendo de ahí, es $\mathbb{E}_0(T_0)=1/\pi_0=2^N$ . Esto implica que el tiempo esperado para llegar a cero, comenzando en uno, es $\mathbb{E}_1(T_0)=2^N-1$ . Esto ya es exponencial en $N$ incluso cuando el punto de partida está justo al lado del límite.

Concedido, a partir de uno, podríamos llegar al punto límite $N$ primero. Pero estoy dispuesto a apostar que esto es tan improbable que $\mathbb{E}_1(T_{\{0,N\}})$ es exponencial en $N$ .

---

Actualización: Creo que he encontrado una manera de hacer esto riguroso. Crear un nuevo paseo aleatorio en un círculo mediante la combinación de los estados $0$ y $N$ Llamamos a este estado combinado $b$ (para el límite). Las probabilidades de transición son todas iguales, excepto desde $b$ se salta a cualquiera de los dos $1$ o $N-1$ con probabilidad $1/2$ . Esta cadena tiene una distribución invariable $\pi_j={N\choose j}/2^N$ para $j=1,\dots, N-1$ y $\pi_b=2/2^N$ .

El número esperado de pasos para llegar al límite, cuando se empieza por ahí, es $$\mathbb{E}_b(T_b)=1/\pi_b=2^{N-1}.$$ Por otro lado, el análisis del primer paso da $$\mathbb{E}_b(T_b)=1+\mathbb{E}_1(T_b)/2+\mathbb{E}_{N-1}(T_b)/2=1+\mathbb{E}_1(T_b),$$ donde la última ecuación es por simetría. Por lo tanto, $\mathbb{E}_1(T_b)=2^{N-1}-1$ , lo que implica para el modelo original que $\mathbb{E}_1(T_{\{0,N\}})=2^{N-1}-1.$

Answer 2

Si $i \in [0.1N,0.99N]$ entonces el tiempo esperado es exponencial, ya que para alcanzar el límite cuando se está fuera del intervalo $[N/4,3N/4]$ se desplaza hacia el límite con una probabilidad como máximo de $1/4$ . Si la probabilidad fuera $1/4$ entonces el tiempo esperado hasta alcanzar el límite sería exponencial en $N$ y por lo tanto $E(T_i)$ es exponencial en $N$ para $i \in [0.1N,0.99N]$ .

Answer 3

Si $k_i$ es el tiempo esperado de absorción condicionado a comenzar en $i$ entonces $k_0=k_N=0$ y el condicionamiento en el primer paso da $$ k_r = 1 + \frac{r}{N}k_{r-1} + \frac{N-r}{N} k_{r+1}.$$

En principio se pueden resolver: para $N=4$ se obtiene $0,7,8,7,0$ , para $N=5$ se obtiene $0, 15, 35/2, 35/2, 15, 0$ , para $N=6$ es $0,31,36,37,36,31, 0$ y así sucesivamente. Pero una forma cerrada parece difícil.

Dejar $\delta_i = k_i-k_{i-1}$ hace que la recurrencia sea de primer orden: se obtiene $$r \delta_r = N + (N-r) \delta_{r+1}$$ pero sigue sin ser fácil de resolver. Sustituyendo repetidamente se obtiene $$ \begin{align*} \delta_1 &= N+(N-1)\delta_2 \\ &= N + \frac{N(N-1)}{2} + \frac{(N-1)(N-2)}{2}\delta_3 \\ &= N + \frac{N(N-1)}{2} + \frac{N(N-1)(N-2)}{3} + \cdots \\ &= \cdots \end{align*}$$ - coeficientes binomiales. El $k_i$ son simétricos respecto a $N/2$ por lo que el $\delta_i$ son antisimétricos, y de ahí se puede obtener $k_1 = \delta_1 = \frac{2^{N-2}-2}{2}=2^{N-1}-1$ como observó el usuario940. De ahí se puede deducir $k_2 = \frac{N}{N-1}(2^{N-1}-2)$ y así sucesivamente. Pero si sólo te importa el crecimiento, ya sabes $k_1$ es exponencial en $N$ y es fácil conseguir que el otro $k_i$ son mayores que $k_1$ .