The average time for a spider to reach the top of a cliff

The following question was asked in an theoretical computer science entrance exam in India:

A spider is at the bottom of a cliff, and is n inches from the top. Every step it takes brings it one inch closer to the top with probability $1/3$, and one inch away from the top with probability $2/3$, unless it is at the bottom in which case, it always gets one inch closer. What is the expected number of steps for the spider to reach the top as a function of $n$?

How do we solve this problem? The recurrence for the expectation seems tricky because of the boundary conditions :(

• It is a random walk problem with starting position at $w=0$ and absorbing boundaries at $w=-n$ and $w=n$. When $w=0$ the probability of moving left is $1$ and right $0$. For values of $0< w\le n-1$ the probability of moving left is $\tfrac{2}{3}$ and right $\tfrac{1}{3}$. When $-n+1\le w<0$ the probability of moving left is $\tfrac{1}{3}$ and right $\tfrac{2}{3}$. So what is needed is the expected number of steps to reach $w=-n$ or $w=n$. I would help with this but it has been over 50 years since I studied random walk problems. Jul 4 '16 at 19:13
• My analysis was incorrect. The $w=0$ must be considered a reflecting boundary and $w=n$ an absorbing boundary. Jul 4 '16 at 19:24
• I would try working out the expected number of steps to ascend one inch from a given position and then summing (using linearity of expectation).
– amd
Jul 4 '16 at 19:35

The recurrence for the expectation $a_n$ is

$$a_k=1+\frac13a_{k-1}+\frac23a_{k+1}\;,$$

with solution $a_k=c_1+c_22^{-k}-3k$. The boundary conditions are $a_0=0$ and $a_n=1+a_{n-1}$, yielding $c_1+c_2=0$ and $c_22^{-n}-3n=1+c_22^{-(n-1)}-3(n-1)$. Solving the second equation for $c_2$ yields $c_2=-4\cdot2^n$, so $a_k=4\cdot2^n\left(1-2^{-k}\right)-3k$ and $a_n=4\cdot\left(2^n-1\right)-3n$.

The recurrence relation can be thought as,

Tn = (1/3)(Tn-1 + 1) + (2/3)(Tn-1 + 1 + Tn - Tn-2)

On further simplification

Tn = 3* Tn-1 - 2*Tn-2 + 3

The intuition is: To find expected number of steps to reach nth inch we first need to reach (n-1)th inch now after reaching (n-1)th inch we need 1 more step with probability 1/3 to complete nth inch this "move forward" step incurred additional cost of 1 otherwise with probability 2/3 we have to move 1 inch behind from (n-1)th inch so this "move back" step incurred additional cost 1 so we are now at (n-2)th inch, expected number of steps to complete n inches is Tn and expected number of steps to complete n-2 inches is Tn-2 so after reaching (n-2)th inch we require Tn-Tn-2 additional cost to complete n inches. Hope this helps