Expected number of steps in a random walk with a boundary

Question

Let's say I am trying to climb a flight of $N$ stairs. Each time I want to take a step, I flip a fair coin. Heads means I take a step up; tails means I take a step down. If I'm at the bottom of the stairs, tails means I flip the coin again. How many total times do I flip the coin, on average, before I reach the top?

This process is like a 1-D random walk except for the bottom-of-the-stairs condition, so I would expect the answer to involve $N^2$ somehow, but I don't know how to compute it exactly.

Answer 1

Let $p_n$ be the expected number of coin flips to reach the top starting $n$ steps below the top. The recursive equation is $$p_n=(p_{n-1}+p_{n+1})/2+1$$ for $0<n<N$.

That is, $\Delta_{n+1}=\Delta_{n}-2$, where $\Delta_i\equiv p_i-p_{i-1}$. So $\Delta_i=\Delta_1-2(i-1)$.

• The boundary condition at the bottom of stairs is $p_N=(p_{N-1}+p_{N})/2+1$ or $\Delta_N=2$. Substituting the expression for $\Delta_i$ yields $\Delta_1-2(N-1)=2$, and so $\Delta_1=2N$.
• Using the boundary condition at top of stairs ($p_0=0$) gives $p_i=\sum_{j=1}^{i}{\Delta_j}=(\Delta_1-i+1)i=(2N-i+1)i$ for $0\le i\le N$.

Thus, the expected number of coin flips to reach the top of stairs starting from the bottom is $p_N=N^2+N$.