1
$\begingroup$

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 :(

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jul 4 '16 at 19:13
  • $\begingroup$ My analysis was incorrect. The $w=0$ must be considered a reflecting boundary and $w=n$ an absorbing boundary. $\endgroup$ Jul 4 '16 at 19:24
  • $\begingroup$ 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). $\endgroup$
    – amd
    Jul 4 '16 at 19:35
2
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.