(a) Consider a Markov chain on a countable state space 𝕊 with transition probabilities $p_{i,j},i,j∈𝕊$.
(i) Define the notions of irreducibility, aperiodicity and invariant distribution.
(ii) State, without proof, the convergence theorem and the ergodic theorem.
(b) For $a,b∈(0,1)$, consider a Markov chain $\left(X_n,n≥0\right)$ on $\{-1,1\}$ with $X_0=1$ and transition probabilities $p_{-1,1}=1-p_{-1,-1}=a$ and $p_{1,-1}=1-p_{1,1}=b$. Show that \[ ℙ\left(X_n=1\right)→\frac{a}{a+b} \text { as }n→∞ . \] (c) Consider a Markov chain $\left(X_n,n≥0\right)$ on $\{-4,-3,-2,-1,0,1,2,3,4\}$ with $X_0=0$ and transition matrix \[ P=\left(p_{i,j}\right)_{-4≤i,j≤4}=\pmatrix{ 1/2&0&0&0&0&0&0&0&1/2\\ 0&2/3&0&0&0&0&0&1/3&0\\ 0&0&0&0&0&0&1&0&0\\ 0&0&0&1&0&0&0&0&0\\ 2/9&0&1/9&0&0&1/3&0&1/3&0\\ 0&1/3&1/3&0&0&0&0&0&1/3\\ 0&0&1&0&0&0&0&0&0\\ 0&1/6&0&0&0&0&0&5/6&0\\ 1/2&0&0&0&0&0&0&0&1/2} \] so that $ℙ\left(X_1=-4\right)=2/9$.
(i) Find the communicating classes of this Markov chain.
(ii) Find all stationary distributions of this Markov chain.
(iii) Show that $ℙ\left(X_n=4\right)→1/6$ as $n→∞$.
(iv) Does $ℙ\left(X_n=j\right)$ converge for all $j∈𝕊$ as $n→∞$ ? Justify your answer.
(v) how that the long-term proportion spent in state 2 converges almost surely, and determine the limit.
(a) (i) The Markov chain is irreducible if for all $i,j∈𝕊$ there is a path $i=i_0,i_1,…,i_{m-1},i_m=j$ in 𝕊 from $i$ to $j$ with $\prod_{1≤k≤m}p_{i_{k-1},i_k}>0$.(i) Define the notions of irreducibility, aperiodicity and invariant distribution.
(ii) State, without proof, the convergence theorem and the ergodic theorem.
(b) For $a,b∈(0,1)$, consider a Markov chain $\left(X_n,n≥0\right)$ on $\{-1,1\}$ with $X_0=1$ and transition probabilities $p_{-1,1}=1-p_{-1,-1}=a$ and $p_{1,-1}=1-p_{1,1}=b$. Show that \[ ℙ\left(X_n=1\right)→\frac{a}{a+b} \text { as }n→∞ . \] (c) Consider a Markov chain $\left(X_n,n≥0\right)$ on $\{-4,-3,-2,-1,0,1,2,3,4\}$ with $X_0=0$ and transition matrix \[ P=\left(p_{i,j}\right)_{-4≤i,j≤4}=\pmatrix{ 1/2&0&0&0&0&0&0&0&1/2\\ 0&2/3&0&0&0&0&0&1/3&0\\ 0&0&0&0&0&0&1&0&0\\ 0&0&0&1&0&0&0&0&0\\ 2/9&0&1/9&0&0&1/3&0&1/3&0\\ 0&1/3&1/3&0&0&0&0&0&1/3\\ 0&0&1&0&0&0&0&0&0\\ 0&1/6&0&0&0&0&0&5/6&0\\ 1/2&0&0&0&0&0&0&0&1/2} \] so that $ℙ\left(X_1=-4\right)=2/9$.
(i) Find the communicating classes of this Markov chain.
(ii) Find all stationary distributions of this Markov chain.
(iii) Show that $ℙ\left(X_n=4\right)→1/6$ as $n→∞$.
(iv) Does $ℙ\left(X_n=j\right)$ converge for all $j∈𝕊$ as $n→∞$ ? Justify your answer.
(v) how that the long-term proportion spent in state 2 converges almost surely, and determine the limit.
The Markov chain is aperiodic if $\operatorname{hcf}\left\{m≥1:p_{i,i}^{(m)}>0\right\}=1$ for all $i∈𝕊$, where $P^m=\left(p_{i,j}^{(m)}\right)_{i,j∈𝕊}$ is the $m$-step transition matrix.
A distribution $π=\left(π_i\right)_{i∈𝕊}$ on 𝕊 is invariant if $π P=π$.
(ii) If the Markov chain $\left(X_n,n≥0\right)$ is irreducible, aperiodic and has invariant distribution $π$, then for all $i,j∈𝕊$, we have $ℙ_i\left(X_n=j\right)→π_j$ as $n→∞$.
If the Markov chain is irreducible with invariant distribution $π$, then for all $i,j∈𝕊$ \[ ℙ_i\left(\frac{\#\left\{k=1,…,n:X_k=j\right\}}{n}→π_j\right)=1 . \] (b) This is a standard example.
This Markov chain is irreducible and aperiodic. We check that \[ \left(\frac{b}{a+b},\frac{a}{a+b}\right)\left(\begin{array}{cc} 1-a&a\\ b&1-b \end{array}\right)=\left(\frac{b}{a+b},\frac{a}{a+b}\right). \] By the convergence theorem, $ℙ\left(X_n=1\right)→a/(a+b)$, as $n→∞$.
(c) (i) $\{-4,4\},\{-3,3\},\{-2,2\},\{-1\},\{0\},\{1\}$.
(ii) Only the first four classes are closed, each with a unique stationary distribution obtained as in (b) and given by \begin{aligned} &π^{(4)}=(1/2,0,0,0,0,0,0,0,1/2) \\ &π^{(3)}=(0,1/3,0,0,0,0,0,2/3,0) \\ &π^{(2)}=(0,0,1/2,0,0,0,1/2,0,0) \\ &π^{(1)}=(0,0,0,1,0,0,0,0,0) . \end{aligned} So, $\sum_{1≤k≤4}a_k π^{(k)}$ for $a_k≥0$ with $\sum_{1≤k≤4}a_k=1$ are all stationary distributions.
(iii) The convergence theorem applies on the aperiodic closed class $\{-4,4\}$ with stationary distribution $π^{(4)}$. Also, starting from $-3,-2,-1,2,3$ there is zero probability to visit 4 . Partition according to $A_1=\left\{X_1=-4\right\},A_2=\left\{X_1=-2\right\}$, $A_3=\left\{X_1=3\right\},A_4=\left\{X_1=1,X_2=-3\right\},A_5=\left\{X_1=1,X_2=2\right\}$ and $A_6=\left\{X_1=1,X_2=4\right\}$ and apply the Markov property to find (for $n≥2$ ) \begin{aligned} ℙ\left(X_n=4\right)=\sum_{k=1}^6 ℙ\left(A_k\right) ℙ\left(X_n=4 \mid A_k\right) &=\frac{2}{9} ℙ_{-4}\left(X_{n-1}=4\right)+\frac{1}{3} \frac{1}{3} ℙ_4\left(X_{n-2}=4\right) \\ &→\frac{2}{9} \frac{1}{2}+\frac{1}{9} \frac{1}{2}=\frac{1}{6} . \end{aligned} (iv) Convergence of $ℙ\left(X_n=j\right)$ follows as in (iii) for $j∈\{-4,-3,-1,0,1,3,4\}$. For $j=2$, we note similarly that \[ ℙ\left(X_n=2\right)=\frac{1}{9}ℙ_{-2}\left(X_{n-1}=2\right)+\frac{1}{3}\frac{1}{3}ℙ_{-2}\left(X_{n-2}=2\right)=\frac{1}{9}, \] since for odd $n$ the first probability vanishes while the second equals one, while for even $n$ the opposite is true. In particular, $ℙ\left(X_n=2\right)$ converges. The same argument establishes the convergence of $ℙ\left(X_n=-2\right)$.
(v) The ergodic theorem applies on $\{-2,2\}$. From the above, this class is visited with probability $4/9$ and on this event $A$, the proportion tends to $1/2$, while on the complementary event, it vanishes. Hence, we get a.s. convergence to $\frac{1}{2}1_A$.
PREVIOUSProbability paper2019