Markov Chains & Processes

In the study of stochastic processes, the Markov Chain represents the most fundamental model for systems evolving over time where the future is conditionally independent of the past, given the present state. This property, known as the Markov Property, allows for the rigorous analysis of complex systems ranging from thermodynamics to financial modeling and web search algorithms.

1. The Markov Property

Let $\{X_n,n\ge 0\}$ be a stochastic process taking values in a countable state space $S$. The process is a Markov Chain if for all $n\ge 0$ and all states $i_0,i_1,\dots ,i_n,j\in S$:

$P(X_{n+1}=j\mid X_n=i_n,X_{n-1}=i_{n-1},\dots ,X_0=i_0)=P(X_{n+1}=j\mid X_n=i_n)$

If this probability is independent of $n$, the chain is said to be time-homogeneous. We define the transition probability from state $i$ to state $j$ as:

$P_{ij}=P(X_{n+1}=j\mid X_n=i)$

The sequence of probabilities $\{X_0,X_1,\dots \}$ is thus entirely determined by the initial distribution $\nu (i)=P(X_0=i)$ and the transition probabilities.

2. The Transition Probability Matrix

For a finite state space $S=\{1,2,\dots ,k\}$, we can collect these probabilities into a $k\times k$ matrix $P$:

$P=\left(\begin{array}{cccc}{P}_{11}& P_{12}& \dots & P_{1k}\\ P_{21}& P_{22}& \dots & P_{2k}\\ ⋮& ⋮& \ddots & ⋮\\ P_{k1}& P_{k2}& \dots & P_{kk}\end{array}\right)$

Properties of Stochastic Matrices

1. Non-negativity: $P_{ij}\ge 0$ for all $i,j\in S$.
2. Row Stochasticity: ${\sum }_{j\in S}{P}_{ij}=1$ for all $i\in S$.
   • This implies that the vector of ones $1$ is a right eigenvector of $P$ with eigenvalue $\lambda =1$: $P1=1$.

3. The Chapman-Kolmogorov Equations

To understand the evolution over multiple steps, we define the $n$-step transition probability $P_{ij}^{(n)}=P(X_n=j\mid X_0=i)$.

The Chapman-Kolmogorov equations state: $P_{ij}^{(m+n)}={\sum }_{k\in S}{P}_{ik}^{(m)}{P}_{kj}^{(n)}$

In matrix notation, this is elegantly expressed as: $P^{(n)}=P^n$

Thus, the probability of being in state $j$ after $n$ steps, given an initial distribution vector ${\pi }^{(0)}$, is: ${\pi }^{(n)}={\pi }^{(0)}{P}^n$

4. State Classification

The long-term behavior of a Markov Chain depends on the structural relationships between its states.

Communication and Irreducibility

• Accessibility: State $j$ is accessible from $i$ ($i\to j$) if $P_{ij}^{(n)}>0$ for some $n\ge 0$.
• Communication: If $i\to j$ and $j\to i$, we say $i$ and $j$ communicate ($i\leftrightarrow j$). Communication is an equivalence relation that partitions the state space into communicating classes.
• Irreducibility: A Markov Chain is irreducible if there is only one communicating class (i.e., every state is accessible from every other state).

Periodicity

The period $d(i)$ of state $i$ is defined as: $d(i)=\gcd \{n>0:P_{ii}^{(n)}>0\}$ If $d(i)=1$, the state is aperiodic. In an irreducible chain, all states have the same period.

Recurrence vs. Transience

Let $f_i$ be the probability that, starting in state $i$, the process ever returns to $i$.

• Recurrent: $f_i=1$. The process will return to $i$ infinitely many times.
• Transient: $f_i<1$. There is a non-zero probability the process never returns.

A recurrent state is Positive Recurrent if the expected time to return $E[T_i]$ is finite, and Null Recurrent otherwise (only possible in infinite state spaces).

5. Stationary Distribution $\pi$

A probability distribution $\pi$ (represented as a row vector) is called a stationary distribution if: $\pi P=\pi ,\text{subject to }{\sum }_{i\in S}{\pi }_i=1$

This corresponds to a left eigenvector of $P$ associated with the eigenvalue $\lambda =1$.

Fundamental Theorem

For any irreducible and aperiodic (ergodic) Markov Chain:

1. A unique stationary distribution $\pi$ exists.
2. ${\lim }_{n\to \infty }{P}_{ij}^{(n)}={\pi }_j$ for all $i,j$.
3. The distribution of $X_n$ converges to $\pi$ regardless of the initial distribution.

6. Absorbing Markov Chains

A state $i$ is absorbing if $P_{ii}=1$. A chain is absorbing if it has at least one absorbing state and from every state it is possible to reach an absorbing state.

The transition matrix of an absorbing chain can be arranged in canonical form: $P=\left(\begin{array}{cc}Q& R\\ 0& I\end{array}\right)$ where $Q$ represents transitions between transient states. The Fundamental Matrix $N$ is: $N=(I-Q{)}^{-1}=I+Q+Q^2+\dots$ The entry $N_{ij}$ represents the expected number of times the process stays in transient state $j$ given it started in transient state $i$. The expected time to absorption starting from $i$ is the $i$-th entry of the vector $N1$.

7. Applications: Google’s PageRank

The PageRank algorithm models a “random surfer” on the web. Let $G$ be the hyperlink graph. The transition matrix $H$ is defined where $H_{ij}=1/(\text{out-degree of }i)$ if a link exists. To ensure irreducibility and aperiodicity, a damping factor $\alpha$ (typically 0.85) is introduced: $G=\alpha H+(1-\alpha )\frac{1}{n}\mathbf{E}$ where $\mathbf{E}$ is an all-ones matrix. The PageRank vector is the stationary distribution of $G$.

8. Computational Implementation

Below is a Python implementation to compute the stationary distribution of a Markov Chain using two methods: solving the linear system (eigenvector) and long-run simulation.

import numpy as np
from scipy import linalg

def compute_stationary(P):
    """
    Computes the stationary distribution of a transition matrix P.
    Method 1: Eigenvector decomposition.
    Method 2: Power iteration (long-run simulation).
    """
    n = P.shape[0]
    
    # Method 1: Algebraic Solution
    # We solve pi(P - I) = 0, which is (P^T - I)pi^T = 0
    # Also we know sum(pi) = 1.
    A = np.append(P.T - np.eye(n), [np.ones(n)], axis=0)
    b = np.append(np.zeros(n), [1])
    # Use least squares to solve the overdetermined system
    pi_algebraic, _, _, _ = linalg.lstsq(A, b)
    
    # Method 2: Power Iteration
    # Repeatedly apply the transition matrix
    pi_sim = np.ones(n) / n
    for _ in range(1000):
        prev_pi = pi_sim.copy()
        pi_sim = pi_sim @ P
        if np.allclose(pi_sim, prev_pi, atol=1e-10):
            break
            
    return pi_algebraic, pi_sim

# Example: 3-state system
# 0: Sunny, 1: Cloudy, 2: Rainy
P = np.array([
    [0.7, 0.2, 0.1],
    [0.3, 0.4, 0.3],
    [0.2, 0.3, 0.5]
])

algebraic, simulated = compute_stationary(P)
print(f"Algebraic Pi: {algebraic}")
print(f"Simulated Pi: {simulated}")

Quiz