Markov Chains

Grinstead & Snell · GFDL · PDF

A Markov chain is a random process where the next state depends only on the current state, not the history. The transition matrix P encodes all the dynamics. Multiply P by itself to see the future. Ergodic chains converge to a unique stationary distribution.

Transition matrix

A Markov chain on states 1, …, n is defined by its transition matrix P, where Pᵢⱼ = P(next state = j | current state = i). Each row sums to 1. The state after k steps: multiply the initial distribution by Pᵏ.

Scheme

; Markov chain: transition matrix as list of rows
; P[i][j] = probability of going from state i to state j

; Weather: S=sunny(0), R=rainy(1)
; P = [[0.7, 0.3],
;      [0.5, 0.5]]

(define P '((0.7 0.3)
            (0.5 0.5)))

; Matrix-vector multiply: next distribution from current
(define (mat-vec-mul mat vec)
  (map (lambda (row)
    (let loop ((r row) (v vec) (s 0))
      (if (null? r) s
          (loop (cdr r) (cdr v) (+ s (* (car r) (car v)))))))
    mat))

; Transpose for left-multiply: dist * P = P^T * dist
(define (transpose mat)
  (apply map list mat))

(define (step dist P)
  (mat-vec-mul (transpose P) dist))

; Start sunny, evolve
(define d0 '(1.0 0.0))
(define d1 (step d0 P))
(define d2 (step d1 P))
(define d10 (let loop ((d d0) (i 0))
  (if (= i 10) d (loop (step d P) (+ i 1)))))

(display "day 0: ") (display d0) (newline)
(display "day 1: ") (display d1) (newline)
(display "day 2: ") (display d2) (newline)
(display "day 10: ") (display d10) (newline)
; Converges to stationary distribution (5/8, 3/8)

; Markov chain: transition matrix as list of rows
; P[i][j] = probability of going from state i to state j

; Weather: S=sunny(0), R=rainy(1)
; P = [[0.7, 0.3],
;      [0.5, 0.5]]

(define P '((0.7 0.3)
            (0.5 0.5)))

; Matrix-vector multiply: next distribution from current
(define (mat-vec-mul mat vec)
  (map (lambda (row)
    (let loop ((r row) (v vec) (s 0))
      (if (null? r) s
          (loop (cdr r) (cdr v) (+ s (* (car r) (car v)))))))
    mat))

; Transpose for left-multiply: dist * P = P^T * dist
(define (transpose mat)
  (apply map list mat))

(define (step dist P)
  (mat-vec-mul (transpose P) dist))

