finding probability of getting to state $1$ from $0$ in infinite state markov chain

Question

Let $(X_n)$ be iid random variables such that $P(X_n=1)=\frac{1}{6}$, $P(X_n=0)=\frac{1}{3}$, $P(X_n=-1)=\frac{1}{2}$, I want to prove that P(there is an integer $k$ such that $X_1+...+X_k=1$)=$\frac{1}{3}$.

Interpreting this as a Markov chain with states {$1,0,-1,-2,...$} we want the probability of getting to the state $1$ starting at state $0$: p_0, in the general probability of getting to the state $1$ starting at state $n$: $p_n$.

We have the following infinite set of equations:

$p_0=\frac{1}{6}+\frac{1}{3}p_0+\frac{1}{2}p_{-1}$

$p_{-1}=\frac{1}{6}p_0+\frac{1}{3}p_{-1}+\frac{1}{2}p_{-2}$

$p_{-2}=\frac{1}{6}p_{-1}+\frac{1}{3}p_{-2}+\frac{1}{2}p_{-3}$

and in general:

$p_{-k}=\frac{1}{6}p_{-k+1}+\frac{1}{3}p_{-k}+\frac{1}{2}p_{-k-1}$

Solving this in terms of $p_0$ we get that $p_{-k}=p_0+p_0(\frac{1}{3}+...+\frac{1}{3^k})-(\frac{1}{3}+...+\frac{1}{3^k})=\frac{1}{2}(3p_0-1)-(\frac{1}{3})^k (\frac{1}{2}p_0-\frac{1}{2})$

But right now $p_0$ could be arbitrary from $(0,1)$, we need one more equation/information.

$p_{-k}$ is decreasing when $k$ is increasing and it is bounded from below by $0$ so have a limit, can we use it somehow? What can we do to find out that $p_0=\frac{1}{3}$

Answer 1

Method 1

There are two missing pieces of information you need. The first is $$ p_{-1}=p_0^2 $$ Why? In order to start from $-1$ and reach $1$, there needs to be a point where the Markov chain reaches $0$ in between. This is because the chain can only move upwards in increments of $+1$. Therefore, the event of moving $(-1\to 1)$ can be split into two events: moving from $(-1\to 0)$, and then moving from $(0\to 1)$. Furthermore, these two moves are independent, because of the Markov property. The symmetry of the process implies, $P(-1 \to 0)=P(0\to 1)=p_0$, so $P(-1 \to 1)=P(-1\to 0)\cdot P(0\to 1)=p_0^2$.

This equation, combined with $p_0=\tfrac16+\tfrac13p_0+\tfrac12p_{-1}$, gives a quadratic equation involving $p_0$ alone: $$ p_0=\tfrac16 + \tfrac13p_0+\tfrac12 p_0^2 $$ Solving this, we conclude that either $p_0=1/3$ or $p_0=1$. How do we determine which of these is correct?

We can rule out the possibility of $p_0=1$ as follows. Assume that $p_0=1$. This means that starting from $0$, the Markov chain will certainly reach $1$. Once the chain reaches $1$, instead of stopping the process, let us allow the process to continue. Starting from $1$, since $p_0=1$, the chain will certainly move to $2$ (moving $1\to 2$ is equiprobable to moving $0\to 1$). Continuing, the chain will certainly move to $3$, then $4$, and so on, eventually reaching arbitrarily high positive numbers.

Let $S_n=X_1+\dots+X_n$. The strong law of large numbers implies that $S_n/n\to E[X_1]=-1/3$, with probability $1$. This means there exists a number $N$ such that $n>N$ implies $S_n<(-1/3+\epsilon)n$, for any $\epsilon>0$. Since $S_n$ is almost surely eventually negative, it cannot reach arbitrarily high numbers, contradicting the previous paragraph.

Method 2: Martingale convergence

