Finite Markov Chains

A discrete-time stochastic process is made up of $X_n$ for $n=0,1,2,\dots$, where $X_n$ takes on values in a finite set

The possible values for $X_n$ are the states of the system

We can describe the probability of a process as $\mathbb{P}\{X_0=i_0,X_1=i_1,\dots ,X_n=i_n\}$ or more expressively, as an initial probability distribution $\varphi (i)=\mathbb{P}\{X_0=i\}$ and the transition probabilities $q_n(i_n\mid i_0,\dots ,i_{n-1})$

The Markov property states that transitions are reliant only on the current state, not on previous states, $\mathbb{P}\{X_n=i_n\mid X_0=i_0,\dots ,X_{n-1}=i_{n-1}\}=\mathbb{P}\{X_n=i_n\mid X_{n-1}=i_{n-1}\}$

A process is time-homogeneous if the transition probabilities are not functions of $n$

A time-homogeneous Markov chain has each transition probability defined as $p(i_{n-1},i_n)$ for some function $p:S\times S\to [0,1]$. These are of special interest.

We can define this kind of process with an initial distribution $\varphi (i)$ and transition probabilities $p(i,j)$. $p$ is nicely expressed as a transition matrix ${\mathbf{P}}_{ij}=p(i,j)$.

We call $\mathbf{P}$ a stochastic matrix, since $0\le {\mathbf{P}}_{ij}\le 1$ and ${\sum }_{j=1}^N{\mathbf{P}}_{ij}=1$

If we express $\varphi (i)$ as a vector ${\vec{\varphi }}_0$, we can write ${\vec{\varphi }}_n={\vec{\varphi }}_0{\mathbf{P}}^n$

Large-Time Behavior

We are interested in seeing what happens with ${\lim }_{n\to \infty }{\mathbf{P}}^n$. We first observe that for many systems, $\vec{\pi }={\lim }_{n\to \infty }\vec{v}{\mathbf{P}}^n$ for any starting $\vec{v}$.

We call $\vec{\pi }$ an invariant probability distribution for $\mathbf{P}$ if $\vec{\pi }=\vec{\pi }\mathbf{P}$ (also called a stationary, equilibrium, or steady-state distribution)

Definitionally, $\vec{\pi }$ is a left eigenvector of $\mathbf{P}$ with eigenvalue $1$

Question: How do we know $\vec{\pi }$ exists?

The key in this process is that diagonalizing $\mathbf{P}$ gives us an eigenvalue of $1$ and other eigenvalues with absolute value $<1$. This means that repeated powers leaves us with only the eigenvector corresponding to $1$.

Now, for any stochastic matrix, we have $\vec{1}$ as a right eigenvector with eigenvalue $1$, which means there must be a left eigenvector with eigenvalue $1$. So we must show,

1. The left eigenvector can be chosen to have nonnegative entries (and therefore can be normalized to be a distribution)
2. The eigenvalue $1$ is simple (no multiplicity), and all other eigenvalues have absolute value $<1$

We cannot always diagonalize $\mathbf{P}$, but the Jordon decomposition is good enough and has the same effect

Perron-Frobenius Theorem: If $\mathbf{P}$ has all positive entries, then $1$ is a simple eigenvalue, its left eigenvector can be chosen as positive, and all other eigenvalues have absolute value $<1$

This does not cover certain stochastic matrices with $0$ entries that do satisfy the limit behavior. If ${\mathbf{P}}^n$ satisfies Perron-Frobenius, then $\mathbf{P}$ satisfies our needed conditions

Now our question is which kinds of stochastic matrices have some ${\mathbf{P}}^n$ with all positive entries

Cases where this is not true,

1. Simple random walk with reflecting boundary: In this case, every step alternates between even and odd states. The matrix will basically “oscillate” instead of converging.
2. Simple random walk with absorbing boundary: In this case, the boundaries absorb all processes, while the middle (transient) states will go to $0$.
3. Two non-interacting chains: We call this reducible

Definition: Two states communicate $i\leftrightarrow j$ if there exist $p_m(i,j)>0$ and $p_n(j,i)<0$, meaning a process starting in one state can reach the other

$\leftrightarrow$ is an equivalence relation

• Reflexive: $i\leftrightarrow i$
• Symmetric: $i\leftrightarrow j⟺j\leftrightarrow i$
• Transitive: $i\leftrightarrow j\cap j\leftrightarrow k⟹i\leftrightarrow k$

These equivalence relations partition our state space into disjoint communication classes

If there is only one communication class, then the chain is irreducible. Matrices with invariant distributions are irreducible. But we also see irreducible chains that do not have invariant distributions (our reflecting boundary chain).

Some communication classes are transient, meaning a process will leave them and never return with probability $1$

