Web Simulation 

 

 

 

 

Markov Chain Tutorial 

This interactive tutorial demonstrates Markov Chains, a fundamental mathematical model for systems that transition between discrete states based on probabilistic rules. The key insight is that the next state depends only on the current state, not on the history of how we got there—this is called the Markov Property (or "memoryless" property).

The simulation visualizes the connection between the abstract mathematics (transition matrices) and a concrete visual (state diagrams). Watch as the system "rolls dice" to determine which state to visit next, and observe how the long-run statistics converge to the steady-state distribution!

What is a Markov Chain?

A Markov Chain is a stochastic process that transitions between a finite set of states according to fixed probabilities. Formally:

P(Xn+1 = j | Xn = i, Xn-1, ..., X0) = P(Xn+1 = j | Xn = i) = pij

This says: "The probability of going to state j depends ONLY on being in state i right now, not on the entire history."

The Transition Matrix

All transition probabilities are organized in a transition matrix P:

P = [pij] where pij = P(Xn+1 = j | Xn = i)

Key properties of the transition matrix:

  • Each row sums to 1: Σj pij = 1 (probabilities must sum to 1)
  • All entries are non-negative: pij ≥ 0
  • Rows represent "from" states, columns represent "to" states

Steady-State Distribution

After many transitions, a Markov Chain often converges to a steady-state (stationary) distribution π:

π = πP (or equivalently: πj = Σi πi pij)

The steady-state π is an eigenvector of PT with eigenvalue 1. It represents the long-run fraction of time spent in each state!

Mathematical Foundation

Multi-Step Transitions: The probability of going from state i to state j in exactly n steps is given by:

P(Xn = j | X0 = i) = (Pn)ij

This means: "Raise the matrix to the n-th power to find n-step transition probabilities."

Convergence Theorem: For a finite, irreducible, aperiodic Markov Chain:

limn→∞ Pn = �  where each row of �  equals π

Regardless of the starting state, the chain converges to the same steady-state distribution.

 

Markov Chain Controls
800ms
STATE DIAGRAM
TRANSITION MATRIX P
VISIT STATISTICS
STEADY STATE π (theoretical)
Current State: A
Total Steps: 0
HOW NEXT STATE IS DETERMINED
Click Step ▶ or Run to see the decision process
STATE TRANSITION HISTORY (last 50)
VISIT STATISTICS TRAJECTORY
Steps → Dashed lines show theoretical steady state π
Current State (glowing)
Transition Probability
Traveling Packet

 

Usage Guide

Follow these steps to explore Markov Chain dynamics:

  1. Initial View: When you first load the simulation, you'll see:
    • A state diagram showing circular nodes (states A, B, C) connected by color-coded arrows
    • A transition matrix where you can edit probabilities
    • Visit statistics showing how often each state has been visited
    • The steady-state distribution (theoretical long-run probabilities)
    • A decision panel showing how each transition is determined
    • A trajectory graph showing visit statistics over time
  2. Click "Step ▶": Execute one forward step. Watch the decision panel show:
    • Which probability row is used (based on current state)
    • The random number generated (0.0 to 1.0)
    • A visual number line showing which state "wins"
    A glowing packet then travels along the chosen arrow to the destination.
  3. Click "◀ Step": Go back one step. This undoes the last transition and restores the previous state, useful for examining specific transitions.
  4. Click "Run": Start continuous auto-run. The button changes to "Stop". Watch the trajectory graph as visit statistics converge toward the steady-state!
  5. Edit the Matrix: Click any cell in the transition matrix and change the probability. The diagram updates immediately:
    • Arrow color matches the source state (Red from A, Green from B, etc.)
    • Arrow thickness reflects probability (thicker = more likely)
    • Colored pill labels show the exact probability value
    • Row sums must equal 1.0 (shown in Σ column—click "Normalize Rows" to fix)
  6. Try Different Presets:
    • Simple 3-State: Basic example to understand the mechanics
    • Weather Model: Sunny ↔ Cloudy ↔ Rainy transitions (with emoji states!)
    • Gambler's Ruin: Classic absorbing chain ($0 and $3 are absorbing states)
    • PageRank: Simplified web page ranking model (4 states)
  7. Watch the Trajectory Graph: The bottom graph shows visit percentage for each state over time:
    • Solid lines: Actual visit percentages (empirical)
    • Dashed lines: Theoretical steady-state π values
    • Watch lines converge—this demonstrates the Law of Large Numbers!

