You're playing pinball. When you first shoot a ball it randomly comes down through 1 of 3 gates. When you go through an unlit gate, it lights up. Similarly, a lit gate will go out. What is the expected number of balls you have to throw for all 3 gates to light up?

For example, ball A could go through gate 2, B through gate 3, and C through gate 1. This scenario took 3 rolls and has probability 1/27.

I've put serious thought into this question twice over the last couple of years but my answer gets more and more complicated until my brain explodes.

Follow up

Douglas hit the nail on the head. For kicks, here's the Python script I used as a reality check for both the 2 and 3 gate cases.

from random import randint

def pinball(gates):
    trials = []
    for trial in range(10000):
        state = [False for g in range(gates)]
        balls = 0
        while not all(state):
            gate = randint(0, len(state) - 1)
            state[gate] = not state[gate]
            balls += 1
        trials.append(1.0 * balls)
    print sum(trials) / len(trials)

  • $\begingroup$ Do you happen to be thinking of this: en.wikipedia.org/wiki/… ? $\endgroup$ – Zev Chonoles Sep 20 '10 at 21:49
  • $\begingroup$ haha I am indeed. $\endgroup$ – Dave Aaron Smith Sep 21 '10 at 0:23
  • $\begingroup$ It's a pretty common mechanic in pinball, not just Space Cadet. $\endgroup$ – Cap Khoury Sep 21 '10 at 0:39

This is the average time it takes for a random walk on the 1-skeleton of a cube to reach the opposite vertex. There are more general theories for such values, but you can determine this particular one with a simple set of linear equations. Let $T_i$ be the expected time from when $i$ lights are lit. You want to determine $T_0$.

$T_0 = 1 + T_1$

$T_1 = 1 + T_0/3 + 2T_2/3$

$T_2 = 1+ 2T_1/3 + 0$

which has the solution

$\{T_0=10, T_1=9, T_2=7\}$.

  • 3
    $\begingroup$ The result generalizes to hypercubes of dimension n with the expected time behaving like 2^n(1+1/n+O(1/n^2)) $\endgroup$ – Alex R. Sep 20 '10 at 21:41
  • $\begingroup$ How did you find the system of linear equations? I can't seem to understand them intuitively. I'm happy you can do it this way as trying to add it up combinatorially just wasn't working. $\endgroup$ – Dave Aaron Smith Sep 21 '10 at 0:40
  • 2
    $\begingroup$ Dave: for the first equation, note that when all lights are unlit, it will invariably take one round for the first light to be lit, after which we expect T_1 rounds before all lights are lit. For the second equation, when one light is lit, after one round with are either in the situation of having 0 lights lit (with probability 1/3) or 2 lights (probability 2/3). Etc. I hope that helps at least a little. I encourage you to try it for 2 lights if you're still shaky about the details. $\endgroup$ – Eric Tressler Sep 21 '10 at 1:11
  • $\begingroup$ OK, I think I get it now. For 2 lights, it's 4. That's from the linear equations T_0 = 1 + T_1 and T_1 = 1 + .5 T_0 + .5 T_2 and T_2 = 0. $\endgroup$ – Dave Aaron Smith Sep 21 '10 at 15:47

After 3 balls you are either at all lit up, or 1 lit up. Hand calculations give these probabilities at 2/9ths and 7/9ths respectively. If you throw another ball you can't be all lit up, so throw 2 more in. There are 9 ways these 2 balls can land. 3 of these options will take all lit up to all lit up (namely they both fall in the same hole) and 2 of these options will take 1 lit up to all lit up (they fall in one whole then the other - both ways round). And as there are either all lit up or 1 lit up at this stage this is all that can happen.

So if the probability of all lit up at the one possible time is p, then at the next possible time is 3p/9 + 2(1-p)/9 = p+2/9

this value converges on a quarter as (1/4 + 2)/9 = (9/4)/9 = 1/4


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.