Brief
Say a city numbers its taxis 1, 2, 3 and so on up to some unknown N. You spot a handful of them, and the largest number you have seen is 60. How many taxis are there? At least 60, obviously. Probably not 10,000. Bayes' rule turns that intuition into a full distribution over N. This is the same problem the Allies faced estimating German tank production from serial numbers.
If you saw distinct numbers, each set of out of was equally likely, so the likelihood is for (your largest number) and zero below. With a flat prior up to a large cap, the posterior is for . Here you can compute that exactly on a grid, which gives you a reference answer to test a sampler against.
The sampler is Metropolis, the simplest Markov chain Monte Carlo (MCMC) method. From the current , propose a nearby and accept it with probability . Only the ratio appears, so you never need the normalising constant. Run it long enough and the share of time the walk spends at each matches the posterior. In one dimension the grid is easier. Learn MCMC here, where you can check it, because with many unknowns a grid is impossible and sampling is all you have.
DATA · numbers you collect
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- The Metropolis posterior mean is within 1% of the exact grid mean on your data. Record the gap with `python tools/mlarena.py record BM-29 "<relative difference>"`.
- The sample histogram lies on top of the grid posterior, and the trace plot shows no drift after burn-in.
- On 200 simulated cities, the 90% interval contains the true N about 90% of the time.
Side quests
Terms in plain words
- Markov chain Monte Carlo (MCMC)
- Drawing samples from a distribution by running a random walk whose long-run share of time in each state equals that distribution.
- Metropolis sampler
- Propose a nearby state; always move if it is more probable, otherwise move with probability equal to the ratio of the two probabilities.
- Burn-in
- The first part of a chain, thrown away because it still depends on where the walk started.
- Trace plot
- The sampled value plotted against step number. A healthy chain looks like a fuzzy band with no drift.
- Acceptance rate
- The share of proposals the sampler accepts. Too high means steps are too small; too low means they are too big.