For each recurrent class $R$, the submatrix of $\mathbf{P}$ obtained from only considering the rows and columns for states in $R$ is also a stochastic matrix. We can analyze the large-time behavior of $R$ by only considering this submatrix.

Definition: The period of a state $d(i)$ is the greatest common divisor of $J_i:=\{n\ge 0:p_n(i,i)>0\}$

Theorem: If $i\leftrightarrow j$ then $d(i)=d(j)$

Definition: An irreducible matrix $\mathbf{P}$ is aperiodic if $d=1$ and therefore has all entries positive for some ${\mathbf{P}}^n$. According to Perron-Frobenius, there exists a unique invariant probability vector $\vec{\pi }$, such that ${\lim }_{n\to \infty }\vec{\varphi }{\mathbf{P}}^n=\vec{\pi }$ for any $\vec{\varphi }$.

Reducible or Periodic Markov Chains

If $\mathbf{P}$ is reducible with $r$ recurrent classes $R_1,\dots ,R_r$ and $s$ transient classes $T_1,\dots ,T_s$, then each recurrent class acts as a smaller Markov chain. Therefore, there are $r$ invariant probability vectors ${\bar{\pi }}^1,\dots ,{\bar{\pi }}^r$, and the eigenvalue $1$ has multiplicity $r$.

If $i\in R_k$, ${\lim }_{n\to \infty }{p}_n(i,j)={\pi }^k(j)$ if $j\in R_k$ or $0$ otherwise
Therefore, ${\lim }_{n\to \infty }{p}_n(i,j)=0$ for each transient state $j$

Let ${\alpha }_k(i)$ be the probability that the chain starting in state $i$ ends up in recurrent class $R_k$. We see that ${\lim }_{n\to \infty }{p}_n(i,j)={\alpha }_k(i){\pi }^k(j)$. ${\lim }_{n\to \infty }\vec{\varphi }{\mathbf{P}}^n$ exists but depends on $\vec{\varphi }$.

How do we understand the powers of $\mathbf{P}$?

If $\mathbf{P}$ is irreducible but has period $d>1$, then the state space splits into $d$ sets $A_1,\dots ,A_d$. In general, $\mathbf{P}$ will have $d$ simple eigenvalues with absolute value $1$, the $d$ solutions to $z^d=1$. $\vec{\varphi }{\mathbf{P}}^n$ will cycle through these $d$ distributions, which will average to $\vec{\pi }$. In this case, $\pi (i)$ does not represent the limit of $p_n(j,i)$, but the average time spent in $i$.

Return Times

Let $X_n$ be an irreducible Markov chain with transition matrix $\mathbf{P}$. Consider the amount of time spent in state $j$ up to and including time $n$,
$Y(j,n)={\sum }_{m=0}^{n}I\{X_m=j\}$
We can relate this quantity to $\pi$, since ${\lim }_{n\to \infty }\frac{1}{n+1}\mathbb{E}(Y(j,n)\mid X_0=i)={\lim }_{n\to \infty }\frac{1}{n+1}{\sum }_{m=0}^n\mathbb{P}\{X_m=j\mid X_0=i\}=\pi (j)$

Assume $X_0=i$ and let $T$ be the first time after $0$ that the Markov chain is in $i$, $T=\min \{n\ge 1:X_n=i\}$

The $k$th return to state $i$ is given as the sum of independent and identical random variables $T_1+\cdots +T_k$. Therefore, for large $k$, we have $\frac{1}{k}(T_1+\cdots +T_k)\approx \mathbb{E}(T)$

In other words, in $k\mathbb{E}(T)$ steps we find about $k$ visits. And since we know that in $n$ steps we expect about $n\pi (i)$ visits, we have

$$\mathbb{E}(T)=\frac{1}{\pi (i)}$$

Suppose $\mathbf{P}$ has some transient states and let $\mathbf{Q}$ be the submatrix of $\mathbf{P}$ which includes only the rows and columns for the transient states,

$$\mathbf{P}=\left[\begin{array}{c}\begin{array}{cc}\tilde{\mathbf{P}}& 0\\ \mathbf{S}& \mathbf{Q}\end{array}\end{array}\right],{\mathbf{P}}^n=\left[\begin{array}{c}\begin{array}{cc}{\tilde{\mathbf{P}}}^n& 0\\ {\mathbf{S}}_n& {\mathbf{Q}}^n\end{array}\end{array}\right].$$

$\mathbf{Q}$ is called a substochastic matrix, since it has row sums $\le 1$. We already know ${\mathbf{Q}}^n\to 0$, implying its eigenvalues have absolute value strictly less than $1$. Therefore, $\mathbf{I}-\mathbf{Q}$ has no $\lambda =0$ and we can define $\mathbf{M}=(\mathbf{I}-\mathbf{Q}{)}^{-1}$, which is called the fundamental matrix.

