Número esperado de pasos en un paseo aleatorio con un límite

Question

Digamos que estoy tratando de subir a un vuelo de $N$ escaleras. Cada vez que quiero dar un paso, le doy la vuelta a una moneda buena. Los jefes significa que puedo dar un paso; colas significa que tomar un paso hacia abajo. Si estoy en la parte inferior de las escaleras, las colas significa que voltear la moneda de nuevo. Cuántas veces puedo voltear la moneda, en promedio, antes de llegar a la cima?

Este proceso es como una 1-D paseo aleatorio , excepto por la parte inferior-de-las-escaleras condición, así que yo esperaría que la respuesta a involucrar a $N^2$, de alguna manera, pero no sé cómo calcular exactamente.

Answer 1

Deje $p_n$ ser el número esperado de tiradas de la moneda para llegar a la cima de partida $n$ pasos por debajo de la parte superior. La ecuación recursiva es $$p_n=(p_{n-1}+p_{n+1})/2+1$$ for $0<n<$ N.

Es decir, $\Delta_{n+1}=\Delta_{n}-2$ donde $\Delta_i\equiv p_i-p_{i-1}$. Por lo $\Delta_i=\Delta_1-2(i-1)$.

• La condición de contorno en la parte inferior de las escaleras es $p_N=(p_{N-1}+p_{N})/2+1$ o $\Delta_N=2$. Sustituyendo la expresión para $\Delta_i$ rendimientos $\Delta_1-2(N-1)=2$, y por lo $\Delta_1=2N$.
• Usando la condición de frontera en la parte superior de las escaleras ($p_0=0$) da $p_i=\sum_{j=1}^{i}{\Delta_j}=(\Delta_1-i+1)i=(2N-i+1)i$$0\le i\le N$.

Por lo tanto, se espera que el número de tiradas de la moneda para llegar a la cima de las escaleras, a partir de la parte inferior es $p_N=N^2+N$.