MCMC Island Hopping: An Intuitive Guide to the Metropolis-Hastings Algorithm

Imagine you're a politician touring a chain of islands. Each island has a different population, and you want to spend time on each island in proportion to its population — more time on crowded islands, less on quiet ones. The catch: you have no map. You can only see the island you're on and the one next door. This is the core idea behind the Metropolis-Hastings algorithm, one of the most important algorithms in computational statistics. By the end of this post, you'll understand how a simple random walk can recover any target distribution, and you'll implement it from scratch. The algorithm was originally developed for simulating equations of state in physics by Metropolis et al. (1953) , and later generalised by Hastings (1970) . The Problem You have a target distribution — a list of values representing how much time you should spend at each location. In our island example, the populations are: Island 0 1 2 3 4 5 6 Population 2 3 1 5 8 2 9 You want to generate samples from this distri