This post collects a few different approaches to solving the following puzzle from last month:
Problem: My nephew and I like to play a card game together. He is slightly better at the game than I am, so that the probability that he wins any particular game is . The game does not take long to play, and so we usually play multiple games in succession, keeping track of who wins the most games.
However, my nephew likes to win, and so if at any point he has not won the most games, he wants to keep playing. If we stop as soon as he has won more games than I have, what is the expected number (or better yet, probability distribution) of games played in one session?
Solution 1: First, we can simulate playing this game rather easily (I won’t even bother with code here), and with enough samples guess that the expected number of games is exactly 10. But what if we want to understand the behavior when is closer to 1/2, say, 0.501? As the game becomes fairer, the simulation approach becomes doubly difficult: we require more time to simulate each individual session since the expected value is larger, and we also require more samples to accurately estimate the expected value because the variance is larger.
Solution 2: A “complete” solution involves first computing the probability distribution of the number of games in a session. This random variable takes on only (positive) odd integer values; however, for reasons that will be apparent shortly, it will be convenient to index the outcomes by non-negative , where we want the probability .
How does a session last exactly games? The last game must be a win, and before the last game the number of wins must not exceed the number of losses. If we represent the session as a sequence of ordered pairs , each indicating the current cumulative number of losses and wins, respectively, then a session lasting exactly games corresponds to a lattice path from to that never extends above the diagonal , with the exception of the final game from to .
The number of such paths is the n-th Catalan number
Conveniently, each of these paths has the same probability of occurring. So the desired probability distribution is given by
Now we need to compute the expected value. Here is where generating functions are our friend. If we temporarily substitute , then we can write the expected value as
Note that I didn’t bother to expand the expression for the Catalan numbers. We could attack this directly, using some binomial coefficient identities and the recurrence relation for the Catalan numbers to work out a closed form for this summation. But I took a shortcut here, using the fact that we already know the generating function for the Catalan numbers,
By distributing the multiplier in the expression for , I will leave it as an exercise for the reader to verify that
Plugging back in– and not forgetting that final extra — yields, after some tedious simplification, an expected value of .
Solution 3: Finally, we can take the “puzzle solver’s” approach, and cheat somewhat by assuming that a solution exists (i.e., in this case, that the expected value is indeed finite), and working from that assumption. Let be the desired expected value, and consider the outcome of the first game in a session. If it’s a win– which occurs with probably — then we’re done, with just one game played.
If it’s a loss, then with probability , we must (1) keep playing until we first recover our resulting single-game deficit, after which we must (2) still keep playing until we first gain a one-game advantage. The key observation is that the expected number of games required in each of these two stages of the session is . That is,
Solving again yields .