; Start sunny, evolve
(define d0 '(1.0 0.0))
(define d1 (step d0 P))
(define d2 (step d1 P))
(define d10 (let loop ((d d0) (i 0))
  (if (= i 10) d (loop (step d P) (+ i 1)))))

(display "day 0: ") (display d0) (newline)
(display "day 1: ") (display d1) (newline)
(display "day 2: ") (display d2) (newline)
(display "day 10: ") (display d10) (newline)
; Converges to stationary distribution (5/8, 3/8)

Stationary distribution

A distribution π is stationary if πP = π. It is a left eigenvector of P with eigenvalue 1. For an ergodic chain (irreducible and aperiodic), the stationary distribution is unique, and every initial distribution converges to it. This is the ergodic theorem.

Scheme

; Find stationary distribution by solving pi * P = pi
; For 2x2: pi = (p, 1-p) where p = P[1][0] / (P[0][1] + P[1][0])

(define p01 0.3) ; S -> R
(define p10 0.5) ; R -> S

(define pi-sunny (/ p10 (+ p01 p10)))
(define pi-rainy (/ p01 (+ p01 p10)))

(display "stationary: (") (display pi-sunny)
(display ", ") (display pi-rainy) (display ")") (newline)
; (0.625, 0.375)

; Verify: pi * P = pi
(define (dot a b)
  (let loop ((a a) (b b) (s 0))
    (if (null? a) s (loop (cdr a) (cdr b) (+ s (* (car a) (car b)))))))

(define pi-vec (list pi-sunny pi-rainy))
(define col0 (list 0.7 0.5))
(define col1 (list 0.3 0.5))
(display "pi*P = (") (display (dot pi-vec col0))
(display ", ") (display (dot pi-vec col1)) (display ")")
; Should equal pi itself

Absorbing chains

A state is absorbing if, once entered, the chain never leaves. An absorbing chain has at least one absorbing state and every state can reach one. The key question: starting from a transient state, how many steps until absorption? The fundamental matrix N = (I − Q)⁻¹ answers this, where Q is the submatrix of transitions among transient states.

Scheme

; Absorbing chain: gambler with $2, wins or loses $1
; States: 0 (broke=absorbing), 1, 2, 3 (rich=absorbing)
; P(up) = P(down) = 0.5

; Q = transitions among transient states (1 and 2)
; Q = [[0, 0.5],
;      [0.5, 0]]

; N = (I - Q)^(-1) = fundamental matrix
; I - Q = [[1, -0.5], [-0.5, 1]]
; det = 1 - 0.25 = 0.75
; N = (1/0.75) * [[1, 0.5], [0.5, 1]]

(define det 0.75)
(define N00 (/ 1 det))
(define N01 (/ 0.5 det))
(define N10 (/ 0.5 det))
(define N11 (/ 1 det))

; Expected steps to absorption = row sums of N
(define from-1 (+ N00 N01))
(define from-2 (+ N10 N11))

(display "from state 1: ") (display from-1) (display " steps") (newline)
(display "from state 2: ") (display from-2) (display " steps") (newline)
; Both: 2 expected steps

; Absorption probabilities: B = N * R
; R = [[0.5, 0], [0, 0.5]] (prob of going to absorbing states)
(define b10 (* N00 0.5))  ; from 1, absorbed at 0
(define b13 (* N01 0.5))  ; from 1, absorbed at 3
(display "from 1: P(ruin)=") (display b10)
(display ", P(win)=") (display b13) (newline)
; P(ruin from 1) = 2/3, P(win from 1) = 1/3

; Absorbing chain: gambler with $2, wins or loses $1
; States: 0 (broke=absorbing), 1, 2, 3 (rich=absorbing)
; P(up) = P(down) = 0.5

; Q = transitions among transient states (1 and 2)
; Q = [[0, 0.5],
;      [0.5, 0]]

; N = (I - Q)^(-1) = fundamental matrix
; I - Q = [[1, -0.5], [-0.5, 1]]
; det = 1 - 0.25 = 0.75
; N = (1/0.75) * [[1, 0.5], [0.5, 1]]

(define det 0.75)
(define N00 (/ 1 det))
(define N01 (/ 0.5 det))
(define N10 (/ 0.5 det))
(define N11 (/ 1 det))

; Expected steps to absorption = row sums of N
(define from-1 (+ N00 N01))
(define from-2 (+ N10 N11))

(display "from state 1: ") (display from-1) (display " steps") (newline)
(display "from state 2: ") (display from-2) (display " steps") (newline)
; Both: 2 expected steps

; Absorption probabilities: B = N * R
; R = [[0.5, 0], [0, 0.5]] (prob of going to absorbing states)
(define b10 (* N00 0.5))  ; from 1, absorbed at 0
(define b13 (* N01 0.5))  ; from 1, absorbed at 3
(display "from 1: P(ruin)=") (display b10)
(display ", P(win)=") (display b13) (newline)
; P(ruin from 1) = 2/3, P(win from 1) = 1/3

Notation reference

Textbook	Scheme	Meaning
Pᵢⱼ	(list-ref (list-ref P i) j)	Transition probability i → j
πP = π	(dot pi-vec col)	Stationary distribution
N = (I − Q)⁻¹	fundamental matrix	Expected visits to transient states
Pᵏ	(loop ... (step d P) ...)	k-step transition matrix

Neighbors

Probability chapters

🎰 Ch 12 — Random Walks (Markov chains on the integers)
🎰 Ch 4 — Conditional Probability (the Markov property is a conditional independence statement)
🤖 ML Ch.10 — sequence models extend Markov chains with learned transitions
🏛️ Soar — cognitive cycles have a Markov structure
⚙ Algorithms Ch.7 — shortest paths on graphs generalize Markov chain state transitions

Connections

🍞 Fritz 2020 — Markov categories: the abstract structure where Markov chains live as morphisms
🍞 Staton 2025 — probabilistic programming composes Markov kernels the same way
Panangaden 2009 — labelled Markov processes: continuous-state generalization with bisimulation
Markov chain
Absorbing Markov chain

Translation notes

The weather example is a 2-state ergodic chain. Real Markov chains can have hundreds of states, but the algebra is the same: matrix powers for multi-step transitions, eigenvector for stationary distribution. The absorbing chain computation uses the fundamental matrix, which the textbook derives via geometric series: N = I + Q + Q² + … = (I − Q)⁻¹. Fritz 2020 shows that the Markov property (future independent of past given present) is exactly the composition law in a Markov category.

Ready for the real thing? Read Chapter 11 of Grinstead & Snell.

The Handshake

← Generating Functions by june.kim Random Walks →