El tiempo de retorno esperado infinito implica que las probabilidades de retorno tienden a cero

Question

Para una cadena de Markov $X_n$ Quiero demostrar que si $$ \mathbb{E} (\min\{n \geq 1:X_n = i\}\mid X_0 = i) = \infty$$ (es decir, si $i$ es transitoria o recurrente nula), entonces $$ p_{ii}^{(n)} \equiv \mathbb{P}(X_n = i \mid X_0 = i) \to 0 \quad \mathrm{as} \quad n \to \infty .$$ Mi intuición es que si el valor esperado anterior es infinito, entonces la probabilidad de que la primera vuelta a $i$ se produce en $n$ debe decaer relativamente lento con $n$ lo que significa que es "bastante probable" que la cadena no haya vuelto a $i$ en la primera $n$ pasos. De ahí que las probabilidades de retorno sean pequeñas. Sin embargo, no puedo convertir esto en una prueba de que decaen a cero. Por favor, sea lo más elemental posible.

---

Si $i$ es transitoria, entonces el teorema es fácil de demostrar. La transitoriedad equivale a la suma de las $p_{ii}^{(n)}$ siendo finitos, lo que significa que deben tender a cero. El caso de la recurrencia nula está resultando más difícil.

Answer 1

Aquí hay una prueba que encontré en la sección 1.8 de las cadenas de Markov de James Norris. Es mucho más sofisticada de lo que pensé que sería necesario; si alguien tiene una prueba más sencilla que ofrecer, se agradecería mucho.

Supongamos que $X_n$ es recurrente nulo. Si es periódico con periodo $d$ podemos considerar la subcadena aperiódica $X_{dn}$ y demostrar que las probabilidades de retorno de esta cadena tienden a cero, demostrando así que todas las probabilidades de retorno tienden a cero. Por lo tanto, supongamos que la cadena es aperiódica.

Dejemos que $T_j$ ser el primer tiempo de retorno al estado $j$ . Sabemos que $$ \infty = \sum_{k = 0}^\infty k \,\mathbb{P}_j(T_j = k) = \sum_{k = 0}^\infty \mathbb{P}_j(T_j > k) \,.$$ Dado $\varepsilon > 0$ elija $K$ tal que $$ \sum_{k=0}^K \mathbb{P}_j(T_j > k) \geq \frac{1}{\varepsilon} \,.$$ Entonces, para $n \geq K$ , $$ \begin{align}1 &\geq \sum_{k =n-K}^n\mathbb{P}(X_k = j, X_m \neq j \;\text{for}\; m=k+1,\ldots,n) \\ &= \sum_{k =n-K}^n \mathbb{P}(X_k = j)\mathbb{P}_j(T_j > n - k) \\ &=\sum_{k =0}^K \mathbb{P}(X_{n-k} = j)\mathbb{P}_j(T_j > k)\,.\end{align}$$ Por lo tanto, debemos tener $\mathbb{P}_j(X_{n-k} = j)\leq \varepsilon$ para algunos $k = 0,1,\ldots,K$ .

Ahora hacemos un argumento de acoplamiento. Sea $Y_n$ sea una cadena con las mismas probabilidades de transición que $X_n$ y una distribución inicial que se definirá más adelante. La cadena $W_n = (X_n,Y_n)$ es irreducible en virtud de la aperiodicidad de $X_n$ . Si $W_n$ es transitorio, entonces fijando $X_n$ y $Y_n$ para tener la misma distribución inicial podemos demostrar fácilmente que las probabilidades de retorno tienden a cero.

