The postman who likes full boxes
A postman delivers 10 letters into two letter boxes. The first two letters go one into each box. Each later letter goes into a box with probability proportional to the number of letters already in it: with 3 letters in one box and 1 in the other, the next letter goes to the first box with probability .
Find the expected number of letters in the box that ends up with fewer letters (if both end with 5, count 5).
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
This is Pólya's urn. Find the distribution of the number of letters in the first box at the end.
Show that every sequence of placements with the same final counts has the same probability.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Pólya's urn started with one ball of each colour gives a uniform final count: the first box ends with letters for each with probability . Then the expectation of the smaller count is an average of nine numbers.
Step 1: one sequence. After the first two letters, 8 more are placed. Take any order in which of them go to the first box and to the second. The probabilities of the placements in the first box have numerators (the box holds 1, then 2, ... letters), those in the second box , and the denominators are always . So the sequence has probability
Step 2: count. There are such orders, so The first box ends with letters, uniform on .
Step 3: the smaller box. It holds : about 2.78.
For many letters. With letters, the share of the first box tends to a uniform random number on , so the smaller box gets about letters on average. Small early differences get locked in.