La probabilidad de aterrizaje en la n-ésima de la escalera.

Question

Pregunta inicial: comenzamos a subir una escalera de inicio en la escalera de cero. Elegimos a tomar cualquiera de 1,2, o 3 pasos a la vez, donde cada número de pasos tienen la misma probabilidad de ser elegido. ¿Cuál es la probabilidad de acertar el cuarto de la escalera?

Como yo: En lugar de reconocer qué tipo de problema que me estaba mirando, me formó un árbol, y se encontró que hay siete formas de llegar al cuarto de la escalera. Teniendo en cuenta los pesos de cada uno de estos resultados he encontrado que la probabilidad de golpear el cuarto de la escalera a ser 37/81.

Pregunta más profunda: Mientras me encontrado que hallar el número de maneras de golpear la $n$th paso no fue demasiado difícil (creo que es la suma de las maneras de golpear a los tres pasos anteriores, $k(n-3)+k(n-2)+k(n-1)$), no fue capaz de utilizar con éxito para encontrar la regla general para la probabilidad de golpear el $n$th paso.

Estoy buscando algunos consejos clasificación de este tipo de problemas de probabilidad, o tal vez un enlace a un problema similar. Este podría ser visto como una especie de paseo aleatorio? Hay alguna esperanza para una forma cerrada (explícito) de la solución?

Answer 1

Deje $p_{n,k}$ la probabilidad de golpear el $n^\text{th}$ de la escalera después de exactamente $k$ pasos, y deje $p_n$ la probabilidad de golpear el $n^\text{th}$ de la escalera en algún momento. A continuación, $p_{n,k}$ es el coeficiente de $x^n$ en el polinomio $(\frac13x+\frac13x^2+\frac13x^3)^k$. Por lo tanto, $p_n=\sum_{k=0}^\infty p_{n,k}$ es el coeficiente de $x^n$ en $$ \begin{align} \sum_{k=0}^\infty \left(\tfrac13x+\tfrac13x^2+\tfrac13x^3\right)^k &=\frac1{1-(\tfrac13x+\tfrac13x^2+\tfrac13x^3)} \\&=\frac{1/2}{1-x}+\frac{1/4}{1+x/(1+i\sqrt{2})}+\frac{1/4}{1+x/(1-i\sqrt{2})} \end{align} $$ La última igualdad se puede derivar el uso de la costumbre parcial fracciones método. La expansión de cada una de estas fracciones en su serie de Taylor, se obtiene $$ \boxed{p_n = 1/2+\frac{1/4}{(-1-i\sqrt{2})^n}+\frac{1/4}{(-1+i\sqrt{2})^n}} $$ Así que se puede obtener una respuesta exacta que involucran números complejos por arte de magia la cancelación, junto con un asintótica resultado de que las probabilidades convergen de manera exponencial rápidamente a $1/2$.

Answer 2

Deje $N(n,k)$ el número de maneras de llegar a la escalera $n$ exactamente $k$ pasos. Si $P_n$ es la probabilidad de alcanzar la escalera $n$, entonces:

$$P_n = \sum_{k = 0}^{\infty}3^{-k}N(n,k)$$

Tenga en cuenta que $N(n,k)$ está definida para todos los números enteros $n$ y todos los números enteros no negativos $k$, y por lo $P_n$ está definida para todos los números enteros $n$.

Si usted ha llegado a la escalera $n$$k$, e $k \geq 1$, lo que significa que estaban en la escalera $n-1, n-2$ o $n-3$ $k-1$ pasos. Así:

$$N(n,k) = N(n-1,k-1) + N(n-2,k-1) + N(n-3,k-1); \qquad k \geq 1$$

Ahora, suponga $n > 0$. Tenemos:

\begin{align*} P_{n} &= N(n,0) + \sum_{k = 1}^{\infty}3^{-k}\big(N(n-1,k-1) + N(n-2,k-1) + N(n-3,k-1)\big) \\ &= \frac{1}{3}\sum_{k = 0}^{\infty}3^{-k}N(n-1,k) + 3^{-k}N(n-2,k) + 3^{-k}N(n-3,k) \\ &= \frac{1}{3}\big(P_{n-1} + P_{n-2} + P_{n-3}\big) \end{align*}

Desde $N(n,0) = 0$$n \neq 0$. Así que, fuera de $P_0 = 1$, cada probabilidad es simplemente el promedio de las tres probabilidades previas, y $P_n = 0$$n < 0$. Algunos valores iniciales:

$$P_0 = 1$$

$$P_1 = \frac{1}{3}(0 + 0 + 1) = \frac{1}{3}$$

$$P_2 = \frac{1}{3}(0 + 1 + 1/3) = \frac{4}{9}$$

$$P_3 = \frac{1}{3}(1 + 1/3 + 4/9) = \frac{16}{27}$$

$$P_4 = \frac{1}{3}(1/3 + 4/9 + 16/27) = \frac{37}{81}$$

Lo cual está de acuerdo con su cálculo.

Answer 3

Tenemos un proceso de Markov

$\begin{bmatrix}p_{n+3}\\p_{n+2}\\p_{n+1} \end{bmatrix} =\begin{bmatrix}\frac {1}{3}&\frac 13&\frac 13\\1&0&0\\0&1&0 \end{bmatrix}\begin{bmatrix}p_{n+2}\\p_{n+1}\\p_{n} \end{bmatrix}$

$p_{n+2} = A^n p_0$

$A$ es diagonalizable, pero me estoy haciendo un lío cuando me diagonlize.

Los valores propios son $1, \frac {-1+\sqrt 2 i }{3}, \frac {-1-\sqrt{2} i}{3}$