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.
Best Answer
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)$.
Thus, the expected number of coin flips to reach the top of stairs starting from the bottom is $p_N=N^2+N$.