¿Cuál es la probabilidad de esta cadena de Markov no alcance el estado de $r$?

Question

Considere la posibilidad de un paseo aleatorio en los enteros no negativos.

Empezar a $0$, y en cada paso se mueva $1$ mayor, o $2$ menor (pero no puede ir por debajo de $0$). La dirección es recogida w.p. $1/2$ de forma independiente en cualquier paso.

De $0$ usted puede permanecer en $0$, o ir a $1$.

De $1$ usted lanza una moneda y acudir a $0$ o a $2$.

De $i>1$, de ir a la $i-2$ o a $i+1$.

• ¿Cuál es la probabilidad de que durante la $n$ pasos, el proceso nunca se alcanza el estado de $r$?

  Si este no tiene una forma simple (como una función de la $n,r$), podemos obtener una cota superior para que?

Este parece ser resueltos por una fórmula de recurrencia, pero no pude llegar a una expresión explícita.

Answer 1

Ya que es un proceso de Markov, estas probabilidades de satisfacer ecuaciones recursivas. Es decir, desde que en su caso llegar a $r$ es lo mismo que llegar a cualquier número de $r$ hasta $\infty$ (mover hacia arriba son de tamaño $1$), resolver un problema de la accesibilidad de la para el intervalo de $[r, +\infty)$. En general, usted tiene $V_0(x) = 1_A(x)$ y $$ V_{n+1}(x) = 1_A(x) + 1_{A^c}(x) \cdot PV_n(x) $$ donde $1_A$ es la función de indicador de $A$ $P$ es la matriz estocástica. Así, en $A$ la solución es obviamente $1$ todos los $n$, y podemos simplificar esto para $x\notin A$: para aquellos $$ V_{n+1}(x) = \sum_{y\noen Un}p(x,y)V_n(y) + \sum_{y\en A^c}p(x,y) $$ aquí $p(x,y)$ es la probabilidad de ir de$x$$y$. En su caso, sólo dos valores son probables cuando salen de $x$, vamos a decir $x^+$$x^-$, cada una con una probabilidad de $\frac12$. Así que usted consigue $$ V_{n+1}(x) = \frac12\left(V_n(x^-) + V_n(x^+)\right) $$ con las siguientes condiciones límite: $V_0(x) = 1_A(x)$ $V_n(x) = 1$ todos los $x\in A$. Eso debería ser suficiente para que usted pueda llevar en sus cálculos.

P. S. Acabo de dar cuenta que usted busca la probabilidad de no llegar a $r$. En ese caso, usted puede calcular lo que he propuesto y restar de $1$. O, si usted quiere tener una prolija solución, acaba de sustituir a $U_n := 1 - V_n$ en las ecuaciones anteriores: tendrás la posibilidad de obtener un aún más simple recurrente esquema.

Answer 2

Como mencioné en mi comentario, si $n>r$, entonces podemos tener atmost $r-1$ pasos que se mueven hacia arriba. Por lo que la probabilidad de que después de $n$ pasos, no llegamos a $r$ es,

$$P_{n,r} = \sum_{i=0}^{r-1} {n \choose i} {1 \over 2^{n}}$$

Para incluir la restricción de que nos siguen por encima de 0, aviso que si nos movemos hasta $p$ a veces, tenemos que avanzar $q$ veces abajo, de modo que $p+q=n$$p-2q>=0$. La solución para que el valor mínimo de $p$, obtenemos $p>={2n \over 3}$. Esto también pone una restricción que $r>=2n/3$. Ajuste el valor de $i$ en nuestro original eqution, obtenemos

$$P_{n,r} = \sum_{i={2n \over 3}}^{r-1} {n \choose i} {1 \over 2^{n}}$$