Long-Run Markov Chains

Example 1 (Stationary Distributions)

Consider a $2-$state Markov Chain with $S=\{0,1\}$.

$$P=\left(\begin{array}{cc}3/4& 1/4\\ 1/6& 5/6\end{array}\right)$$

and $\mathbb{P}(X_1=0|X_0=0)=3/4$ etc. Then

$$\underset{n\to \infty }{\lim }{P}^n=\left(\begin{array}{cc}0.4& 0.6\\ 0.4& 0.6\end{array}\right)=\left[\begin{array}{c}\pi \\ \pi \end{array}\right]$$

where $\pi =(0.4,0.6)$ is the stationary distribution.

Proof:

Let ${\pi }_0=(a_0,a_1)=(\mathbb{P}(X_0=0),\mathbb{P}(X_0=1))$. Note that $a_0+a_1=1$. Then

$${\pi }_n=[\mathbb{P}(X_n=0),\mathbb{P}(X_n=1)]={\pi }_0{P}^n$$

which implies that

$$\underset{n\to \infty }{\lim }{\pi }_n=\underset{n\to \infty }{\lim }{\pi }_0{P}^n$$

from Proposition (Stochastic Properties). We get

$$\underset{n\to \infty }{\lim }{\pi }_0{P}^n=(a_0,a_1)\left(\begin{array}{cc}0.4& 0.6\\ 0.4& 0.6\end{array}\right)=(0.4,0.6)=\pi$$

Example 2 (Starting Distributions Don’t Matter)

Suppose we have $3-$states and $S=\{0,1,2\}$ and

$$P=\left(\begin{array}{ccc}3/4& 1/4& 0\\ 1/8& 2/3& 5/24\\ 0& 5/6& 1/6\end{array}\right)$$

With $\mathbb{P}$ being defined as usual. Then

$$\underset{n\to \infty }{\lim }{P}^n=\left(\begin{array}{c}\pi \\ \pi \\ \pi \end{array}\right)$$

where $\pi =(2/11,4/11,5/11)$.

Set ${\pi }_0=(\mathbb{P}(X_0=i))$. Then ${\pi }_n={\pi }_0{p}^n$ such that

$$\underset{n\to \infty }{\lim }{\pi }_n={\pi }_0\cdot \left(\begin{array}{c}\pi \\ \pi \\ \pi \end{array}\right)=\left(\pi (1)\cdot \sum _i{\pi }_0(i),\dots \right)=\pi$$

Because the sum of the starting distribution must equal $1$, it does not matter what distribution we start from. We will always return to stationary vector $\pi$.

Remark

1. For any state $j$, the probability of a system being that state at time $n$ approaches a fixed value $\pi (j)$ as $n$ goes to infinity. $$\underset{n\to \infty }{\lim }\mathbb{P}(X_n=j)=\pi (j)$$ Essentially, after enough time, the specific starting state is irrelevant.
2. Once the distribution reaches the long-term state $\pi$, it stays there. The distribution is invariant under the transition matrix $P$. $$\begin{array}{rl}\pi =\underset{n\to \infty }{\lim }{\pi }_{n+1}& =\underset{n\to \infty }{\lim }{\pi }_0{P}^{n+1}\\ & =\underset{n\to \infty }{\lim }({\pi }_0{P}^n)\cdot P\\ & =\pi P\end{array}$$ So we get that $\pi$ is a row eigenvector of $P$.

Theorem (Average Transition Behavior)

For a Markov Chain,

$$\underset{n\to \infty }{\lim }\frac{1}{n}\sum _{k=0}^{n-1}{p}_k(i,j)=\underset{n\to \infty }{\lim }{p}_n(i,j)=\pi (j)$$

We are essentially asking:

If we simulated all possible Markov Chains from state $i$, what fraction of them would be in state $j$ on average?

The idea is that even if we bounce around $j$, the average of those probabilities settles to $\pi (j)$.

Proof:

