Settings
Actions
Display Options
Transition Matrix Editor
Each row must sum to 1.0 (stochastic matrix)
Probability Distribution
Convergence to Stationary Distribution
Mathematical Analysis
Current Distribution p_t
Stationary Distribution π
π satisfies π = πP
Eigenvalues of P
λ₁ = 1 is guaranteed for stochastic matrices
Chain Properties
Mixing Time Estimate
Steps to reach ε = 0.01 distance from π
Total Variation Distance
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
What is a Markov Chain?
A Markov chain is a stochastic process with the memoryless property: the future state depends only on the current state, not on the sequence of events that preceded it.
Markov Property
P(X_{t+1} | X_t, X_{t-1}, ..., X_0) = P(X_{t+1} | X_t)
Transition Formula
p_{t+1} = p_t P
where p_t is the distribution vector at time t, and P is the transition matrix
Key Concepts
- State Space S: The set of all possible states
- Transition Matrix P: P[i][j] = P(X_{t+1}=j | X_t=i)
- Stochastic Matrix: Each row sums to 1.0
- Path Probability: Product of transition probabilities along the path
Stationary Distribution π
A stationary distribution π is a probability distribution that remains unchanged in the Markov chain: once the system reaches π, it stays there forever.
Stationary Equation
π = πP
or equivalently: π(P - I) = 0
Left Eigenvector Interpretation
π is the left eigenvector of P corresponding to eigenvalue 1
πP = λπ where λ = 1
Existence and Uniqueness
- Existence: Every finite Markov chain has at least one stationary distribution
- Uniqueness: Guaranteed for irreducible chains (all states communicate)
- Perron-Frobenius: For regular chains, π has all positive entries
Total Variation Distance
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
Measures how close the current distribution is to stationary
Convergence Properties
Under what conditions does a Markov chain converge to its stationary distribution?
Chain Types
- Regular (Aperiodic + Irreducible): Converges to unique π from any starting distribution
- Periodic: States cycle through a periodic pattern
- Reducible: Contains absorbing states or multiple communicating classes
Convergence Rate
Determined by the second-largest eigenvalue magnitude (SLEM):
|p_t - π| ≈ C × |λ_2|^t
Spectral gap = 1 - |λ₂|, larger gap = faster convergence
Mixing Time
Time to get ε-close to stationary distribution:
t_mix(ε) = log(ε) / log(|λ_2|)
Periodicity Detection
A state has period d if all cycles from that state have lengths divisible by d
- Aperiodic: d = 1 (can return at any time)
- Periodic: d > 1 (cycles are synchronized)
Detailed Balance (Reversible Chains)
π(i)P(i,j) = π(j)P(j,i)
A sufficient condition for π to be stationary
Real-World Applications
PageRank Algorithm
Google's PageRank models web surfing as a random walk. The stationary distribution gives the importance of each page.
P = (1-d)M + d(1/n)J
M: link matrix, d: damping factor, J: all-ones matrix
Random Walks on Graphs
Used in network analysis, recommendation systems, and graph sampling. The stationary distribution relates to node degrees.
MCMC Sampling Methods
Markov Chain Monte Carlo methods generate samples from complex probability distributions by constructing chains with the target as stationary distribution.
- Metropolis-Hastings algorithm
- Gibbs sampling
- Boltzmann machines
Hidden Markov Models (HMMs)
Used in speech recognition, bioinformatics, and finance. HMMs have an underlying Markov chain with hidden states.
Queueing Theory
Birth-death processes model queues. The stationary distribution gives the long-run probability of having n customers in the system.
Board Games
Games like Monopoly and Chutes & Ladders can be modeled as Markov chains to compute expected game length and visit frequencies.