Trivia: Best Out of Infinity
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^{note } 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.
It's not difficult to prove that this is the case; if, just playing around with the numbers, one follows the following line of reasoning:
- 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)
- D(0) = 1 + (1/2)*D(-1) + (1/2)*D(1) = 1 + (1/2)*D(1)
P(t=0) = 1/2
P(t=1) = 3/8
P(t=n, i>1) = C_{n} / 2^{n+1}
Now the expected value (mean) of this distribution is 1/8 (3 + sum[1->inf] (n+1) 4^{-n} C_{n}). Now it turns out that the Catalan Numbers grow like 4^{n} ⁄ (n√π√n), giving us:
P(t=1) = 3/8
P(t=n, i>1) = C_{n} / 2^{n+1}
E[t] > [1⁄8] ∑[n=1→∞] (n+1) (4^{n} ⁄ (n√π√n))/4^{n} > [1⁄(8√π)] sum[n=1→∞] n ⁄ (n√n) = [1⁄(8√π)] sum[n=1→∞] 1⁄√n
Which diverges (for example by comparison with the harmonic series).