Markov Chains

The probability \(\mathbb{P}[X_{n+1}=j|X_n=i]\) of going from one state to the next is called the transition probability. If the transition probability does not depend on the time step \(n\), then the Markov chain is called homogeneous.

We can define a transition probability matrix \(P\) such that

\begin{align} P_{ij} = \mathbb{P}[X_{n+1}=j|X_n=i] \end{align}

We can specify the initial distribution of \(X_0\) as \(\mathbb{P}[X_0=i]=\pi_0(i)\). The distribution of \(X_0\) and the transition probability matrix are all that is needed to fully specify a Markov chain.

First, note that the joint probability of \(X_0,\dots,X_n\) is given by

\begin{align} \mathbb{P}[X_0=i_0, X_1=i_1, \dots, X_n=i_n] = \mathbb{P}[X_0=i_0]\mathbb{P}[X_1=i_1|X_0=i_0]\mathbb{P}[X_2=i_2|X_0=i_0,X_1=i_1]\cdots \notag \end{align}

By the Markov property, this simplifies to:

\begin{align} \mathbb{P}[X_0=i_0, X_1=i_1, \dots, X_n=i_n] &= \mathbb{P}[X_0=i_0]\mathbb{P}[X_1=i_1|X_0=i_0]\mathbb{P}[X_2=i_2|X_1=i_1]\cdots \notag \\ &= \pi_0(i)P_{i_0,i_1}P_{i_1,i_2}\cdots P_{i_{n-1},i_n} \notag \end{align}

Consequently, the marginal distribution of \(X_n\) can be computed as

\begin{align} \mathbb{P}[X_n=i_n] &= \sum_{i_0,i_1,\dots,i_{n-1}\in S} \mathbb{P}[X_0=i_0,X_1=i_1,\dots X_{n-1}=i_{n-1},X_n=i_n] \notag \\ &= \sum_{i_0,i_1,\dots,i_{n-1}\in S} \pi_0(i)P_{i_0,i_1}\cdots P_{i_{n-1},i_n} \notag \\ &= [\pi_0(i)P^n]_n \notag \end{align}

In fact, for all \(n \geq 0\), \(\boxed{pi_n=\pi_0P^n}\).

Let \(A\) be the event of hitting \(0\) before \(N\). Then, let \(\alpha(i) = \mathbb{P}[A|X_0=i]\), and we can see that \(\alpha(0)=1\) and \(\alpha(N)=0\).

By the Markov property and homogeneity, we have

\begin{align} \mathbb{P}[A|X_0=i, X_1=j] = \mathbb{P}[A|X_1=j]=\mathbb{P}[A|X_0=j] = \alpha(j) \notag \end{align}

Then,

\begin{align} \alpha(i) = \sum_{j \in S}P_{ij}\alpha(j) = (1-p)\alpha(i-1) + p\alpha (i+1) \notag \end{align}

Solving, we get

\begin{align} \alpha(i) = \begin{cases} \frac{N-i}{N} &p = \frac{1}{2} \\ \frac{r^i-r^N}{1-r^N} &p \neq \frac{1}{2} \end{cases} \end{align}

where \(r = \frac{1-p}{p}\).

The row state vector \(\pi\) is called a stationary distribution or invariant distribution of the Markov chain with transition probability matrix \(P\) if

1. \(\pi_i \geq 0 \; \forall i \in S\) and \(\sum_{i\in S}\pi_i = 1\)
2. \(\pi P = \pi\) (left eigenvector with eigenvalue \(1\))

State \(j\) is accessible from state \(i\) if \([P^n]_{ij} > 0\) for some positive \(n \in \mathbb{N}\) (there is a path from \(i\) to \(j\)). States \(i\) and \(j\) intercommunicate if \(j\) is accessible from \(i\) and \(i\) is also accessible from \(j\).

A Markov chain is called irreducible if any state \(i\) and \(j\) in the state space are intercommunicable, i.e. any state can reach any other state. Every Markov chain with finite state space has at least one stationary distribution. Additionally, if that chain is irreducible, that stationary distribution is unique.

The period \(d(i)\) of a state \(i\in S\) is defined as

\begin{align} d(i) = \text{gcd}(n \geq 1 | [P^n]_{ii}>0) \end{align}

In other words, the GCD of the number of steps it takes for all paths that go back to that state. A state is periodic if \(d(i) > 1\), and aperiodic if \(d(i) = 1\).

Theorem: If \(i\) and \(j\) intercommunicate, then \(d(i)=d(j)\).

Proof: Recall that \(d(i) = \text{gcd}(n\geq 1 | [P^n]_{ii}>0)\). We want to show that \(d(i)=d(j)\), so it is equivalent to show that \(d(i) | d(j)\) and \(d(j) | d(i)\).

Since \(i\) and \(j\) intercommunicate, there is a path from \(i\) to \(j\) with length \(l_{ij}\), and a path from \(j\) to \(i\) with length \(l_{ji}\). We know that there exists a path from \(j\) back to \(j\) with length \(l_{ij}+l_{ji}\). Then, an arbitrary path from \(j\) back to \(j\) with length \(k\) means that we also have a path from \(i\) back to \(i\) with length \(l_{ij}+l_{ji}+k\). Then,

\begin{align} d(i)&|l_{ij}+l_{ji}+k \notag \\ d(i) &| l_{ij} + l_{ji} \notag \\ \Rightarrow d(i) &| k \notag \end{align}

Since \(k\) must be a multiple of \(d(j)\), we have \(d(i)|d(j)\). By symmetry, we can also see that \(d(j)|d(i)\). \(\square\)

The Fundamental Theorem of Markov Chains says that if a finite Markov chain is irreducible and aperiodic, then it converges to a stationary distribution.