A birthday cake has lit candles. At each step you pick a number uniformly at random and blow out candles. If any candles remain lit, the process repeats (using a new value of ). As a function of , what is the expected number of rounds needed to blow out all the candles?
For example, suppose the cake starts out with 14 lit candles. You roll a fair 14-sided die2 to choose a number between 1 and 14. Suppose you roll a 6. You then blow out 6 candles, leaving 8 lit candles. You now roll a fair 8-sided die; suppose you roll a 3. You blow out 3 candles, leaving 5. So you roll a fair 5-sided die. Maybe this time you actually roll a 5, so you blow out all the remaining candles and you are done. In this particular case, the whole process took three rounds; the question is to determine how many rounds it will take on average.
If one starts with lit candles, it seems clear that the average number of rounds will be less than (it would be very unlucky to roll a 1 every single time) but greater than (it is pretty lucky to roll an on the first try, although not nearly as much so as rolling all 1’s).
Have fun thinking about it. There is, in fact, a nice analytical solution, which I will explain in a future post!
US states visited: 9 (Massachusetts, Vermont, New York, Michigan, Wisconsin, Iowa, Kansas, Missouri, Arkansas); countries visited: 4 (US, Canada, Netherlands, Germany); plane flights: 10; hours of driving: 40; beds: 13; unexpected two-week detours to stay with in-laws: 1; number of days late by which the moving company delivered our belongings: 25.↩