Fog Creek Software
Discussion Board




King for a week

A certain tropical island has a ruling system consiting of twelve counsel members. Each week one of the twelve members of the counsel is picked to be king; at the end of the week a new king is picked at random from the twelve member counsel ( Note that it is possible for the same person to be elected king again, since the choice is completely random among the twelve). Question: how many weeks would elapse, on average, before each person has been king at least once? A more difficult question would be how many weeks would have elapsed before there was at least a 50% chance that everyone has been king at least once? The first question is asking for the mean, the second for the median.

John
Saturday, February 26, 2005

Answer for the expected number of weeks is:

12*(1+1/2+1/3+....+1/12)

This is a well known problem. Google for keywords: cover time random walk complete graph

Tapori
Wednesday, March 09, 2005

*  Recent Topics

*  Fog Creek Home