Una rigurosa prueba de un hecho obvio acerca de una cadena de Markov

Question

Así que estoy teniendo problemas para escribir una rigurosa prueba de algo que parece muy claro.

Considere la siguiente cadena de Markov en un anillo: con una probabilidad de $1/2$, se queda donde está, con una probabilidad de $1/2-1/n$ se mueve hacia la izquierda, y con una probabilidad de $1/n$ salta al azar a una de nodo. Cuando el último ha ocurrido, vamos a decir que de un salto se ha producido.

Deje $A$ ser el caso de que por el tiempo $10n$, exactamente un salto se ha producido. Deje $B$ ser el caso de que el paseo aleatorio nunca ha tomado el auto loop en el nodo $1$.

Quiero demostrar que la $P(B|A)$ es menor acotado por una constante independiente de $n$. En realidad estoy adivinando que $P(B|A) \geq 1/2^{11}$.

Esto me parece obvio: condicional en $A$, el número de veces que la cadena de transiciones en el nodo $1$ tiempo $10n$ es en la mayoría de las $11$, y la probabilidad de no tomar el auto-loop es $1/2$ cada vez. Pero, ¿cómo decir esto formalmente?

Edit: en Realidad el esquema superior es algo problemático: como Craig señala en los comentarios, teniendo exactamente un salto cambios en las probabilidades de tomar el auto loop cuando la cadena está en el nodo $1$. Pero, presumiblemente, la oportunidad de tomar el sentido contrario de transición sólo debe aumentar, ya que el número de saltos está por debajo de lo que cabría esperar en $10n$ transiciones. Así que me gustaría estar perfectamente satisfecho con la obligada $(1/2-1/n)^{11}$ lugar.

Answer 1

Yo no acababa de atrevemos a escribir esto cuando hubo un $500$-punto de recompensa en la duda, ya que parece demasiado fácil para que. Es más probable que no que me estoy perdiendo algo básico, ya que no se había dado respuesta a pesar de la inusual recompensa; pero esto todavía parece bastante sencillo para mí, así que voy a explicar y tal vez usted me puede decir donde estoy pasando mal.

Primera vez que voy a reformular la pregunta para asegurarse de que el problema no está en mi falta de comprensión de la pregunta. Tenemos $n$ estados dispuestos de forma cíclica, y las probabilidades de transición que son invariante en el tiempo y la traducción-invariante. Para cada estado hay tres posibilidades en cada paso: Con una probabilidad de $1/2$, el estado sigue siendo el mismo, con una probabilidad de $1/2-1/n$ no es una transición al siguiente estado en el ciclo, y con una probabilidad de $1/n$ hay una transición a un estado seleccionado de forma aleatoria con una distribución uniforme sobre todos los $n$ estados (incluyendo el estado actual y el estado en el ciclo). Así, el total de las probabilidades de transición se $1/2+1/n^2$ a permanecer en el mismo estado, $1/2-1/n+1/n^2$ para la transición al siguiente estado en el ciclo, y $1/n^2$ para las transiciones para el resto de $n-2$ estados.

Ahora queremos considerar este proceso bajo la condición de $A$ que por el tiempo $10n$ exactamente un salto se ha producido (donde un "salto" se aclaró para incluir también a la $1/n^2$ de probabilidad de permanecer en el mismo estado). En particular, queremos limitar la probabilidad bajo esta condición del evento $B$ que "la caminata al azar nunca ha tomado el auto loop en el nodo 1". Hay un número de posibles ambigüedades allí. En primer lugar, supongo que "nunca" significa "no por el tiempo $10n$". Segundo, robjohn la pregunta de si el "auto loop" incluye el $1/n^2$ plazo o sólo el $1/2$ plazo no ha sido contestada. No creo que esto hace una diferencia para mi argumento, voy a asumir que el $1/n^2$ plazo se incluye, desde el enlazados para que el caso implica también atado en el otro caso. Tercero, MartianInvader la pregunta sobre si "nodo 1" se refiere al nodo inicial no ha sido contestada. De nuevo, voy a asumir que no, ya que hace a la cuestión, al menos tan duro como cualquier otra interpretación. En resumen, yo interpreto $B$ "el paseo aleatorio no ha permanecido en el nodo inicial en cualquier paso hasta el momento de $10n$".

