| rdfs:comment | - 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 proof of this is straightforward:
|
| abstract | - 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 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.
|
