# Probability problem to solve with Markov Chain

I have the following problem.

We have $$N$$ steps and one variable $$Y$$, whose initial value is $$Y_0=2$$. We start from $$Y_0=2$$, and at every step, there is a probability of $$1/2$$ that $$Y$$ increases or decreases by 2. What is the probability that the state $$Y=0$$ is never visited within $$N$$ steps?

I want to approach this problem by using Markov Chains. In particular, I call $$p(k,n)$$ the probability that we never reach $$Y=0$$ if we are on the state $$Y=k$$ at the $$n-th$$ step. Therefore, we have the following recursion relation

$$p(k,n) = \frac{1}{2}p(k-2,n+1) + \frac{1}{2}p(k+2,n+1)$$

with the boundary condition $$p(0,n) = 0$$. Is this the right way to approch this problem in terms of a Markov Chain? How do I get a closed form expression of the probability?

• You could work backwards and compute $p(k, N), p(k, N-1), p(k, N-2), \ldots$ for each $k$? Mar 10 at 20:13
• Why do you have the steps incremented by $2$? Wouldn't it be the same to start at $1$ and have the increments equal to $\pm 1$?
– lulu
Mar 10 at 20:18
• @lulu yes it would be the same, it's just a matter of normalization Mar 10 at 20:31
• @angryavian yes, I can work backwards, but I don't know if that's the smartest thing to do Mar 10 at 20:32
• Just seems to complicate things, having all those unnecessary factors of $2$ everywhere.
– lulu
Mar 10 at 20:32

Not an approach with states/markov chains

First normalize everything to steps of $$1$$. Second assume $$N$$ is odd i.e. $$N=2n+1$$ (if $$N$$ is even, then the probability is the same as the probability for $$N-1$$).

Let's consider the number of paths such that it reaches $$0$$ for the first time after exactly $$2k+1$$ steps. It must reach $$1$$ after $$2k$$ steps but never go below $$1$$ before that and then go to $$0$$ on the last step. The number of such sequences of steps such that it reaches $$1$$ after exactly $$2k$$ steps (but never goes below) is $$C_k$$, the $$k$$th catalan number. So the probability of this event occurring is $$\frac{C_k}{2^{2k+1}}$$.

Hence, the probability that we reach $$0$$ at least once is $$\sum_{k=0}^n \frac{C_k}{2^{2k+1}}$$ Note that $$\frac{C_k}{2^{2k+1}}$$ is the coefficient of $$x^k$$ in the expansion of $$\frac{1-\sqrt{1-x}}{x}$$ So $$\sum_{k=0}^n \frac{C_k}{2^{2k+1}}$$ is the coefficient of $$x^n$$ in the expansion of $$\frac{1-\sqrt{1-x}}{x(1-x)}$$ $$=\frac{(1-x)^{-1}-(1-x)^{-1/2}}{x}$$ Note that $$(1-x)^{-1}=\sum_{k=0}^\infty x^n$$ and $$(1-x)^{-1/2}=\sum_{k=0}^\infty \binom{2n}{n}\frac{1}{4^n}x^n$$.

So the probability that we reach $$0$$ within $$2n+1$$ steps is $$1-\frac{1}{4^{n+1}}\binom{2n+2}{n+1}$$, hence the probability that we never reach $$0$$ is $$\frac{1}{4^{n+1}}\binom{2n+2}{n+1}$$. Looking at the asymptotic growth of central binomial coefficients, this indeed approaches $$0$$ as expected.