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

where

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 .

Pingback: Probabilities in the game SET | Possibly Wrong

Pingback: Analysis of Chutes and Ladders | Possibly Wrong