a (biased) game of war

Here was the problem that took up half our class time today trying to solve (time well spent, I believe): Two players, Alexa and Beatrice, take turns drawing cards from a deck. The first one to draw an ace wins. Alexa draws first. What is the probability Alexa wins?

This problem could be solved with a naïve view of probability, but because I assigned it in order for the class to practice using modern definitions, I’d like to spell those out. First, a sample space is the set $S$ of all possible outcomes of a given experiment (here, the game). A subset of the sample space is called an event. (One might think of an “event“ as “all the possible ways the experiment can succeed,” for whatever definition of “success” we might like.) A probability measure on $S$ is a function that takes each event $E$ and assigns to it a number $P(E)$ with the following properties:

• For every event $E$, $0 \le P(E) \le 1$.
• $P(S) = 1$ (I think of this as the statement “whenever you perform the experiment, something happens.”)
• If $E_1$, $E_2$, $E_3$, …, is any sequence of mutually exclusive events (meaning that $E_i \cap E_j = \varnothing$ whenever $i \ne j$), then \[ P \left( \bigcup_{i=1}^\infty E_i \right) = \sum_{i=1}^\infty P(E_i). \] (Note that this still holds if the sequence only has finitely many events; for example, if $E$ and $F$ are mutually exclusive, then $P(E \cup F) = P(E) + P(F)$.)

(This definition works fine if $S$ is finite; if $S$ is uncountably infinite, then we have to be more careful about what kinds of events we can allow. But in our situation $S$ is finite, so no worries.) This is the modern, axiomatic view of probability, essentially as formulated by Kolmogorov. (If you haven’t read Slava Gerovitch’s recent, excellent article on Kolmogorov’s life, you should.) The key realization is that the probability of an event is not given a priori; we must always make assumptions about the likelihood of an event.

The first question that arises in analyzing the game between Alexa and Beatrice is therefore, What is the sample space? That is, what are the possible outcomes? The students in my probability class came up with essentially three possibilities:

1. The set “Alexa wins on her $n$th draw, or Beatrice wins on her $n$th draw“.
2. The set of all sequences of cards drawn from a deck, with the last card drawn an ace.
3. The set of all possible orderings of the 52 cards in the deck.

In class, I added the following analysis of these choices:

1. This is the simplest description of the set of possible outcomes; one is only concerned with who won, and at which point in the game she won.
2. This is the most “natural” (i.e., experiential) description of the possible outcomes; one pays attention only to which cards appear in the course of the game.
3. This is the most “equitable” description of possible outcomes; we generally assume that, if the deck has been well-shuffled, then all orderings are equally likely.