Por lo tanto, supongamos que $W_n$ es recurrente. Pero un irreducible La cadena recurrente explora todos los estados con probabilidad unitaria, por lo que las dos cadenas $X_n$ y $Y_n$ se reúnen casi con seguridad. Set $Z_n$ para igualar $X_n$ antes de que las dos cadenas se encuentren (en $n = T$ , digamos) y $Y_n$ a partir de entonces. Entonces $X_n$ y $Z_n$ tienen la misma distribución por lo que $$\begin{align}|\mathbb{P}(X_n = j) - \mathbb{P}(Y_n = j)| &= |\mathbb{P}(Z_n = j) - \mathbb{P}(Y_n = j)| \\ &=|\mathbb{P}(X_n = j, n < T) - \mathbb{P}(Y_n = j, n < T)| \\ & \leq \mathbb{P}(n < T) \to 0 \,. \end{align} $$ De ahí que las dos cadenas $X_n$ y $Y_n$ tienen probabilidades de retorno convergentes. Ahora sólo tenemos que explotar el hecho de que somos libres de elegir la distribución inicial para $Y_n$ . Si $X_n$ tiene una distribución inicial $\lambda$ dejar $Y_n$ tienen una distribución inicial $\lambda P^k$ para $k = 1,\ldots,K$ para que $\mathbb{P}(Y_n = j) = \mathbb{P}(X_{n+k} = j)$ . Como las dos cadenas tienen probabilidades convergentes, podemos encontrar $N$ tal que para $n \geq N$ y $k=1,\ldots,K$ , $$ | \mathbb{P}(X_n = j) - \mathbb{P}(X_{n+k} = j)| \leq \varepsilon \,.$$ Finalmente, sabemos por lo anterior que en cualquier intervalo de longitud $K$ hay algo de $k$ tal que $\mathbb{P}(X_k = j) \leq \varepsilon$ y por lo tanto $$ \mathbb{P}(X_n = j) \leq 2 \varepsilon \,.$$ Desde $\varepsilon > 0$ era arbitraria hemos demostrado el resultado.

Answer 2

Aquí hay otra prueba tomada del capítulo 3 de A First Course in Stochastic Processes de Karlin y Taylor. Es más elemental pero quizás menos esclarecedora. Sea $X_n$ sea una cadena de Markov recurrente nula y aperiódica (ver otra respuesta para reducir al caso aperiódico). Sea $T_j$ ser el primer tiempo de retorno al estado $j$ y definir las secuencias $$a_n = \mathbb{P}_j(T_j = n) \quad \text{and} \quad u_n = p_{jj}^{(n)}\,.$$ Estos satisfacen la ecuación $$ u_n - \sum_{k=0}^{n-1}u_k \,a_{n-k} = 0 \quad n\geq 1\tag{1}\,.$$ Ahora $u_n$ es una secuencia acotada por lo que $\lambda = \lim \sup u_n$ es finito, y podemos encontrar una subsecuencia $u_{n_j}$ que converge a $\lambda$ . Desde $X_n$ es aperiódico sabemos que $u_d > 0$ para todo lo que sea suficientemente grande $d$ y junto con la recurrencia nula esto implica $a_d > 0$ para todo lo que sea suficientemente grande $d$ . Demostramos que para tales $d$ la secuencia $u_{n_j-d}$ converge al mismo límite $\lambda$ .

---

Supongamos lo contrario. Entonces existe algún $\mu < \lambda$ tal que $u_{n_j-d} < \mu$ para un número infinito de $j$ . Establecer $\varepsilon = a_d(\lambda-\mu)/3 > 0$ . Tenemos, por recurrencia nula, $$ \sum_{n=1}^\infty a_n = 1 \quad \implies \quad \exists N \geq d\quad \text{with} \quad\sum_{n=1}^N a_n > 1 - \varepsilon \,.$$ Ahora dejemos que $j$ sea tal que $n_j \geq N$ , $u_{n_j} > \lambda - \varepsilon$ , $u_{n_j-d} < \mu$ y $u_n < \lambda + \varepsilon$ para todos $n \geq n_j - N$ . Entonces, aplicando estas desigualdades a la ecuación de recursión $(1)$ produce $$ \begin{align} u_{n_j} &<\sum_{k=0}^{n_j - N - 1} \,a_{n_j-k} + \sum_{k=n_j - N}^{n_j-1} u_k a_{n_j-k} < \varepsilon + \sum_{k=n_j - N}^{n_j-1}u_k \,a_{n_j-k} \\ &< \varepsilon + (\lambda + \varepsilon)(a_1 + \cdots a_{d-1} + a_{d+1} + \cdots + a_N) + a_d \mu \\ &<\varepsilon + (\lambda+ \varepsilon)(1- a_d) + a_d \mu <2 \varepsilon + \lambda - a_d(\lambda - \mu) = \lambda - \varepsilon \,. \end{align}$$ Pero esto contradice $u_{n_j} > \lambda - \varepsilon$ .

---

