Best Out of Infinity/Trivia

The idea of Best Out of Infinity suggests to a certain kind of person an interesting pair of questions.

First, supposing every game had even odds (e.g. if it was just flipping a coin), and supposing that there's no time limit, what are the odds that Alice, who keeps upping the number of games, will eventually "win"?

Nope, not a trick question: she will, eventually, win. Which leads to the second question: how long will it take, on average? More formally, what is the expected value of the number of games played when Alice wins?

The answer is forever, infinite. Most games^[1] end in under four games, but at every point the 50% of the time Alice loses will add much, much more time than the 50% of time she wins can save.

The proof of this is straightforward:

• Call the expected number of games remaining for Alice to win from an N game deficit D(N). (That is: if she is down N games, we expect D(N) additional games for her to catch up.) Note that this allows us to express the original question as, "Calculate D(0)".
• Note that D(-1) = 0. (If Alice is up one game, she's won.)
• Note that each game has two equal possibilities (1/2 chance): she wins, putting her N-1 games down, or she loses, putting her N+1 games down. Either way, this adds one game to the count. Thus, mathematically: D(N) = 1 + 0.5*D(N-1) + 0.5*D(N+1).
• Calculate.
  • D(0) = 1 + (1/2)*D(-1) + (1/2)*D(1) = 1 + (1/2)*D(1)
    • D(1) = 1 + (1/2)*D(0) + (1/2)*D(2)
  • Substituting: D(0) = 1 + 1/2 + (1/4)*D(0) + (1/4)*D(2)
    • D(2) = 1 + (1/2)*D(1) + (1/2)*D(3) = 1 + 1/2 + (1/4)*D(0) + (1/4)*D(2) + (1/2)*D(3)
    • Rearranging: D(2) = 2 + (1/3)*D(0) + (2/3)*D(3)
  • Substituting: D(0) = 1 + 1/2 + (1/4)*D(0) + 1/2 + (1/12)*D(0) + (1/6)*D(3)
  • Rearranging: D(0) = 1 + 1/2 + 1/2 + (1/4 + 1/12)*D(0) + (1/6)*D(3)
    • D(3) = 1 + (1/2)*D(2) + (1/2)*D(4) = 1 + 1 + (1/6)*D(0) + (1/3)*D(3) + (1/2)*D(4)
    • Rearranging: D(3) = 3 + (1/4)*D(0) + (3/4)*D(4)
  • Substituting: D(0) = 1 + 1/2 + 1/2 + 1/2 + (1/4 + 1/12 + 1/24)*D(0) + (1/8)*D(4)

...at which point the pattern should be obvious: each additional term, when expanded in this fashion, adds 1/2 to the constant, which therefore must increase without bound. Proving this directly is, of course, trivial.

If we've bored you with enough math for now, return to main page.

1. ↑ 62.5%