A monkey is sitting on $0$ on $\mathbb{R}$, at $t = 0$ . In every period $t\in({1,2,\dots})$ it moves one unit to the right with probability $p$ and one unit to the left with probability $1-p$. Let $P_k$ denote the probability that the monkey will reach positive integer $k$ in some period $t>0$. Find the value of $P_k$ for any positive integer $k$.

My attempt-

Let there be $R$ right and $L$ left steps, then, $$L+R = t$$ The position at $t>0$ is $$R-L = R-(t-R) = 2R-t$$

Now, $$R\sim Bin(t,p)$$ Then, if $X=k$ is the position at time $t>0$ it implies that $2R-t =k $ or $R = \frac{k+t}{2}$

So, $$P_k = {t \choose \frac{k+t}{2}}p^\frac{k+t}{2}(1-p)^\frac{t-k}{2}$$

But I don’t know how to find the answer for a specific $k$, like the question asks me to find $P_0$ when $p =\frac{1}{2}$, can somebody help me out with this.

Also if there is another way to do this question without using markov chain please let me know.

I also tried conditioning on the first step to do something similar to finding the solution to gambler’s ruin but couldn’t work that out.

  • $\begingroup$ What do you mean by ' I don't know how to find answer to specific k'? $\endgroup$ – Tojrah Mar 25 at 15:35
  • $\begingroup$ The answer given to me says that $P_k$ is always 1 I don’t get how that is, also how do i deal with$(t/2)!$ $\endgroup$ – user601297 Mar 25 at 15:37

Note that if $p\geq\frac12$, $P_k=1$ for all $k$. So, we are more interested in the cases when $p<\frac12$.

Now when $p<\frac12$, we set up our problem as follows: Let $P_{kj}$ be the probability that, given a random walk with $p<\frac12$, the monkey reaches $k$ before reaching $j$, where $j<0$. If we can find $P_{kj}$ for arbitrary $j$, then $P_k=\lim_{j\to-\infty}P_{kj}$.

For computing $P_{kj}$, I think that using a Markov chain to set up equations is probably the best way to go.

  • $\begingroup$ Can you tell me why if $p>1/2$ we have $P_k=1$ for all k, I don’t understand why this is $\endgroup$ – user601297 Mar 25 at 17:42
  • $\begingroup$ Because, on average, it should be moving to the right. As such, it should eventually reach all numbers to the right of the origin. $\endgroup$ – Don Thousand Mar 25 at 17:48
  • $\begingroup$ Ok got it, thanks a lot $\endgroup$ – user601297 Mar 25 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.