Some cool things about finite Markov chains and thereof

In this post, I wanna summarize Sections 1.5 and 1.6 of Introduction to Stochastic Processes and kinda blew my mind.

Okay, so we’re dealing with finite Markov chains {$X_n$} that have transition matrix $P$. A markov chain can have some recurrent classes and some transient states. Therefore, we can divide $P$ in blocks that represent these concepts. Concretely,

where $\tilde{P}$ contains the transitions of recurrent classes and $Q$ contains the transitions of transient states. The matrix $Q$ is a substochastic matrix and since it only contains transient states, its eigenvalues are strictly less than one, which implies $\lim_{n \to \infty} Q^n \to 0$.

So, now let’s prove that if a matrix $A$ has eigenvalues less than one, then $\lim_{n \to \infty} A^n \to 0$. We know that we can write any matrix $A$ in its Jordan form as $A = M J M^{-1}$, hence $A^n = MJ^nM^{-1}$. The matrix $J$ is of the form

where

As $n$ tends to infinity, $J^n$ tends to zero, and as a result $A^n$ tends to zero.

Let $i$ be a transient state and $Y_i$ denote the total number of visits to $i$ which by the virtue of being a transient state is finite almost surely. Suppose $X_0 =j$, where $j$ is another transient state. Then,

However, we’ll show right away that $\left(I + Q + Q^2 \dots \right)(1 - Q) = I$.

By ChatGPT.

Let $A$ be any matrix with eigenvalues’s magnitude strictly less than one, then

Proof.

Consider the partial sum

\(S_n = \sum_{k =0}^n A^k.\) Then,

Hence,

\(\begin{align*} S_n = (I - A)^{-1}\left(I - A^{n + 1}\right) \end{align*}.\) As $n$ tends to infinity, $S_n$ tends to $(I - A)^{-1}$.

Therefore, define $M = (1 - Q)^{-1}$ to get $\mathbb{E}[Y_i \mid X_0 = j] = M_{ji}$. The upshot is: If we want to compute the expected number of steps until the chain enters a recurrent class, assuming $X_0 = j$, we need only sum $M_{ji}$ over all transient states $i$.

We can also use this technique to determine the expected number of steps that an irreducible Markov chain takes to go from one state $j$ to another state $i$. We first write the transition matrix $P$ for the chain with $i$ being the first pivot:

We then change $i$ to an absorbing state

Let $T_i$ be the number of steps needed to reach state $i$. For any other state $k$ let $T_{i,k}$ be the number of visits to $k$ before reaching $i$.Then,

We now suppose that there are at least two different recurrent classes and ask the question: starting at a given transient state $j$, what is the probability that the Markov chain eventually ends up in a particular recurrent class?

In order to answer this question, we can assume that the recurrent classes consist

of single points $r_1,\dots , r_k$ with $p(r_i, r_i) = 1$. If we order the states so that the recurrent states $r_1,\dots , r_k$ precede the transient states $t_1, \dots, t_s$, then

For $i = 1,\dots , s, \, j = 1,\dots , k$, let $\alpha(t_i, r_j)$ be the probability that the chain

starting at $t_i$ eventually ends up in recurrent state $r_j$. We set $\alpha(r_i, r_i) = 1$ and $\alpha(r_i, r_j) = 0 \; \mathrm{if}\, i \neq j$. For any transient state $t_i$ and some $n$,

In the matrix form, if $A$ is an $s \times k$ matrix with $\alpha(t_i, r_j)$ entries, then the above display can be written as:

\(\begin{pmatrix} I \\ A \end{pmatrix} = P \begin{pmatrix} I \\ A \end{pmatrix} = \begin{pmatrix} I & 0 \\ S & Q \end{pmatrix} \begin{pmatrix} I \\ A \end{pmatrix}.\) Hence,

Example. Consider a random walk with absorbing boundary on {$0, 1, \dots, 4$}. If we order the states {$0, 4, 1, 2, 3$} so that the recurrent states precede the transient states then

Then,

