2
$\begingroup$

The title is a reformulation of a game that is played as follows:

Before you are six light bulbs (all start turned off). You repeatedly roll a fair six-sided die and each time you roll a number you flip the switch of the corresponding switch, turning it on if it's off, and off if it's on.

What is the expected number of rolls it will take until every light bulb is turned on?

Note: I am not just asking "What is the expected number of rolls until each number has been rolled?", as this question has already been asked and answered many times here.

$\endgroup$
  • 1
    $\begingroup$ Did you set up the standard Markov chain approach? IE apply the linearity of iterated expectation. $\endgroup$ – Calvin Lin May 19 at 3:49
  • 1
    $\begingroup$ @CalvinLin I see that this is a seven-state absorbing Markov chain, but I don't understand what is meant by "the linearity of iterated expectation." Please explain or furnish a link. Thanks. $\endgroup$ – saulspatz May 19 at 5:27
  • $\begingroup$ @saulspatz See Christian's solution - IE $ e_ 0 = 1 + 1 e_1$. $\endgroup$ – Calvin Lin May 19 at 19:34
  • $\begingroup$ @CalvinLin That's how I did it too. I just hadn't heard the term, I guess. $\endgroup$ – saulspatz May 19 at 20:15
  • $\begingroup$ @saulspatz Yea, it's an "obvious" thing especially once you've seen it used several times before. Ah, it's actually known as the Law of Iterated Expection (and several other variants), as opposed to my phrase "linearity of iterated expectation" (though that describes it so much better IMO). $\endgroup$ – Calvin Lin May 19 at 20:19
6
$\begingroup$

Denote by $e_k$ $\>(0\leq k\leq 5)$ the expected number of additional moves when there are $k$ bulbs alight. One then has equations like $$e_5=1+{5\over6}e_4,\quad e_4=1+{1\over3}e_5+{2\over3}e_3,\quad\ldots,\quad e_0=1+1\,e_1\ .$$ Solving this system gives $e_0={416\over5}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.