Example 8.3.1. Consider a gambler who at each play of the game either wins \(1\) unit with probability \(P\) or loses \(1\) unit with probability \(1-P\). If we suppose that the gambler will stop playing when his fortune hits either \(0\) or \(m\), then the
gambler’s sequence of fortunes is a Markov chain having transition
probabilities.

\[P_{i,i+1}=P,\hspace {0.3cm} P_{i,i-1}=1-P,\hspace {0.3cm} i=1,2,........, m-1.\] \[P_{00}=1,\hspace {0.5cm} P_{mm}=1\]
\[ \begin {bmatrix} 1&0&0&0&0&0&0\\ 1-P&0&P&0&0&0&0\\ 0&1-P&0&P&0&0&0\\ 0&0&1-P&0&P&0&0\\ 0&0&0&1-P&0&P&0\\ 0&0&0&0&1-P&0&P\\ 0&0&0&0&0&0&1\\ \end {bmatrix} \]
\[P_{ij}=P\{X_{n+1}=j/X_n=i\}\]

\[P^{(2)}_{ij}=P\{X_{n+1}=j/X_n=i\}=\text {the system in state}\hspace {0.2cm}i\hspace {0.2cm}\text {will be in state}\hspace {0.2cm} j\hspace {0.2cm}\text {after two transitions.}\]
We want to compute \(P^{(2)}_{ij}!\) \[P^{(2)}_{3,4}=P\{X_{n+2}=4/X_n=3\}=0\] \begin {align*} P^{(2)}_{ij} &=P\{X_{n+2}=j/X_n=i\}\\ &=P\{X_2=j/X_0=i\}\\ &=\sum ^m_{k=0}P\{X_2=j/X_1=k,X_0=i\}\hspace {0.1cm}P\{X_1=k/X_0=i\}\\ &=\sum ^m_{k=0}P\{X_2=j/X_1=k\}\hspace {0.1cm}P\{X_1=k/X_0=i\}\\ &=\sum ^m_{k=0}P_{kj}P_{ik} =\sum ^m_{k=0}P_{ik}\hspace {0.1cm}P_{kj}\\\\ \implies \hspace {0.5cm}P^{(2)}_{ij} &=\sum ^m_{k=0}P_{ik}P_{kj}\\ \end {align*}

\begin {align*} P^{(2)}_{3,5} &=\sum ^6_{k=0}P_{3k}P_{k5}\\ &=P_{30}P_{05}+P_{31}P_{15}+P_{32}P_{25}+.....\\ &=P^2 \end {align*}

\[P^{(2)}_{34}=\sum ^6_{k=0}P_{3k}P_{k4}=0.\]
In general, we can define \(n\)-stage transition probabilities, denoted by \(P^{(n)}_{ij}\) and is given by \[P^{(n)}_{ij}=P\{X_{n+l}=j/X_l=i\}=P\{X_n=j/X_0=i\}\]

Example 8.3.3 (Random Walk). Tracking a particle as it moves along one-dimensional axis. Suppose that at each point in time the particle will move either one-step to the right or one-step to the left with probabilities \(P\) and \(1-P\) respectively.
The particles path follows a Markov chain with transition probabilities \[P_{i,i+1}=P\hspace {0.4cm} \text {and}\hspace {0.4cm} P_{i,i-1}=1-P,\hspace {1cm} i=0,\pm 1,\pm 2,\pm 3..........\] If the particle is in state \(i\), then the probability that it will be in state \(j\) after \[n\hspace {0.3cm}\text { transitions is that}\hspace {0.3cm} \frac {n-i+j}{2}\hspace {0.3cm}\text { steps are to the right and}\] \[n-\frac {(n-i+j)}{2}=\frac {n+i-j}{2}\hspace {0.4cm}\text {are to the left.}\] \[P^{(n)}_{ij}= \begin {pmatrix} n\\\\\frac {n-i+j}{2}\\ \end {pmatrix} P^{\frac {n-i+j}{2}}(1-P)^{\frac {n+i-j}{2}}\hspace {0.2cm}............\hspace {0.2cm} (*) \] where \( \begin {pmatrix} n\\x\\ \end {pmatrix} =0\) if \(x\) is not a non-negative integer less than or equal to \(n\)

\(*\) can be written as \begin {align*} P^{(2n)}_{i,i+2k} &= \begin {pmatrix} 2n\\\\ n+k\\ \end {pmatrix} P^{n+k}(1-P)^{n-k},\hspace {0.5cm} k=0, \pm 1, \pm 2,........,\pm n\\\\ P^{(2n+1)}_{i,i+2k+1} &= \begin {pmatrix} 2n+1\\\\n+k+1\\ \end {pmatrix} P^{n+k+1}(1-P)^{n-k},\hspace {0.5cm} k=0, \pm 1, \pm 2,.........,\pm n.\\\\ P\{X_n=j\} &=\sum ^n_{i=1}P(X_n=j \mid X_0=i)P(X_0=i)\\ &=\sum _i P^{(n)}_{ij} P(X_0=i) \end {align*}

\(P^{(n)}_{ij}\) converges as \(n\longrightarrow \infty \) to the value \(\pi _j\) that depends only on \(j\). That is for large values of \(n\) the probability of being in state \(j\) after \(n\) transitions is approximately equal to \(\pi _j\) regardless of the initial state it was.

It can be shown that a sufficient condition for a Markov chain to posses this property is that \(n>0\), \[P^{(n)}_{ij}>0,\hspace {0.3cm}\text {for}\hspace {0.3cm} i,j=0,1,2,.........., m\hspace {0.2cm}........(**)\] A Markov chain that satisfy \((**)\) are said to be ergodic chains.

Comments:
Transition functions and initial distributions.
Let \(\{X_n\}\), \(n\geq 0\) be a Markov chain having state space \(\mathbf {E}\).

1.

The function \(P_{ij}\), \(i\in \mathbf {E}\) and \(j\in \mathbf {E}\) defined by \(P_{ij}=P\{X_1=j/X_0=j\},\hspace {0.5cm} i,j\in \mathbf {E}\hspace {0.2cm}\) is called the transition function of the Markov chain. It is such that \(P_{ij}\geq 0\) and \(\sum \limits ^m_{j=1}P_{ij}=1\).

2.

The function \(\pi _0(i)=P\{X_0=i\}\), is called the initial distribution, it is such that \(\pi _0(i)\geq 0\) and \(\sum \limits ^m_{i=1}\pi _0=0\).

3.

It can be shown that given any transition function and any initial distributions, there is a probability space and random variables \(X_n\), \(n\geq 0\) defined as on the probability space satisfying the following \begin {align*} &P\{X_n=i_n, X_{n-1}=i_{n-1},.............,X_1=i_1, X_0=i_0\}\\ &=P_{i_{n-1}i_n} P_{i_{n-2}i_{n-1}} ........... P_{i_1i_2} P_{i_0i_1} \pi _0 (i_0) \end {align*}