8.1 Good King Markov and His island kingdom

Good King Markov and his island kingdom provide an intuitive metaphor for MCMC. The king visits islands with probabilities proportional to their population, creating a Markov chain that, in the long run, reflects the distribution of interest.

8.1.1 The Metropolis algorithm

King Markov rules a chain of 10 islands. The populations are different on each island. The king wants to spend time on each island proportional to its population, but he does not know the total population — he only knows the relative population of neighboring islands.

The Metropolis algorithm solves this:

Propose: Randomly propose to move to a neighboring island.
Accept/Reject: If the proposed island has a larger population, accept. If smaller, accept with probability equal to the ratio of populations.
Repeat: Over many steps, the fraction of time spent on each island converges to the population proportions.

# Good King Markov: Metropolis algorithm on 10 islands
set.seed(42)

# Island populations (unnormalized)

populations <- c(5, 12, 3, 8, 20, 15, 7, 10, 4, 6)
n_islands <- length(populations)

# Metropolis algorithm

n_steps <- 10000
current <- 1 # start at island 1
visits <- numeric(n_steps)

for (t in 1:n_steps) {

# Propose a neighboring island

proposal <- current + sample(c(-1, 1), 1)

# Wrap around

if (proposal < 1) proposal <- n_islands
if (proposal > n_islands) proposal <- 1

# Accept or reject

accept_prob <- min(1, populations[proposal] / populations[current])
if (runif(1) < accept_prob) {
current <- proposal
}
visits[t] <- current
}

# Compare visited frequencies to true proportions

visited_freq <- table(visits) / n_steps
true_prop <- populations / sum(populations)

cat("Island Visited True\n")
for (i in 1:n_islands) {
cat(sprintf(" %2d %.3f %.3f\n", i, visited_freq[i], true_prop[i]))
}

# Plot

barplot(rbind(visited_freq, true_prop), beside = TRUE,
col = c("steelblue", "firebrick"),
main = "King Markov: visited frequency vs true proportion",
xlab = "Island", ylab = "Proportion")
legend("topright", legend = c("Visited", "True"), fill = c("steelblue", "firebrick"))

Click Run to execute this code in your browser with WebR

8.1.2 Why it works

The Metropolis algorithm works because it satisfies detailed balance:

$\pi(x) \cdot T(x \to x') = \pi(x') \cdot T(x' \to x)$

where $\pi$ is the target distribution and $T$ is the transition probability. This ensures that the chain is reversible and converges to the target distribution.

# Verify detailed balance for the Metropolis algorithm
# For two neighboring islands i and j:
# pi(i) * T(i->j) = pi(j) * T(j->i)

populations <- c(5, 12, 3, 8, 20, 15, 7, 10, 4, 6)

# Check islands 4 and 5

i <- 4; j <- 5
pi_i <- populations[i]
pi_j <- populations[j]

# T(i->j) = min(1, pi_j/pi_i) * 0.5 (0.5 = prob of proposing j from i)

# T(j->i) = min(1, pi_i/pi_j) * 0.5

T*ij <- min(1, pi_j / pi_i) * 0.5
T*ji <- min(1, pi_i / pi_j) * 0.5

cat("Detailed balance check (islands 4 and 5):\n")
cat(" pi(4) _ T(4->5) =", pi_i _ T*ij, "\n")
cat(" pi(5) * T(5->4) =", pi*j * T*ji, "\n")
cat(" Equal?", abs(pi_i * T*ij - pi_j * T_ji) < 1e-10, "\n")

Click Run to execute this code in your browser with WebR

Rethinking

The king does not need to know the total population. The remarkable thing about the Metropolis algorithm is that it only needs the ratio of populations, not the absolute values. This is why MCMC works for Bayesian inference: we only need the ratio of posterior probabilities (likelihood times prior), not the normalizing constant. The king's algorithm is the foundation of all MCMC methods, from the simple Metropolis to the sophisticated Hamiltonian Monte Carlo.

Summary of Section 8.1

The Metropolis algorithm samples from a distribution by proposing moves and accepting/rejecting based on the ratio of probabilities.
It satisfies detailed balance, ensuring convergence to the target distribution.
It only needs ratios of probabilities, not the normalizing constant.
This is the foundation of all MCMC methods.

Practice

Markov chain Monte Carlo