# Random walk by a monkey

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.

• What do you mean by ' I don't know how to find answer to specific k'? – Tojrah Mar 25 at 15:35
• 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)!$ – user601297 Mar 25 at 15:37

## 1 Answer

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.

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