Key Insight: The trajectory graph visually demonstrates convergence. After many steps, the solid lines (empirical) approach the dashed lines (theoretical steady state π)!

Understanding the Visualization

The State Diagram

Each circle represents a state in the Markov Chain. Arrows show possible transitions:

  • Arrow color: Matches the source state (e.g., arrows from A are red, from B are green)
  • Arrow direction: Points from "current state" to "next state"
  • Arrow curvature: Uses "Right-Hand Rule"—A→B and B→A curve in opposite directions to avoid overlap
  • Arrow thickness: Proportional to transition probability (thicker = higher probability)
  • Pill labels: Color-coded backgrounds showing exact probability (e.g., "0.50" = 50% chance)
  • Self-loops: Circular arrows pointing outward mean "stay in the same state"
  • Golden glow: Indicates the current state with animated border
  • Traveling packet: Golden dot that follows the curved arrow path during transitions
The Transition Matrix

The matrix P contains all transition probabilities:

  • Rows: Represent the "from" state (current state)
  • Columns: Represent the "to" state (next state)
  • Cell pij: Probability of going from state i to state j
  • Σ column: Shows row sum (must equal 1.0 for valid matrix)
Matrix ↔ Diagram Connection
TRANSITION MATRIX
A B
A 0.3 0.7
B 0.4 0.6
pAB = 0.7 → 70% chance A→B
⟺
STATE DIAGRAM
A
B
0.7
Row A, Column B in matrix = Arrow from A to B in diagram

The Simulation Algorithm

Here's how the "Step" function determines the next state—using weighted random choice:

Step 1: Get Probabilities for Current State

Look up the row in the transition matrix corresponding to the current state:

Step 1: Select Probability Row
If current state is A, use row A:
A B C
A 0.2 0.5 0.3
B 0.1 0.6 0.3
C 0.4 0.2 0.4
probabilities = [0.2, 0.5, 0.3]
Step 2: Roll Random Number & Accumulate

Generate a random number r between 0 and 1, then find which "region" it falls into:

Step 2: Weighted Random Selection
A
B
C
20%
50%
30%
0.0
0.2
0.7
1.0
r = 0.63
Example: r = 0.63
A: 0.0 – 0.2 → 0.63 > 0.2 ❌
B: 0.2 – 0.7 → 0.63 ≤ 0.7 ✓ Winner!
C: 0.7 – 1.0 → (not checked)
Result: Transition to state B
The Algorithm in Code
// Weighted Random Choice Algorithm
1. Get probabilities for current state: row = P[currentState]
2. Roll random number: r = Math.random() // 0.0 to 1.0
3. Accumulate probabilities until r is exceeded:
accumulated = 0
for each state j:
  accumulated += row[j]
  if (r ≤ accumulated) → nextState = j; break
4. Transition: currentState = nextState

Key Insight: States with higher probabilities have proportionally larger "regions" on the number line and are more likely to be chosen. This is how the computer "rolls weighted dice"!

The Decision Panel

The simulation includes a "How Next State is Determined" panel that shows this algorithm in action for each step:

  • Step 1: Shows the current state and its probability row from the matrix
  • Step 2: Displays the random number r that was generated
  • Step 3: Visual number line with colored segments and the r marker showing which state "wins"
  • Result: The chosen next state highlighted in green

This panel updates in real-time with each step, making the weighted random choice algorithm completely transparent!

The Trajectory Graph

The bottom panel shows a line graph of visit statistics over time, demonstrating convergence:

  • Solid colored lines: Empirical visit percentages for each state
  • Dashed colored lines: Theoretical steady-state π values
  • X-axis: Number of steps (time)
  • Y-axis: Percentage (0% to 100%)

As you run more steps, watch the solid lines approach the dashed lines—this visually demonstrates the Law of Large Numbers and convergence to the stationary distribution!

Key Concepts

The Markov Property (Memorylessness)

The defining feature: future depends only on present, not past. No matter how you arrived at state B, the probabilities for leaving B are always the same. This makes Markov Chains mathematically tractable and computationally efficient.

Steady-State Distribution