(One could add the set of outcomes, “Alexa wins” or “Beatrice wins”, as a potential choice of sample space, but I had already suggested to the students that it is worthwhile to consider when a particular player wins.) Another way to distinguish the third choice of sample space from the first two is philosophical: is the experiment done when the players have finished drawing cards, or before that, when the deck is placed in front of them? After all, once the deck is shuffled and laid down, if one knows the order of the cards, then one knows who will win. One student delivered a description of how to find the probability that Alexa wins, when the sample space is chosen to be “all possible orderings of the deck”: \[ P(\text{Alexa wins}) = \frac{\#(\text{orderings in which the first ace appears in an odd position})} {\#(\text{possible orderings of the whole deck})}. \] The denominator equals, of course, 52!. Counting the numerator then becomes the challenge. It is equivalent to the solution proposed below.

A useful approach, applicable to many situations, is to think about the sequence of events, “Alexa wins on her first turn“, “Alexa wins on her second turn“, etc. These events are clearly mutually exclusive: if Alexa wins after drawing her seventh card, then the game is over, and she won’t win after drawing ten cards. So if we can find the probability of each of these events, then we can add them up to find the total probability that Alexa wins.

Finding the probability that Alexa wins on the first turn is straightforward enough; she just has to draw an ace from the deck. This will happen with probability 4/52 = 1/13.

Finding the probability that Alexa wins on her second turn is a bit trickier, but contains the germ of the complete solution. First, she must draw anything but an ace; the probability of this is 48/52. Then Beatrice must draw anything but an ace; since Alexa has already drawn one card, the probability of this is 47/51. Then Alexa draws an ace; with only 50 cards remaining, her chances are 4/50. Thus the probability she wins after drawing two cards is (48/52)(47/51)(4/50).

Now we can see how the general case works: in order for Alexa to win on her $n$th turn, she and Beatrice must each have drawn $(n-1)$ cards that are not aces, and Alexa must draw an ace after that. The probability of this happening is $\frac{48}{52}\cdot\frac{47}{51}\cdot\frac{46}{50} \cdots \frac{48-2n+1}{52-2n+1}\cdot\frac{4}{52-2n+2}$ (as long as $n > 1$).

How many turns must we consider? Well, suppose all four aces were at the end of the deck. Then Alexa and Beatrice would each draw 24 cards before reaching an ace, and Alexa would win on her 25th turn. The probability of this happening is \[ \frac{48!4!}{52!} = \frac{1}{270\,725} \approx 0.0000037, \] since the 48 non-aces can appear in any order, followed by the four aces. Thus we need to add together the probability that Alexa wins on each of her 25 (potential) turns to get the total probability that she wins.

Before we compute this total, what do we think the result should be? Does Alexa have a greater chance of winning than Beatrice, or the reverse? Or are their chances equal? The students came up with the following arguments:

• Alexa has more potential turns than Beatrice—25 as opposed to 24, because Beatrice could never win on her 25th—so Alexa is more likely to win. (Given how small is the probability that Alexa wins on her 25th turn, I find this argument not very convincing.)
• Each time Beatrice draws a card, she has fewer cards to choose from, but the same number of aces, so her likelihood of drawing an ace at each turn is greater than Alexa’s, and she has a better chance of winning. (This, however, disregards the sequence of events necessary for Beatrice to have the opportunity to draw.)
• As previously mentioned, we just want to know how likely it is that the first ace appears in an odd position. It seems that there should be no preference for the first ace to appear in an odd versus an even position, so the two players have equal chances of winning. (This does make sense to me, intuitively, but there’s something skewed about the “first ace” that makes it questionable. As we’ll see, the computations do not bear this estimation out, but they nearly do.)

Apparently, Alexa’s advantage in drawing first has the potential to be balanced out by Beatrice’s greater chance of drawing an ace due to the reduced number of cards in the deck on her turn.

I don’t know how to resolve this philosophical conundrum without actually doing the computation, so here goes. With a bit of reindexing, the probability that Alexa wins can be computed by the sum \[ \sum_{N=0}^{24} \frac{48!}{(48-2N)!}\cdot\frac{(52-2N)!}{52!}\cdot\frac{4}{52-2N} \] (here $N$ is the number of turns that have elapsed before Alexa draws her $(N+1)$st card). Using Wolfram|Alpha, we find that this sum is about 0.5198. Therefore Alexa has a small but clear advantage. In fact, her chances of winning are better than the house’s chances of winning at French roulette if you, the gambler, bet on all reds, which is 19/37, or about 0.5135. We can check our work (i.e., do we have the right formula?) by applying similar reasoning to compute Beatrice’s chances of winning as \[ \sum_{N=0}^{23} \frac{48!}{(48-2N-1)!}\cdot\frac{(52-2N-1)!}{52!}\cdot\frac{4}{52-2N-1}, \] which is about 0.4802, as we would expect.

I have two lingering questions about this scenario:

• Is there a way to determine that the first player has an advantage in the game without doing the full computation? That is, can one provide a “rigorous” (but not overly computational) argument that Alexa will win more than half the time?
• The probability that the first player wins in this game must necessarily be a rational number, because it is a finite sum of rational numbers. As it turns out, this fraction is exactly 433/833, which has a remarkably small denominator (especially considering that the last term in the sum is 1/270725). Is the number 833 intrinsically meaningful in this situation, or is this a coincidence?

Comments are welcome.

Added 9/12: I have made perhaps a small step towards understanding heuristically why the first player should have a small advantage. Suppose instead of the winner being the first one to draw an ace, it is the first one to draw the ace of spades. Then the players have equal chances: a specific card is equally likely to be in either an even or odd position. Now suppose that the winning condition is to draw a red card; then the first player already has 1/2 probability of winning on her first turn, apart from any advantage she has later in the game. It seems plausible that if the winning condition depends on drawing one of $k$ designated cards before the other player does, then the first player’s probability of winning is an increasing function of $k$, reaching probability 1 when $k$ is 52 (i.e., the winning condition is “draw a card”). I may get around to calculating how the answer varies with $k$.