Probability Puzzle Solution

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 p=0.55.  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 p 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 X 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 n, where we want the probability P(X=2n+1).

How does a session last exactly 2n+1 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 (l,w), each indicating the current cumulative number of losses and wins, respectively, then a session lasting exactly 2n+1 games corresponds to a lattice path from (0,0) to (n,n+1) that never extends above the diagonal w=l, with the exception of the final game from (n,n) to (n,n+1).

The number of such paths is the n-th Catalan number

c_n = \frac{1}{n+1} {2n \choose n}

Conveniently, each of these paths has the same probability of occurring.  So the desired probability distribution is given by

P(X=2n+1) = \frac{1}{n+1} {2n \choose n} p^{n+1} (1-p)^n

Now we need to compute the expected value.  Here is where generating functions are our friend.  If we temporarily substitute x=p(1-p), then we can write the expected value as

E(X) = p g(x)

where

g(x) = \sum_{n=0}^{\infty} (2n+1) c_n x^n

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,

c(x) = \sum_{n=0}^{\infty} c_n x^n = \frac{1 - \sqrt{1 - 4x}}{2x}

By distributing the (2n+1) multiplier in the expression for g(x), I will leave it as an exercise for the reader to verify that

g(x) = 2x c'(x) + c(x) = \frac{-1 + \frac{1}{\sqrt{1 - 4x}}}{2x}

Plugging x=p(1-p) back in– and not forgetting that final extra p— yields, after some tedious simplification, an expected value of 1/(2p-1).

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 v 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 p— then we’re done, with just one game played.

If it’s a loss, then with probability 1-p, 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 v.  That is,

v = p + (1-p)(1 + 2v)

Solving again yields v = 1/(2p-1).

Optimal angle on a swing

This is another interesting problem that is similar to– but slightly trickier than– the golf problem from last year.

Problem: It’s recess, and you are swinging on a playground swing set, and because it’s against playground rules and girls are watching, you want to jump off the swing.  How should you time your release (i.e., at what angle from vertical should you let go) to maximize the distance traveled before hitting the ground?

I like this problem, because there is a lot of freedom to make simplifying assumptions or not, yielding solutions ranging from complex and only numerically tractable to simpler, more elegant, and still reasonably accurate.  For example, let’s make it easier by putting the swing set on a flat moon (i.e., gravity acts directly downward with no air resistance), and you are a spherical chicken of negligible radius (i.e., a point mass) riding the swing whose seat just misses the ground when it hangs vertical, and you want to maximize the over-the-ground distance measured from that point at which the swing hangs vertical.

 

Probability Puzzle

This same problem has come up in a couple of completely unrelated contexts recently, and it seemed worth sharing here.  It has the usual “nice” properties of being approachable in several different ways, from (initial) computer simulation to (eventual) analytic solution.  Following is my attempt at re-stating the problem as a puzzle, involving neither of the original contexts:

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 p=0.55.  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?