Polya's Urn Process
12 Sep 2008
Puzzle

There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the urn with fewer balls?

Source

Do not remember.

Solution

To analyze the problem, let us first understand card shuffling as follows. We start with 1 card. The second card moves to one of two "slots" chosen uniformly at random: either to the left or to the right of the card already in the shuffle. In general, the i-th card chooses one out of i slots. When all n cards are in the shuffle, we have a random permutation of cards. Now, let us see how the process of populating two urns with n balls, as outlined in the puzzle, is related to card shuffling. Imagine that the first two balls are joined with a rod. These correspond to the first card in the pile. The third ball (which corresponds to the second card) has two choices. In general, the i-th ball corresponds to card i-1 and has i-1 choices. Now, the first card could be in any position uniformly at random. This means that all configurations with a balls in the first pile and b balls in the second pile, with a + b = n, are equally likely. In other words, the following configurations of balls in the two urns are all equally likely: (1, n-1), (2, n-2), (3, n-3), ..., (n-3, 3), (n-2, 2) and (n-1, 1). It turns out that the average number of balls in the smaller urn is (n+1) / 4 if n is odd, and n2 / (4n - 4) when n is even. As n increases, both quantities converge to n/4.

Reference: George Polya, Sur quelques points de la theorie des probabilites, Annales de L'Institut, Henri Poincare 1 (1930), pages 117-161.