retagged by
2,283 views
10 votes
10 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$?

  1. It will never reach the top.
  2. Linear in $n$.
  3. Polynomial in $n$.
  4. Exponential in $n$.
  5. Double exponential in $n$.
retagged by

6 Answers

0 votes
0 votes
E(X)= $\sum$ P(Xi)*i

When it is at bottom it has only one chance that is going up : 0*(1/3) . Otherwise for every step it has 2 option either to move up or to move down.

E(X) = 0*(1/3) + 1*(1/3) + 1*(2/3) + 2*(1/3) + 2*(2/3) + ...... (n-1)*(1/3) + (n-1)*(2/3)

        =  (1+2+3 ..... (n-1) ) * (1/3) + (1+2+4......(n-1)*(2/3)

        =  n(n-1)/2

Therefore E(X) is O(n^2) .

I am getting option C.

@Arjun Sir plz check if possible .

 

I am getting option C.
0 votes
0 votes

$1^{st}$ step is taken with probability $=1$ i.e. it will go $1$ step closer  to cliff so now it need to take $n-1$ inches more.

For remaining $n-1$ inches,

suppose he takes $k$ steps and $l$ steps to move forward and backwards respectively and by taking $k+l$ steps he reaches at the top. $(k>l)$

since in each step he covers $\pm1$ inch so in $k+l$ steps he covers $n-1$ inches.

i.e. $k+l = n-1$

$step$ $+1$ $-1$
$P(step)$ $1/3$ $2/3$

so we can say that he takes $k$ steps with probability $1/3$ and $l$ steps with probability $2/3$ to cover the distance of $n-1$ inches. (also he has already covered $+1$ step with probability $1$)

$E(step)=1.1+ 1. (\frac{1}{3})^k -1. (\frac{2}{3})^l $

$\implies E(step)=1+  \frac{1}{3} +  \frac{1}{3} +  \frac{1}{3} +   \frac{1}{3} + ...k\ times - \frac{2}{3} - \frac{2}{3} -\frac{2}{3} -\frac{2}{3} -\frac{2}{3} ....l \ times$

$\implies E(step)=1+  ( \frac{1}{3} -\frac{2}{3}) +  ( \frac{1}{3} -\frac{2}{3}) + ( \frac{1}{3} -\frac{2}{3}) +...l \ times +  \frac{1}{3} +  \frac{1}{3} +   \frac{1}{3} + ...(k-l)\ times$

$\implies E(step)=1-  ( \frac{1}{3} ) -  ( \frac{1}{3}) - ( \frac{1}{3}) +...l \ times +  \frac{1}{3} +  \frac{1}{3} +   \frac{1}{3} + ...(k-l)\ times$

$\implies  E(step)= 1-  (\frac{1}{3})^l +(\frac{1}{3})^{k-l} $

$\implies  E(step)= 1-  (\frac{1}{3})^{(n-1-k)} +(\frac{1}{3})^{k-(n-1-k)} $

$\implies  E(step)= 1-  (\frac{1}{3})^{-(k-n+1)} +(\frac{1}{3})^{2k-n+1} $

$\implies  E(step)= 1-  (3)^{(k-n+1)} +(3)^{-2k+n-1} $

So option $d.$ is correct.

 

edited by
Answer:

Related questions

23 votes
23 votes
5 answers
1
13 votes
13 votes
2 answers
3
makhdoom ghaya asked Oct 26, 2015
1,695 views
The probability of throwing six perfect dices and getting six different faces is$1 -\dfrac{ 6!} { 6^{6}}$$\dfrac{6! }{ 6^{6}}$$6^{-6}$$1 - 6^{-6}$None of the above