$$\begin{array}{rl}\frac{1}{n}\sum _{k=0}^{n-1}{p}_k(i,j)& =\frac{1}{n}\sum _{k=0}^{n-1}\mathbb{P}(X_k=j|X_0=i)\\ & =\frac{1}{n}\sum _{k=0}^{n-1}\mathbb{E}\left[1(X_k=j)|X_0=i\right]\\ & =\mathbb{E}\left[\frac{1}{n}\sum _{k=0}^{n-1}1(X_k=j)|X_0=i\right]\\ & \to \pi (j)\end{array}$$

as $n\to \infty$. So, the mean fraction of the time spent in state $j$ is shown by $\pi (j)$.

Theorem (Time Average of the Indicator)

What if we ran every Markov Chain, but every time we reached state $i$ at some time $k$, we counted it. What fraction of the time do we spend on state $i$? More formally, what is

$$\frac{1}{n}\sum _{k=1}^{n}1\{X_k=i\}$$

where

$$1(X_k)=\{\begin{array}{ll}1& X_k=i\\ 0& \text{otherwise}\end{array}$$

If $n\to \infty$ then this value converges to $\pi (i)$ for all $i\in S$.

Theorem (Law of Large Numbers for Markov Chains)

Instead of counting visits, we can count the “reward” of visiting specific states.

$$\underset{n\to \infty }{\lim }\frac{1}{n}\sum _{k=1}^{n}g(X_k)={\mathbb{E}}_{\pi }(g(X))$$

Remarks (Markov Chain Computation)

• We can view Markov Chains as evolutions of probability vectors (PMFs): ${\pi }_0,{\pi }_1,\dots ,{\pi }_{n+1}={\pi }_{n}P$. But this is hard to compute for large state spaces (when $|S|$ is large).
• Markov Chains are a random sequence of states $X_0,X_1,\cdots \in S$, which is often easier to simulate.
• Recall from Discrete Case that we can generate discrete random variables $X$ where $\mathbb{P}(X=i)=p_i$ for $i\in \{1,2,3\}$ and $p_1+p_2+p_3=1$.

Algorithm (Generate/Simulate Markov Chains)

Input: Transition matrix $P$ and an initial distribution ${\pi }_0$.

Output: A Markov Chain $X_0,\dots ,X_n\in S$ where $X_k\sim {\pi }_k$.

1. Generate $X_0\sim {\pi }_0$.
2. For $k=1$ to $n$:
   1. Generate $X_{k+1}$ from $p(X_k,-)$, the PMF over $S$ given by the $X_k$‘th row of $P$.
3. Repeat this $N$ times to get a sample from ${\pi }_n$.

The key idea is to generate the distribution $\pi$ by simulating Markov Chain $\{X_n{\}}_{n=0}^{\infty }$ with a stationary distribution $\pi$. Often $\pi$ is known up to a normalizing constant. By Theorem (Average Transition Behavior), Theorem (Time Average of the Indicator), and Theorem (Law of Large Numbers for Markov Chains) this algorithm converges to $\pi$.

Remark (Discreteness)

This algorithm also works for discrete time and states. Let $X\in S$ be discrete random variables, e.g. $S=\{1,2,\dots ,N\}$. Then the target PMF of $X$ is

$$\pi =(\pi (1),\dots ,\pi (N))$$

where

$$\forall i\in S,\pi (i)=\mathbb{P}(X=i)$$

Stationary distribution $\pi$ has a special PMF form:

$$(i)=\frac{1}{Z}b(i)>0$$

for all $i\in S$, where $b(i)>0$ are known and $Z>0$ is an unknown normalization. In particular,

$$\sum _{i\in S}(i)=1⟺\sum _{i\in S}b(i)=Z$$

You can think of $b(i)$ as the “score” or weight of each state. If $b(i)>b(j)$, then state $i$ is more likely than state $j$. $Z$ is how we normalize the PMF $(i)$.

In practice, $Z$ is hard to compute, as it is the sum of $N$ terms. $Z$ is called the partition function in statistical physics.