← All Base Form Math projects
BM-29NOT STARTEDBASE FORM · PROBABILITYMATHPYTHON

How many taxis?

Guess how many taxis a city has from the numbers you've spotted, with a Metropolis sampler giving a full range of answers.

EST.7 h
REWARD+100 XP
AFTERoriginal

ML-ARENA BENCHMARKS

YOUR NUMBER VS THE INDUSTRY'S
METRICINDUSTRYMINE
posterior
GOAL · means within 1%
exact grid posterior—
no results yet
YOUR RESULTS

Your recorded results appear here.

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 kk distinct numbers, each set of kk out of NN was equally likely, so the likelihood is 1/(Nk)1/\binom{N}{k} for N≥mN \ge m (your largest number) and zero below. With a flat prior up to a large cap, the posterior is p(N∣data)∝(Nk)−1p(N \mid \text{data}) \propto \binom{N}{k}^{-1} for N≥mN \ge m. 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 NN, propose a nearby N′N' and accept it with probability min⁡(1,p(N′∣data)/p(N∣data))\min\left(1, p(N' \mid \text{data}) / p(N \mid \text{data})\right). 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 NN 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.

VISUALFig. 1
20 60 100 150 200 number of taxis N max seen = 60 mean ≈ 79 N below 60is impossible
Posterior for N after 5 distinct numbers with a largest of 60, using a flat prior. It is zero below 60, peaks at 60 and has a long right tail; the mean is about 79. Why it's here: Shows the cliff your sampler will keep bumping into and the tail it has to explore.
HINT · OBJECTIVE 2
Stuck? Hints stay hidden until you ask.
HINT · OBJECTIVE 4
Stuck? Hints stay hidden until you ask.

DATA · numbers you collect

Objectives

0 / 6 CLEARED

Read-only. Log in to update progress.

VICTORY CONDITIONS

  1. 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>"`.
  2. The sample histogram lies on top of the grid posterior, and the trace plot shows no drift after burn-in.
  3. On 200 simulated cities, the 90% interval contains the true N about 90% of the time.

Side quests

Compare a flat prior with a 1/N prior and see how much the answer moves with 5 numbers and with 30.
Let the numbering start at an unknown value instead of 1, and sample both unknowns with a 2D Metropolis walk.
Compare with the classic frequentist estimate m + m/k − 1 over many simulated cities.

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.