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 . 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?

### Like this:

Like Loading...

*Related*

So, as long as p is greater than .5, I think the expected number of games played in a session is one. I’m having a little more difficulty with the distribution… I think the negative binomial distribution gets me part of the way there, i.e. it tells me the probability of x loses before r wins for x+r games. I’m stumped on where to go after that.

You’re right that the problem falls apart if p is 1/2 or less. However, the expected number of games does depend on p; i.e., it’s only equal to 1 if p=1, and is larger for smaller p. For an example that hopefully isn’t too much of a spoiler, when p=0.6 the expected number of games is 5. (Or perhaps I have unclearly specified the original problem; can you verify this experimentally via simulation?)

To put it formally, I think what you’re looking for is a probability mass function f(n|p)=Probability that you will play exactly n games given p, or the cumulative mass function, F(n|p) = Probability that you will play at least n games.

Through simulation, I got an average of 5 games played for p=0.6. And while developing the simulation I discovered, by accidentally typing a “”, that when p is less than .5, I’d have to wait a very, very long time for the simulation to complete.

I’m still working on the equation for f(n|p)… if there’s no closed form for this, you could save me a lot of time by telling me now =).

Good– I just wanted to be sure that we weren’t accidentally solving different problems. And I’m not a sadist :); there is a nice closed form solution, both for the pdf as well as the expected value. (Actually, the expected value has a particularly nice “direct” derivation, but it can also be simplified from the infinite summation that you get from the pdf.) If there is interest, I can re-post with a complete solution in a week or two.

Alright, I think I’ve got the pdf, f(n|p)=C((n-1)/2) * p^ceil(n/2) * (1-p)^floor(n/2), for n=1,3,5,…, where C(k) is the Catalan number sequence, and f(n|p) is 0 for odd values of n, assuming you would keep playing if you were tied.

So I cheated a little bit, I used my simulation results to back out what the first few coefficients would be (assuming I had the p^ceil(n/2) * (1-p)^floor(n/2) part right), a little google searching on these numbers led me to [ http://oeis.org/A000108 ]. I’d be interested to see your complete solution, I’m not sure I appreciate the derivation of the coefficients.

**correction** f(n|p) is zero for even values of n

Cool! The Catalan numbers are one of the two nice “nuggets” of mathematics in this problem. The other is the tools involved in rolling up that infinite summation into a simple expression (in terms of p) for the expected value. I’ll post the solution soon with a few different derivations.

Pingback: Probability Puzzle Solution | Possibly Wrong