1
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ You could work backwards and compute $p(k, N), p(k, N-1), p(k, N-2), \ldots$ for each $k$? $\endgroup$
    – angryavian
    Mar 10 at 20:13
  • $\begingroup$ 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$? $\endgroup$
    – lulu
    Mar 10 at 20:18
  • $\begingroup$ @lulu yes it would be the same, it's just a matter of normalization $\endgroup$
    – apt45
    Mar 10 at 20:31
  • $\begingroup$ @angryavian yes, I can work backwards, but I don't know if that's the smartest thing to do $\endgroup$
    – apt45
    Mar 10 at 20:32
  • $\begingroup$ Just seems to complicate things, having all those unnecessary factors of $2$ everywhere. $\endgroup$
    – lulu
    Mar 10 at 20:32

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.