The Gateway to Computer Science Excellence
+6 votes
771 views

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$.
in Probability by Boss | 771 views
0

@Arjun sir, Can you please see my approach to solve this question, 

I know, (n-1)Cr term needs some modification because, I have assumed consecutive fall down.

But, I think, Its should be option a) It will never reach the top. because probability of going up is less than falling down. 

Please help me ?

5 Answers

+1 vote

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

by Active
0
I seem to have made a mistake. I guess we need to find the closed form of the summation, if there is one, before we can decide that $E[X]$ is exponential in $n$.
0 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
by Veteran
0
you have to use expectation formula..
+3
@Arjun, can you please solve this question ?
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.

by
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.
by Loyal
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.

 

by Boss
edited by
0

@Arjun Sir , please check it.

0
Expectation is basically counting of a term - number of steps here. You are only involving probability in your calculation which is wrong. Also, is $1/3^n$ exponential in $n$?
0

@Arjun Sir , I didn't understood.

the expected value of a discrete random variable is the probability-weighted average of all its possible values , i am also taking step as +1 and -1 along with probability.

$3^n$ is exponential since exponential function since it is  $f(x) = a^x$ form.

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,923 answers
201,115 comments
118,162 users