Hence , starting at state 1 the probability that the the walk is eventually absorbed at state 0 is 3/4.

Example (Gambler’s ruin). Consider the random walk with absorbing boundary on {$0, \dots , N$}. Let $\alpha(j) = \alpha(j, N)$ be the probability that the walker starting at state $j$ eventually ends up absorbed in state $N$. The boundary conditions are $\alpha(0) = 0, \alpha(N) = 1$. For state $0 < j < N$ we have:

This is a linear difference equation. So, let’s solve it. We need to test $\alpha(j) = \lambda^j$ in the equation:

Hence,

After applying the boundary conditions:

Suppose $p = 1/2$, and let $T$ be the time it takes for the random walk to reach $0$ or $N$, and let

$G(0) = 0, G(N) = 0$ and by considering one step we can that

As an inhomogeneous linear difference equation, $G(j) = j^2$ is a solution. After solving the homogeneous version, we get:

After applying the boundary conditions, we get:

Example Simple Random Walk on a Circle. Let $N \geq 2$ be an integer. We can consider {$0, 1, … , N -1$} to be a “circle” by assuming that $N - 1$ is adjacent to $0$ as well as $N -2$. The invariant probability is the uniform distribution (why?). Assume that $X_0 = 0$ and let $T_k$ denote the first time at which the number of distinct points visited equals $k$. Then $T_N$ is the first time that every point has been visited. By definition  $T_1 = 0$, and $T_2 = 1$. We compute $r(k) = \mathbb{E}[T_k - T_{k-1}]$ for $k = 3,\dots , N$; a little thought will show that the value depends only on $k$ and not on $N$. At time $T_{k-1}$ the chain is at a boundary point so that one of the neighbors of $X_{T_{k - 1}}$, has been visited and the other has not. In the next step we will either visit the new point or we will go to an interior point. If we go to the interior point, the random walk has to continue until it reaches a boundary point and then we start afresh. By $G(j) = j(N - j)$ above, the expected time that it takes the random walk from the interior point (next to the boundary point) to reach a boundary point within {$1, \dots k - 1$} is

We therefore get the equation

\(r(k) = 1/2 + 1/2[1 + (k - 3) + r(k)].\) Therefore,

Example (Urn Model). Suppose there is an urn with $N$ balls. Each ball is colored either red or green. In each time period, one ball is chosen at random from the urn and with probability $1/2$ is replaced with a ball of the other color; otherwise, the ball is returned to the urn. Let $j$ denote the number of red balls. This chain would tend to keep the number of red balls and green balls about the same. In fact, the invariant probability is given by the binomial distribution

\(\pi(j) = {N \choose j}\frac{1}{2^N}.\) Proof.

And,

Hence, their sum equals ${N \choose j}\frac{1}{2}$ and we have:

Example (Cell Genetics). Suppose each cell has $N$ particles each of type $I$ or $II$. Let $j$ be the number of particles of type $I$. In reproduction, it is assumed that the cell duplicates itself and then splits, distributing the particles. After duplication, the cell has $2j$ particles of type $I$ and $2(N - j)$ particles of type $II$. It then selects $N$ of these $2N$ particles for the next cell. By using the hypergeometric distribution we see that this gives rise to transition probabilities

This Markov chain has two absorbing states, $0$ and $N$. Eventually, all cells will have only particles of type $I$ or of type $II$.

Example (Card shuffling). Consider a deck of cards numbered $1, \dots, n$. At each time we draw a card at random and placing it at the top of the deck. This can be thought of as a Markov chain on $S_n$, the set of permutations of $n$ elements. If $\lambda$ denotes any permutation (one-to-one

correspondence of {$1,\dots, n$} with itself), and $\nu_j$ denotes the permutation corresponding to moving the $j$th card to the top of the deck, then the transition probabilities for this chain are given by

This chain is irreducible and aperiodic (we have self-loops). The unique invariant probability is the uniform measure on $S_n$, the measure that assigns probability $1/n!$ to each permutation (how?).