Ahora dejemos que $r_n = a_{n+1} + a_{n+2} + \cdots$ , de tal manera que $r_0 = 1$ y $a_n = r_{n-1}-r_n$ . Por recurrencia nula tenemos $$\sum_{n=0}^\infty r_n = \infty \tag{2} \,.$$ Entonces, a partir de la ecuación $(1)$ encontramos $$ r_0 u_n + r_1 u_{n-1} + \cdots + r_n u_0 = r_0 u_{n-1} + r_1 u_{n-2} + \cdots + r_{n-1} u_0 \,.$$ Si el lado izquierdo es igual a $A_n$ se puede escribir $A_n = A_{n-1}$ , donde $A_0 = r_0 u_0 = 1$ . Por lo tanto, para un $n_j \geq N \geq d$ tenemos $$ r_{d} u_{n_j-d} + r_{d+1} u_{n_j-d-1} + \cdots + r_{N} u_{n_j - N} \leq A_{n_j}= 1 \,. $$ Ahora tomando el límite $j \to \infty$ lleva a $$ (r_d + r_{d+1} + \cdots +r_N) \lambda \leq 1 \,.$$ Por último, dado que $N$ es arbitraria, la ecuación $(2)$ nos dice $\lambda = 0$ . Por lo tanto, $$ \lim_{n\to \infty} u_n = 0 \,.$$

Answer 3

Esto es más un comentario extendido que una respuesta, pero quería decir que la prueba de Karlin y Taylor puede considerarse bastante esclarecedora. La idea de buscar un "límite local" a lo largo de $n_k$ es una técnica general en la teoría ergódica. Hay una manera de hacer todo el manejo de épsilon por adelantado que creo que hace la prueba más clara.

Dada una secuencia $n_k$ Considere la posibilidad de definir las estadísticas locales limitantes $$p_{-d}=\lim_{\substack{k\to\infty\\ n_k\geq d}} p_{ii}^{(n_k-d)}\text{ for $ d\geq 0 $}$$ Estos límites podrían no converger para una secuencia general $n_k$ pero podemos pasar sucesivamente a sucesiones más pequeñas de forma que el límite para $d$ existe, y finalmente diagonalizar para obtener una secuencia donde todos los límites convergen. Con más detalle: definir $n^{0}_k=n_k$ y para cada $d\geq 0$ elige una subsecuencia $n^{d+1}_k$ de $n^d_k$ tal que $p_{ii}^{(n^{d+1}_k-d)}$ converge como $k\to\infty$ . Entonces todos los límites existen a lo largo de la secuencia diagonal $n^k_k$ .

De forma aún más abstracta, los límites pueden conjurarse automáticamente a partir del teorema de Hahn-Banach, o de sus otras formas como el teorema de la compacidad o el lema del ultrafiltro. Este límite preserva algunas propiedades de las secuencias originales:

Lema.

Consideremos una secuencia de pesos $w_d\geq 0$ , $d\in\mathbb Z$ y asumir que el límite $L=\lim_{k\to\infty}\sum_{d=0}^{\infty} w_d p_{ii}^{(n_k-d)}$ existe. Entonces:

• $\sum_{d=0}^\infty w_dp_{-d}\leq L$ .
• Si $\sum_{d=0}^\infty w_d$ converge entonces $\sum_{d=0}^\infty w_dp_{-d}=L$ .

Prueba . Para cada $N$ la suma $\sum_{d=0}^N w_d p_{ii}^{(n_k-d)}$ es una función continua del $N$ -tupla $(p_{ii}^{(n_k-0)},\dots,p_{ii}^{(n_k-N)})$ y el lim sup es como máximo $L$ por lo que el límite es como máximo $L$ . Para el segundo punto, observe que el término de error $\sum_{d=N+1}^\infty w_d p_{ii}^{(n_k-d)}$ es como máximo $\sum_{d=N+1}^\infty w_d$ que tiende a cero cuando $N\to\infty$ .

El argumento de Karlin y Taylor se puede poner en este escenario como sigue. Podemos encontrar una secuencia $n_k$ dando límites satisfactorios $p_0=\lambda>0$ y $p_{-d}\leq\lambda$ para todos $d$ . Entonces, utilizando el lema anterior, y la notación de su respuesta:

• $\sum_{d=0}^\infty r_d p_{-d}\leq 1$
• $\sum_{d=1}^\infty a_d p_{-d}=\lambda$
• $p_{-d}\leq \lambda$ para cada $d$ (es un límite de valores con lim sup como máximo $\lambda$ )

La condición $\sum_{d=1}^\infty a_d p_{-d}=\lambda$ es una combinación convexa de los valores $p_{-d}\leq\lambda$ que obliga a $p_{-d}=\lambda$ siempre que $a_d>0$ . Pero $\{d\mid a_d>0\}$ tiene huecos acotados, lo que significa que $\lambda\sum_{d:a_d>0} r_d$ diverge, contradiciendo $\sum_{d=0}^\infty r_d p_{-d}\leq 1$ .