Ahora, ya que las probabilidades de transición son invariante en el tiempo, bajo la condición de $A$ que por el tiempo $10n$ exactamente un salto se ha producido, cada vez es igualmente probable que sea el momento de un salto, por lo que el total de las probabilidades es el promedio de las probabilidades de $10n$ procesos, cada uno de los cuales tiene un salto sin duda que ocurren en un momento determinado $1\le t\le10n$, y en todos los otros momentos no hay ningún salto, y el resto de las probabilidades de transición se normaliza por un factor de $1/(1-1/n)$, por lo que se $\frac12\frac1{1-1/n}$$(\frac12-\frac1n)\frac1{1-1/n}$, respectivamente. Cada uno de estos $10n$ procesos son procesos de Markov. En cada uno de estos procesos, la probabilidad de nunca tomar el auto de bucle en el nodo inicial es de al menos $(\frac12\frac1{1-1/n})^m\gt(\frac12)^m$ donde $m$ es el mayor número de probabilidades de que el proceso pueda tener, hasta el momento de $10n$, de tomar ese auto loop sin tomar. Ahora en $10n$ pasos, el proceso puede tener en la mayoría de $10$ tales posibilidades sin saltar, y el salto puede añadir en más de una oportunidad nueva, por lo $m\le11$. Por lo tanto, en cada uno de los procesos, la probabilidad de nunca tomar el auto loop es, al menos,$1/2^{11}$, y por lo tanto, esta obligado tiene también para el promedio de estas probabilidades, que es el deseado probabilidad condicional.

Answer 2

No es una solución

Desde mi recompensa caduca pronto, pensé que me iba a añadir un comentario largo sobre este problema. No estoy diciendo que esto es la manera correcta de resolver el problema, pero esto es como yo lo veo.

Deje $\alpha$ denotar un fijo de partida del estado para el proceso de $(X_t)$, es decir,
suponga $\mathbb{P}(X_0=\alpha)=1$.

La intuición y el rigor que se conjugan a la perfección en el siguiente modificación problema:

Deje $T$ ser el tiempo cuando la cadena vuelve a $\alpha$ por décima vez. Por el fuerte de Markov de la propiedad, el diez las transiciones de estado $\alpha$ a $T$ son independientes de las variables aleatorias. Por lo tanto, dejando $S$ a ser el número de veces que "estar" en $\alpha$, tenemos $\mathbb{P}(S=0, 0\leq t\leq T)=(1/2)^{10}$.

Ahora, el único invariante de distribución de probabilidad de $\pi$ para esta cadena es uniforme a lo largo de la $n$ a los estados y, en consecuencia, $\mathbb{E}(T_\alpha)=1/\pi_\alpha=n,$ donde $T_\alpha$ es el tiempo de retorno de la estatal $\alpha$.

Puesto que el promedio de tiempo para una vuelta es exactamente $n$, esperamos unos diez devuelve hasta el momento de $10n$. Esto sugiere $$\mathbb{P}(S=0, 0\leq t\leq 10n)\approx \mathbb{P}(S=0, 0\leq t\leq T)=(1/2)^{10}.\hskip.7in (1)$$ Si pudiéramos hacer esta aproximación rigurosa, podemos obtener el necesario límite inferior.

En mi opinión, acondicionado en el número de saltos a ser igual a uno es un arenque rojo. Esa condición no es necesaria para controlar el número de devoluciones a $\alpha$ a $10n$. El mismo podría ser alcanzado por una buena aproximación en (1).

Espero que alguien que es mejor en tales argumentos se tomará el reto y darle una rigurosa prueba de este resultado.

Answer 3

Correcto, si la tengo totalmente entendido mal la pregunta.

Dado que el 1 de salto se ha producido, la probabilidad de que el otro $10n$ se mueve hacia la izquierda es $(1-\frac{2}{n})^{10n}$ debido a que la probabilidad de que un nodo determinado se moverá hacia la izquierda si no se mantuvo de la misma es $2(\frac{1}{2}-\frac{1}{n})$.

$\frac{d}{dx}(1-\frac{2}{n})^{10n}$=$\frac{2(10n)}{n}(1-\frac{2}{n})^{10n}$

$\frac{d}{dx}=0$ al $10n-1=0$ o $1-\frac{2}{n}=0$, que es al $n=2$ o $n=0.1$.

No hay puntos estacionarios o discontinuidades para n>2 por lo tanto, si la función comienza a aumentar seguirá en aumento. La probabilidad es mayor para n=3 que para n=2, por lo que se comenzará a aumentar. Para n=2, la probabilidad es 0, que es menor que su límite inferior. Sólo valores enteros de n se consided, así que para n>2 el límite inferior es $\frac{1}{3^{30}}$.