Again, let $S_n=X_1+\dots+X_n$. Define $$ M_n=3^{S_n} $$ You can prove that $M_n$ is a martingale, with respect to the natural filtration. Indeed, $$ \mathbb E[M_{n+1}\mid M_n] = \tfrac16 3^{S_n+1}+\tfrac 13 3^{S_n}+\tfrac 12 3^{S_n-1}=3^{S_n}=M_n. $$ Furthermore, since $-\infty \le S_n\le 1$, we have $0\le M_n\le 3$. Since $M_n$ is bounded, $\lim_{n\to\infty} M_n$ exists with probability $1$, and the expected value of the limiting variable is the same as $E[M_0]$ (Martingale convergence theorem). Letting $M_\infty$ be the limiting variable, we have $$ \mathbb E[M_\infty]=\mathbb E[M_0]=3^0=1 $$ On the other hand, $\lim_{n\to\infty}S_n$ can only be $-\infty$ or $1$, so $\lim_{n\to\infty} M_n$ can only be $0$ or $3$. Therefore, $$ \mathbb E[M_\infty]=p_0\cdot 3+(1-p_0)\cdot 0 $$ Combining the last two equations, you conclude $p_0=1/3$.

Answer 2

I will prove that $\sum_{k} p_{-k}$ converges. Indeed,

\begin{align} p_{-k} &\le \sum_{t=0}^{\infty}\sum_{s=0}^{\infty} \binom{2t+k+1}{t}\binom{2t+s+k+1}{s}\left(\frac16\right)^{t+k+1}\left(\frac12\right)^{t}\left(\frac13\right)^{s}\\ &= \left(\frac16\right)^{k+1}\sum_{t=0}^{\infty}\binom{2t+k+1}{t}\left(\frac1{12}\right)^{t} \sum_{s=0}^{\infty} \binom{2t+k+1+s}{s} \left(\frac1{3}\right)^s\\ &= \left(\frac16\right)^{k+1}\sum_{t=0}^{\infty}\binom{2t+k+1}{t}\left(\frac1{12}\right)^{t}\frac1{\left(1 - \frac13\right)^{2t+k+2}}\\ &= \left(\frac16\right)^{k+1}\sum_{t=0}^{\infty}\binom{2t+k+1}{t}\left(\frac1{12}\right)^{t}\frac1{\left( \frac23\right)^{2t+k+2}}\\ &= \left(\frac16\right)^{k+1}\left(\frac32\right)^{k+2}\sum_{t=0}^{\infty}\binom{2t+k+1}{t}\left(\frac{3}{16}\right)^{t}\\ &= \frac32 \left(\frac14\right)^{k+1}\frac1{\sqrt{1 - 4\times \frac{3}{16}}} \left(\frac{1-\sqrt{1-4\times\frac{3}{16}}}{2\times \frac{3}{16}}\right)^{k+1}\\ &= \frac32\times 2 \times \left(\frac14\right)^{k+1} \left(\frac{4}{3}\right)^{k+1}\\ &= 3\times\left(\frac13\right)^{k+1} = \left(\frac13\right)^{k} \end{align}

This proves that the series $\sum_{k}p_{-k}$ converges and so $$\lim_{k\to \infty} p_{-k} = 0.$$

Answer 3

Suppose we have state space $\mathbb{Z}$, and state transitions $s\mapsto t$ with probabilities given by \begin{align*} P(t=s-1)&=\,\frac{1}{2}\\[4pt] P(t=s)&=\,\frac{1}{3}\\[4pt] P(t=s+1)&=\,\frac{1}{6}\\[4pt] \end{align*} For integers $a,b,c$ with $a < b < c$, let $X(a,b,c)$ be the event that state $c$ is reached before state $a$, starting with state $b$.

In a conceptually similar way, for integers $b,c$ with $b < c$, let $X(-\infty,b,c)$ be the event that state $c$ is eventually reached, starting with state $b$.

Let $p(a,b,c)=P\bigl(X(a,b,c)\bigr)$ and let $p(-\infty,b,c)=P\bigl(X(-\infty,b,c)\bigr)$.

