Why Do Markov Chains Always Converge? A Hands‑On Exploration

Markov Chain Overview

A Markov chain assumes that the probability of transitioning to a new state depends only on the current state, not on earlier ones. For example, tomorrow’s weather depends only on today’s weather. This simplification makes the model useful in many time‑series applications such as RNNs, HMMs, and MCMC.

Mathematically, if the sequence of states is \(X_0, X_1, \dots\), then the conditional probability \(P(X_{t}=j\mid X_{t-1}=i)\) depends only on the immediate predecessor.

Once the transition probabilities between any two states are known, the Markov chain model is defined. The figure below (from Wikipedia) shows a three‑state stock‑market model.

The three states are Bull market, Bear market, and Stagnant market, with transition probabilities such as a 0.025 chance of moving from Bull to Stagnant. The transition matrix is constructed accordingly.

Properties of the Transition Matrix

Using the example matrix, we start with an initial distribution (e.g., 30% Bull, 40% Bear, 30% Stagnant) and repeatedly multiply by the matrix. The following Python code performs the iteration:

<code>import numpy as np
matrix = np.matrix([[0.9,0.075,0.025],[0.15,0.8,0.05],[0.25,0.25,0.5]], dtype=float)
vector1 = np.matrix([[0.3,0.4,0.3]], dtype=float)
for i in range(100):
    vector1 = vector1 * matrix
    print("Current round:", i+1)
    print(vector1)
</code>

After about 60 iterations the distribution stabilizes at \([0.625, 0.3125, 0.0625]\), i.e., 62.5% Bull, 31.25% Bear, 6.25% Stagnant, regardless of the initial distribution.

Changing the initial distribution (e.g., \([0.7, 0.1, 0.2]\)) yields the same steady‑state after many iterations, as shown by the second code block and its output.

<code>matrix = np.matrix([[0.9,0.075,0.025],[0.15,0.8,0.05],[0.25,0.25,0.5]], dtype=float)
vector1 = np.matrix([[0.7,0.1,0.2]], dtype=float)
for i in range(100):
    vector1 = vector1 * matrix
    print("Current round:", i+1)
    print(vector1)
</code>

This convergence property holds for most Markov chains, both discrete and continuous, provided the chain is aperiodic and irreducible (every state can be reached from any other).

Mathematically, the steady‑state \(\pi\) satisfies \(\pi P = \pi\) and is the unique non‑negative solution of this equation.

Sampling with Markov Chains

Once the transition matrix and its stationary distribution are known, we can generate samples that follow the stationary distribution. Starting from any simple distribution (e.g., a Gaussian), we repeatedly sample the next state using the conditional probabilities defined by the matrix. After a sufficient number of steps, the collected samples approximate the target distribution, enabling Monte Carlo integration.

Input the Markov‑chain transition matrix and set the number of transition steps and desired sample size.

Sample an initial state from a simple distribution.

Iteratively sample the next state from the conditional distribution defined by the matrix.

Collect the states after the burn‑in period; these constitute samples from the stationary distribution.

In practice, constructing a transition matrix for an arbitrary target distribution is non‑trivial. Markov Chain Monte Carlo (MCMC) methods such as Metropolis‑Hastings and Gibbs sampling address this by designing transition kernels that have the desired distribution as their stationary distribution.

Source

刘建平 Pinard https://www.cnblogs.com/pinard/p/6632399.html