lotus

previous page: 96 combinatorics/coinage/impossible.p
  
page up: Puzzles FAQ
  
next page: 98 combinatorics/full.p

97 combinatorics/color.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

97 combinatorics/color.p


An urn contains n balls of different colors. Randomly select a pair, repaint
the first to match the second, and replace the pair in the urn. What is the
expected time until the balls are all the same color?

combinatorics/color.s

(n-1)^2.

If the color classes have sizes k1, k2, ..., km, then the expected number of
steps from here is (dropping the subscript on k):

     2               k(k-1)              (j-1) (k-j)
(n-1)  -  SUM      ( ------  +   SUM   --------------- )
         classes,      2        1<j<k      (n-j)
      class.size=k

The verification goes roughly as follows. Defining phi(k) as (k(k-1)/2 +
sum[j]...), we first show that phi(k+1) + phi(k-1) - 2*phi(k) = (n-1)/(n-k)
except when k=n; the k(k-1)/2 contributes 1, the term j=k contributes
(j-1)/(n-j)=(k-1)/(n-k), and the other summands j<k contribute nothing.
Then we say that the expected change in phi(k) on a given color class is
k*(n-k)/(n*(n-1)) times (phi(k+1) + phi(k-1) - 2*phi(k)), since with
probability k*(n-k)/(n*(n-1)) the class goes to size k+1 and with the same
probability it goes to size k-1. This expected change comes out to k/n.
Summing over the color classes (and remembering the minus sign), the
expected change in the "cost from here" on one step is -1, except when we're
already monochromatic, where the handy exception k=n kicks in.

One can rewrite the contribution from k as

   (n-1) SUM (k-j)/(n-j)
        0<j<k

which incorporates both the k(k-1)/2 and the previous sum over j.
That makes the proof a little cleaner.

 

Continue to:













TOP
previous page: 96 combinatorics/coinage/impossible.p
  
page up: Puzzles FAQ
  
next page: 98 combinatorics/full.p