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$.
| 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.

0

+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.

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$.
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 ?

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.

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

$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.