Optimal strategy of a probabilistic game

combinatoricsgame theoryprobability

We have $n$ red balls and $n$ black balls in a box. We will take out a ball from the box one at a time and never put it back. Every time before we take out a ball from the box, you can decide whether to join the game or not. You will win the game if two balls of the same color are taken out consecutively after you join the game. What is your optimal strategy?

Best Answer

Your strategy doesn't matter. Consider the following alternative game: You can join whenever you want, but still draw all the balls out. You win if the final two balls are the same color. We observe:

  1. If we join the alternative game at any point, the odds of winning this game are the same as if we had joined the real game (the final two balls have the same distribution as the next two balls, given what has been drawn so far.

  2. If players A and B use the same decision rule when to join, but A joins the real game and B the alternative one, they have the same chance of winning (average the first observation over all times of joining).

  3. Player B's chance of winning in the alternative game does not change at all based on his strategy when to join, so Player A's chance can't change either.

This is a variant on the "Next Card Red" game, which is described in Peter Winkler's "Games People Don't Play "