3
$\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$
5
  • 1
    $\begingroup$ Did you set up the standard Markov chain approach? IE apply the linearity of iterated expectation. $\endgroup$
    – Calvin Lin
    Commented May 19, 2020 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
    Commented May 19, 2020 at 5:27
  • $\begingroup$ @saulspatz See Christian's solution - IE $ e_ 0 = 1 + 1 e_1$. $\endgroup$
    – Calvin Lin
    Commented May 19, 2020 at 19:34
  • $\begingroup$ @CalvinLin That's how I did it too. I just hadn't heard the term, I guess. $\endgroup$
    – saulspatz
    Commented May 19, 2020 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
    Commented May 19, 2020 at 20:19

1 Answer 1

Reset to default
7
$\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}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .