How to approach?

Question

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?

a)Never reach to the top

b)Linear to n

c)Polynomial to n

d)Exponential to n

Comments

Any reference?

---

why is it -1??

---

@Debashish Deka , @Arjun sir can u help on this question ??

Answer 1

T(n) represents number of steps taken in order to cross "n" inches
T(n)= 1 + T(n-1) ; // Since at the bottom probability of getting closer is 1.
T(n-1) = 1/3(1+ T(n-2)) + 2/3(1 + T(n)); // since now probability of getting closer is 1/3 and away is 2/3.
Substituting T(n); we get'
T(n-1) = 5/3 + (T(n-2))/3 + 2/3(T(n-1)); 
=> T(n-1)= 5 + T(n-2);
Back substituting T(n-1) into T(n) , we get,
T(n)= T(n-2) + 5 +1;
Similarly,
T(n-2) = 1/3(1+T(n-3)) + 2/3(1 + T(n-1));
Substituting value of T(n-1),we get,
T(n-2)= 13 + T(n-3);
Back substituting T(n-2) in T(n), we get,
T(n) = T(n-3) + 13 + 5 + 1;
Similarly 
T(n) = T(n-4) + 29 + 13 + 5 +1
If we make a observation then, above equation can be re-written as 
T(n)= T(n-4) + (2^(4+1)-3) + (2^4-3) + (2^3-3) + (2^2-3);
OR
T(n)= T(n-4) +(2^(4+1)) + (2^4) + (2^3) + (2^2) - 4*3
Generalizing above recurrence now, we get,
T(n) = T(n-k) + (2^(k+1)) + (2^k) + (2^(k-1)) +-----------+(2^3) + (2^2) - k*3
Adding 3 and subtracting 3 to make it a complete GP, we get,
T(n) = T(n-k) + (2^(k+1)) + (2^k) + (2^(k-1)) +-----------+(2^3) + (2^2) +(2^1)+(2^0) -3- k*3
Solving GP,we get,
T(n) = T(n-k) + 2^(k+2) -1 -3(1+k);
Now we use anchor condition; which is T(0)=0 , obviously.
putting n-k = 0,we get
T(n)= T(0) + 2^(n+2) - 3(1+n) - 1 ;  since n-k=0 => n=k;
Thus T(n) = 2^(n+2) -4 - 3n 
Or  T(n) = 4.2^n - 4 -3n => T(n) = 4(2^n-1) - 3n.
Thus answer is exponential to n.