Probability problem to solve with Markov Chain

Question

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?

Answer 1

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.