retagged by
2,279 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

2 votes
2 votes

This can be modelled as a binomial random variable (Bernoulli trials) where the probability of success for a trial is $\frac{1}{3}$ and that of failure is $\frac{2}{3}$.
 

The expectation of this binomial random variable is given as $E[X] = \sum_{x = 0}^{n}x . ^{n}C_{x}(1/3)^x(2/3)^{n - x}$.

This is exponential in $n$ due to the $(2/3)^{n - x}$ term.

Ref: http://www.math.ubc.ca/~feldman/m302/binomial.pdf

1 votes
1 votes
It will be linear to n

It will go (n-1) inches in (n-1)*3 steps

last 1 inch goes in 1 step

so total (n-1)*3+1 steps
1 votes
1 votes
For a cliff of height n, minimum number of steps required by the spider is n. Let $S$ be the random variable that denotes the number of steps taken by the spider to climb the cliff. $P(S = n) = {(\frac{1}{3})}^n$.

Now lets say that while climbing, the spider slips down one inch. Now it will require n+1 steps to reach the top. $P(S = n+1) = {(\frac{1}{3})}^{n+1}(\frac{2}{3})$. To generalize, suppose the spider slips down k steps (in any order) while climbing the cliff. $P(S = n+k) = {(\frac{1}{3})}^{n+k}{(\frac{2}{3})}^k$

$E(S) = n{(\frac{1}{3})}^n + (n+1){(\frac{1}{3})}^{n+1}(\frac{2}{3}) + (n+2){(\frac{1}{3})}^{n+2}{(\frac{2}{3})}^2 + ….$    ---(1)   (Infinite AGP series)

Here $r = \frac{1}{3}*\frac{2}{3}$. Multiplying $E(S)$ by r, we get

$E(S).\frac{1}{3}.\frac{2}{3} = n{(\frac{1}{3})}^{n+1}(\frac{2}{3}) + (n+1){(\frac{1}{3})}^{n+2}{(\frac{2}{3})}^2 + …..$  --- (2)

Subtracting (2) from (1), we get

$\frac{7}{9}E(S) = n{(\frac{1}{3})}^n + {(\frac{1}{3})}^{n+1}(\frac{2}{3}) + {(\frac{1}{3})}^{n+2}{(\frac{2}{3})}^2 + …..$

 $=n{(\frac{1}{3})}^n + {(\frac{1}{3})}^{n+1}(\frac{2}{3})[1 + {(\frac{1}{3})}{(\frac{2}{3})} + {(\frac{1}{3})}^2{(\frac{2}{3})}^2 +  …..]$

$ = n{(\frac{1}{3})}^n + {(\frac{1}{3})}^{n+1}(\frac{2}{3})(\frac{1}{1 – (\frac{1}{3}).(\frac{2}{3})})$

$\therefore\frac{7}{9}E(S) = n{(\frac{1}{3})}^n + {(\frac{1}{3})}^{n+1}(\frac{2}{3})(\frac{9}{7})$

$\therefore E(S) = \frac{9}{7}(n{(\frac{1}{3})}^n + {(\frac{1}{3})}^{n+1}(\frac{2}{3})(\frac{9}{7}))$

Can be simplified further but we can see that expected number of steps is exponential in n

Option D
0 votes
0 votes

Let this be a bernoulli distribution in which the indicator random variable is Xi={ 1 if step is taken in the front direction and 0 otherwise.

We know that in Bernoulli Distribution, E(Xi) = P( step is taken in the front direction) = 1/3

Similarly let there be a bernoulli distribution in which the indicator random variable is Yi={ 1 if step is taken in the backward direction and 0 otherwise. Hence E(Yi) = 2/3.
 

Now according to linearity E(Xi+Yi) = E(Xi) + E(Yi) even if Xi and Yi are dependent variables.

If total number of front steps be z+n, then total number of back steps are z.

E(X + Y) = (z+n)*E(Xi) + z*E(Yi)
or, E(X + Y) = 1/3*(z+n) + 2/3*z = $\frac{3z + n}{3}$

hence the equation is linear in terms of n.

Answer:

Related questions

23 votes
23 votes
5 answers
1
13 votes
13 votes
2 answers
3
makhdoom ghaya asked Oct 26, 2015
1,691 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