Note that by physical symmetry we have $p(a-1,b-1,c-1)=p(a,b,c)$.

Claim:$\;p(-\infty,0,1)={\large{\frac{1}{3}}}$.

Proof:

For each positive integer $n$, let $v_n=p(-n,0,1)$.

We proceed to show, by induction on $n$, that $$ v_n=\frac{3^n-1}{3^{n+1}-1} $$ holds for all positive integers $n$.

For $n=1$ we have \begin{align*} & p(-1,0,1)=\frac{1}{6}+\frac{1}{3}p(-1,0,1) \\[4pt] \implies\;& v_1=\frac{1}{6}+\frac{1}{3}v_1 \\[4pt] \implies\;& v_1=\frac{1}{4} \\[4pt] & {\phantom{v_1}} =\frac{3^1-1}{3^2-1} \\[4pt] \end{align*} so the base case $n=1$ is verified.

For the inductive step, assume that $$ v_n=\frac{3^n-1}{3^{n+1}-1} $$ holds for some positive integer $n$.

Then we get \begin{align*} & p(-n-1,0,1)=\frac{1}{4}+\frac{3}{4}p(-n-1,-1,0)p(-n-1,0,1) \\[4pt] \implies\;& p(-n-1,0,1)=\frac{1}{4}+\frac{3}{4}p(-n,0,1)p(-n-1,0,1) \\[4pt] & \qquad \Bigl(\, \text{since $p(-n-1,-1,0)=p(-n,0,1)$} \,\Bigr) \\[4pt] \implies\;& v_{n+1}=\frac{1}{4}+\frac{3}{4}v_nv_{n+1} \\[4pt] \implies\;& v_{n+1}=\frac{1}{4-3v_n} \\[4pt] & {\phantom{v_{n+1}}} = \frac {1} { 4 - 3 \Bigl( {\large{\frac{3^n-1}{3^{n+1}-1}}} \Bigr) } \\[4pt] & {\phantom{v_{n+1}}} = \frac {1} { 4 - 3 \Bigl( {\large{\frac{3^n-1}{3^{n+1}-1}}} \Bigr) } \cdot \frac {3^{n+1}-1} {3^{n+1}-1} \\[4pt] & {\phantom{v_{n+1}}} = \frac {3^{n+1}-1} { 4(3^{n+1}-1) - 3(3^n-1) } \\[4pt] & {\phantom{v_{n+1}}} = \frac {3^{n+1}-1} { (4{\,\cdot\,}3^{n+1}-4) - (3^{n+1}-3) } \\[4pt] & {\phantom{v_{n+1}}} = \frac {3^{n+1}-1} { 3{\,\cdot\,}3^{n+1}-1 } \\[4pt] & {\phantom{v_{n+1}}} = \frac {3^{n+1}-1} {3^{n+2}-1} \\[4pt] \end{align*} which completes the induction.

Then we get \begin{align*} p(-\infty,0,1) &= P\Bigl(\bigcup_{n=1}^\infty X(-n,0,1)\Bigr) \\[4pt] &= \lim_{n\to\infty} P\Bigl(X(-n,0,1)\Bigr) \\[4pt] &\qquad \Bigl(\, \text{since}\; X(-1,0,1) \subset X(-2,0,1) \subset X(-3,0,1) \subset \cdots \,\Bigr) \\[4pt] &= \lim_{n\to\infty} v_n \\[4pt] &= \lim_{n\to\infty} \frac{3^n-1}{3^{n+1}-1} \\[4pt] &= \lim_{n\to\infty} \frac{3^n-1}{3^{n+1}-1} \cdot \frac{3^{-n}}{3^{-n}} \\[4pt] &= \lim_{n\to\infty} \frac{1-3^{-n}}{3-3^{-n}} \\[4pt] &= \frac{1-0}{3-0} \\[4pt] &= \frac{1}{3} \\[4pt] \end{align*} as was to be shown.