Reservoir Sampling

A stream of items flows past you, one at a time. The stream has unknown length — it might end after 10 items or after a billion. You have memory for exactly one item at a time.

After the stream ends, you must produce one item, chosen uniformly at random from all items that came through.

How do you do it?