[Math] Expected sum of cards until first Ace

card-gamesprobabilityprobability theorystatistics

I came across this question while preparing for an interview.

You draw cards from a $52$-card deck until you get first Ace. After each card drawn, you discard three cards from the deck. What's the expected sum of cards until you get the first Ace?

Note

  1. J, Q, K have point value 11, 12 and 13, and Ace has point value 1

  2. discarded cards don't count towards the sum and if we don't get an Ace we shuffle the deck and continue

  3. when you shuffle, you shuffle all cards but you keep the sum, and when you draw a new card you add it to that sum (you don't start from zero after each shuffle)

My thought so far: the expected sum is definitely between $73$ and $91$.

$73$ is the expected sum if we don't discard any cards, so the problem simply becomes the expected sum until first Ace, that is, $(2+\dots+13) \cdot 4 \cdot \frac{1}{5}+1$.

$91$ is the expected sum if we discard all $51$ remaining cards (shuffle the deck after each draw). In this case the number of draws needed to see the first Ace follows a Geometric distribution, so the answer is $(\frac{52}{4}-1) \cdot 7.5+1$

Any help is appreciated!!!

Best Answer

At each step, four cards are removed from the deck, so a deck is exhausted in $13$ steps. Let's call that a 'round'.

The game you propose can be restated as follows. At each round, we draw $13$ ordered cards from the deck, and add up the values of the cards that came before the first ace in our $13$ drawn cards. If no ace is drawn, we add up the values of all $13$ drawn cards, shuffle them into the remaining $39$ cards (the ones which were not drawn), and repeat the process.


There are $\binom{48}{13}$ sets of $13$ cards which do not contain an Ace, and so there are $\binom{52}{13}-\binom{48}{13}$ sets of $13$ cards which contain at least one Ace. Hence, the probability that the game ends in a given round is

$$p=1-\frac{\binom{48}{13}}{\binom{52}{13}}=\frac{14498}{20825}\simeq69.62\%$$


Now, if the game has not ended in a given round, then the expected sum of the cards drawn is $13$ times the expected value of a card drawn (by linearity of the expectation). Since no card drawn was an ace, the expected value of a card drawn is

$$\frac{2+3+4+5+6+7+8+9+10+11+12+13}{12}=\frac{15}2,$$

and hence the expected sum is $l=13\cdot\frac{15}2=\frac{195}2=97.5$.


Now, we need to calculate the expected sum of the cards drawn before the first Ace in a round where the game ends. Here, we will break the thing into cases.

$\qquad$Number of Aces in cards drawn: $1$

There are $\binom{48}{12}\cdot\binom{4}{1}$ sets of $13$ cards which contain exactly one Ace. Therefore, given that the $13$ cards drawn contain at least one ace, the probability that we fall in this case (exactly one Ace drawn) is

$$a_1=\frac{\binom{48}{12}\cdot\binom{4}{1}}{\binom{52}{13}-\binom{48}{13}}=\frac{9139}{14498}\simeq 63.04\%$$

The expected position of the lone ace is $\frac{1+2+3+4+5+6+7+8+9+10+11+12+13}{13}=7$, so on average $6$ non-Ace cards will be drawn before it. The expected sum for this case is hence $s_1=6\cdot\frac{15}2+1=46$.

$\qquad$Number of Aces in cards drawn: $2$

There are $\binom{48}{11}\cdot\binom{4}{2}$ sets of $13$ cards which contain exactly two Aces. Like before, the probability that we fall in this case is

$$a_2=\frac{\binom{48}{11}\cdot\binom{4}{2}}{\binom{52}{13}-\binom{48}{13}}=\frac{2223}{7249}\simeq 30.67\%$$

Now, things get trickier. The position of the pairs of aces is a subset of size $2$ on $S=\{1,2,\dots,13\}$, and we are interested in the minimimum of this subset. Let $X$ denote this random variable.

There are $\binom{13}2$ $2$-subsets of $S$, and only $12$ of them contain the number $1$, which is a guaranteed minimum. Therefore

$$\mathbb{P}(X=1)=\frac{12}{\binom{13}2}$$

Similarly, there are $11$ $2$-subsets of $S$ whose minimum is $2$.
More generally, for each $k\in\{1,2,\dots,12\}$, $\binom{13-k}1$ of the $2$-subsets of $S$ have minimum $k$, and we find that

$$\mathbb{P}(X=k)=\frac{\binom{13-k}1}{\binom{13}2}.$$

As a sanity check, notice that they add up to $1$. The expected sum for this case is hence:

$$s_2=\sum_{k=1}^{12}\left(\frac{15}2\cdot (k-1)+1\right) \cdot \mathbb{P}(X=k)=\frac{57}2$$

$\qquad$Number of Aces in cards drawn: $3$

Now we've got most of the work done. We have that

$$a_3=\frac{\binom{48}{10}\cdot\binom{4}{3}}{\binom{52}{13}-\binom{48}{13}}=\frac{39}{659}\simeq 5.92\%$$

For this case, let $Y$ be the random variable which denotes the minimum of a uniformly sampled $3$-subset of $S$. Notice that there are $\binom{13}{3}$ $3$-subsets of $S$.

We will have that for each $k\in\{1,2,\dots,11\}$, $\binom{13-k}2$ of the $3$-subsets of $S$ have minimum $k$. Hence:

$$\mathbb{P}(Y=k)=\frac{\binom{13-k}2}{\binom{13}3}$$

Finally, the expected sum for this case is

$$s_3=\sum_{k=1}^{11}\left(\frac{15}2\cdot (k-1)+1\right) \cdot \mathbb{P}(Y=k)=\frac{79}4$$

$\qquad$Number of Aces in cards drawn: $4$

For this final case we have

$$a_4=\frac{\binom{48}{9}\cdot\binom{4}{4}}{\binom{52}{13}-\binom{48}{13}}=\frac{5}{1318}\simeq 0.38\%$$

and expected sum

$$s_4=\sum_{k=1}^{10}\left(\frac{15}2\cdot (k-1)+1\right) \cdot \frac{\binom{13-k}3}{\binom{13}4}=\frac{29}2$$


Let's put it all together. Supposing the game ends on a given round, the expected sum for that round will be $($and you can check that the $a_i$ add up to $1)$

$$w=\sum_{i=1}^4a_is_i=\frac{282424}{7249}\simeq38.96$$

Finally, the expected sum for the game will be given by

$$\sum_{n=1}^\infty\, \underbrace{\mathbb{P}(\text{Game ends on round $n$})}_{(1-p)^{n-1}\cdot p} \cdot \underbrace{\mathbb{E}(\text{Value of sum of cards of a game ending on round $n$})}_{(n-1)\,l+w}\\ =\sum_{n=1}^\infty\,(1-p)^{n-1}\cdot p \cdot \Big((n-1)\,l+w\Big)=(w-l)+\frac{l}p $$

This last step is standard manipulation of series and term-by-term differentiation, but I can further explain if it's not clear. Therefore, the final answer is

$$\frac{2363461}{28996} \simeq 81.51$$