Analysis / 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 62.5% 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)

...a pattern appears of each additional term, when expanded in this fashion, adding 1/2 to the constant — a constant which therefore increases without bound.

That said, an appearance of a pattern, while sufficient for almost any other purpose, is hardly mathematics — fortunately, it is not too difficult to state a proof:

Trivially, observe that you win at the first game with probability 1/2 and the third with probability 3/8. Lets find the probability that you win at the (2n+3)-th game. This obviously means that you lost your first game and won the last two (otherwise you would have won already) and additionally won (n) of the remaining 2k games.

However, we also know that at no odd point, you won more of these 2n games then you lost — otherwise you would've won already — which immediately suggests that there are C_n such sequences, where C_n is the n-th Catalan Number. Each such sequence has a 2^-n-3 probability of happening.

Lets denote by P(t=n) the probability that you win at time 2n or 2n+1. From the preceding text, we know that

P(t=0) = 1/2
P(t=1) = 3/8
P(t=n, i>1) = C_n / 2ⁿ⁺¹

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), giving us:

E[t] > [1⁄8] ∑[n=1→∞] (n+1) (4ⁿ ⁄ (n√π√n))/4ⁿ > [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).

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

---