For a transient state $i$, $Y_i={\sum }_{n=0}^{\infty }I\{X_n=i\}<\infty$. Suppose $X_0=j$ is another transient state, $\mathbb{E}(Y_i\mid X_0=j)={\sum }_{n=0}^{\infty }{p}_n(j,i)$, which is also the $(j,i)$ entry of the matrix $\mathbf{I}+\mathbf{Q}+{\mathbf{Q}}^2+\dots$

We can show that $(\mathbf{I}+\mathbf{Q}+{\mathbf{Q}}^2+\dots )(\mathbf{I}-\mathbf{Q})=\mathbf{I}$
So $\mathbf{I}+\mathbf{Q}+{\mathbf{Q}}^2+\cdots =(\mathbf{I}-\mathbf{Q}{)}^{-1}=\mathbf{M}$

We can do a lot with this. Observe how the expected number of steps until the chain enters a recurrent class, assuming $X_0=j$, is the sum of the $j$th row of $\mathbf{M}$

To find the expected number of steps the irreducible Markov chain takes to go from any state $j$ to another state $i$, we rearrange $\mathbf{P}$ such that $i$ is the first site, and modify it to be an absorbing site. $\mathbb{E}(T_i\mid X_0=j)=\mathbb{E}\left[{\sum }_{k\ne i}^{}{T}_{i,k}\mid X_0=j\right]={\sum }_{k\ne i}^{}{\mathbf{M}}_{jk}$

Note that the above procedure is only going to make sense on an irreducible chain (I don’t think this quantity would always be defined otherwise).

What if there are multiple recurrent classes? Starting at a given transient state $j$, what is the probability that the Markov chain ends up in a particular recurrent class?

To simplify this problem, we treat recurrent classes as single points $r_1,\dots ,r_k$ with $p(r_i,r_i)=1$. This lets us order our transition matrix as,

$$\left[\begin{array}{c}\begin{array}{cc}\mathbf{I}& 0\\ \mathbf{S}& \mathbf{Q}\end{array}\end{array}\right]$$

Denote $\alpha (t_i,r_j)$ be the probability that the chain starting at transient state $t_i$ ends up in recurrent state $r_j$. With two recurrent states, $\alpha (r_i,r_i)=1$ and $\alpha (r_i,r_j)=0$ if $i\ne j$. For any transient state $t_i$, $\alpha (t_i,r_j)=\mathbb{P}\{X_n=r_j\mid X_0=t_i\}={\sum }_{x\in S}^{}\mathbb{P}\{X_1=x\mid X_0=t_i\}\mathbb{P}\{X_n=r_j\mid X_1=x\}$
$={\sum }_{x\in S}^{}p(t_i,x)\alpha (x,r_j)$

We can write this as $\mathbf{A}=\mathbf{S}+\mathbf{QA}$, where ${\mathbf{A}}_{\mathbf{ij}}=\alpha (t_i,r_j)$ is an $s\times k$ matrix,

$$\mathbf{A}=(\mathbf{I}-\mathbf{Q}{)}^{-1}\mathbf{S}=\mathbf{MS}$$

Reversibility

^202837
Markov chains define a direction for time. Can we reverse the direction of a chain?

$\mathbb{P}[X_{n+1}=j\mid X_n=i]={\mathbf{P}}_{ij}$
$\mathbb{P}[X_n=i\mid X_{n+1}=j]=\text{?}$

Let’s label this “flipped” probability ${\mathbf{Q}}_{ij}$
${\mathbf{Q}}_{ij}=\frac{{\mathbf{P}}_{ij}\cdot \mathbb{P}[X_n=i]}{\mathbb{P}[X_{n+1}=j]}$

We see that conditioning on the entire future leads to the same result, ${\mathbf{Q}}_{ij}=\frac{\mathbb{P}[X_n=i,X_{n+1}=j,\dots ,X_{n+k}=x_{n+k}]}{\mathbb{P}[X_{n+1}=j,\dots ,X_{n+k}=x_{n+k}]}=\frac{P_{ij}\cdot \mathbb{P}[X_n=i]}{\mathbb{P}[X_{n+1}=j]}$

However, this probability is still a function of $n$. We can take the initial condition to be the invariant measure, and now the Markov chain is time-homogeneous. So we see ${\mathbf{Q}}_{ij}$ must be equal to $\frac{{\pi }_i{\mathbf{P}}_{ij}}{{\pi }_y}$

Definition: If ${\pi }_i{\mathbf{P}}_{ij}={\pi }_j{\mathbf{P}}_{ji}$ for some $\pi$ then ${\mathbf{Q}}_{ji}={\mathbf{P}}_{ij}$ and $X_n$ is reversible (and $\pi$ is the invariant measure)