Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Polya's Urn Process

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.

Previous Puzzle: Horses on Auction

You are the chief guest at an auction, where an unknown number of horses will be revealed and auctioned, one after the other, randomly permuted. You are a connoiseur of horses, and can judge whether one horse is 'better' than another. Being the chief guest, you have a one-time privilege of selecting a horse, after it is revealed, but before it gets auctioned off. You get to keep this horse for yourself. Your objective is to maximize the probability of selecting the best horse. One strategy is to pick the first horse. Can you do any better?

An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix?

12 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.