632 views
0 votes
0 votes
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

1 Answer

0 votes
0 votes

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.



 

Related questions

1 votes
1 votes
1 answer
2
Ray Tomlinson asked Sep 23, 2023
380 views
how to approach passage reading question because maximum time i am geting wrong answer while practising questions for go pyq ? how should practicse these questions
2 votes
2 votes
0 answers
3
h4kr asked Dec 21, 2022
301 views
0 votes
0 votes
1 answer
4
sumit goyal 1 asked Sep 7, 2018
191 views
If $2 sin\alpha + 15 cos \alpha = 7$ find $cot \alpha$ ?