The vector π such that πP = π. It represents:

  • The long-run fraction of time spent in each state
  • The probability distribution that the system converges to
  • An eigenvector of PT with eigenvalue 1

Watch the simulation: after many steps, the visit statistics approach the theoretical steady state!

Types of States
State Type Definition Example
Transient May never be visited again after leaving Starting state in some chains
Recurrent Will definitely be visited again (eventually) States in the steady-state
Absorbing Once entered, cannot leave (pii = 1) $0 and $3 in Gambler's Ruin
Chain Properties
Property Meaning Importance
Irreducible Can reach any state from any other state Guarantees unique steady state
Aperiodic No fixed cycle length for returning Guarantees convergence
Ergodic Both irreducible AND aperiodic Pn → steady state matrix

Applications of Markov Chains

Domain Application States Represent
Web Google PageRank Web pages; transitions = links
NLP Text generation, autocomplete Words; transitions = word sequences
Finance Credit ratings, stock models Rating levels; transitions = upgrades/downgrades
Biology DNA sequence analysis Nucleotides (A, T, G, C)
Games Board games, gambling analysis Game positions or chip counts
Physics Particle diffusion, queuing Positions or queue lengths
ML Hidden Markov Models, MCMC Latent variables

Calculating Steady State

For a 2-state chain, the steady state can be solved analytically:

P = [1-a, a; b, 1-b] → π = [b/(a+b), a/(a+b)]

For larger chains, we use:

  • Power Iteration: Repeatedly multiply π by P until convergence
  • Eigenvalue Decomposition: Find eigenvector with eigenvalue 1
  • Linear System: Solve πP = π with constraint Σπi = 1

Presets Explained

Weather Model

A classic example: tomorrow's weather depends only on today's:

  • ☀️ Sunny: 70% stays sunny, 20% becomes cloudy, 10% becomes rainy
  • ☁️ Cloudy: 30% becomes sunny, 40% stays cloudy, 30% becomes rainy
  • 🌧️ Rainy: 20% becomes sunny, 30% becomes cloudy, 50% stays rainy
Gambler's Ruin

Classic absorbing chain: a gambler with $1-$2 bets $1 per round:

  • $0 (Broke): Absorbing state—game over!
  • $1, $2: 50% chance to win $1, 50% chance to lose $1
  • $3 (Rich): Absorbing state—goal reached!

Question: Starting with $1, what's the probability of reaching $3 vs $0?

PageRank

Simplified web graph: pages link to each other, creating transition probabilities:

  • Random surfer clicks links with equal probability
  • Steady state = importance score of each page
  • This is the foundation of Google's original algorithm!

Controls Reference

Control Function
Preset Load pre-configured example chains (Simple, Weather, Gambler's Ruin, PageRank)
States Change the number of states (2, 3, or 4)
◀ Step Go back one step (undo last transition)
Step ▶ Execute one forward step with full decision visualization
Run / Stop Toggle continuous auto-run mode
Reset Clear all statistics, history, and trajectory graph
Speed Adjust animation speed (100ms–2000ms per step)
Normalize Rows Scale all matrix rows to sum to 1.0
Matrix cells Click to edit transition probabilities directly

Visual Panels

Panel Description
State Diagram Interactive graph with color-coded arrows showing transition probabilities
Transition Matrix Editable probability matrix with row sum validation
Visit Statistics Bar chart showing percentage of visits to each state
Steady State π Theoretical long-run distribution (calculated via power iteration)
Decision Panel Shows step-by-step how each transition is determined (probability row, random number, winner selection)
Transition History Sequence of last 50 visited states
Trajectory Graph Line graph showing visit statistics over time with steady-state reference lines (dashed)

Limitations and Extensions

  • Discrete time: This simulation uses discrete steps. Continuous-time Markov Chains exist for modeling events that happen at random times.
  • Finite states: We limit to 4 states for visualization clarity. Real applications may have millions of states.
  • Homogeneous: Transition probabilities don't change over time. Non-homogeneous chains have time-varying P(t).
  • Observable states: States are directly visible. Hidden Markov Models (HMMs) have latent states with observable emissions.
  • Ergodic assumption: The steady-state calculation assumes the chain is ergodic (irreducible + aperiodic). Absorbing chains like Gambler's Ruin don't have a traditional steady state.