Expected sum of cards until first Ace

Question

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!!!

Answer 1

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$$

Answer 2

Although an exact solution is complicated and worth more thoughts, I did a quick simulation which hopefully can provide some insights.

Expected sum v.s. number of cards thrown

Essentially the plot above demonstrates how the expected sum till first ACE changes with respect to the number of cards thrown after each draw. One can see that the increase is slower than linear – it might be even slightly slower than logarithm, as can be seen from the red curve.

I am also presenting the codes for the simulation in case someone else is interested in more investigation. On the other hand, I think that it will be more exciting to approach the problem exactly, for which I have an idea, but it involves very lengthy calculation that may leads to nowhere at all…

class Cards(object):

def __init__(self):
    self.c = np.asarray([4]*13) 

    ### a length-13 list containing the number of remaining cards of each number 
    ###i.e. A,2,3,...,13

    self.s = np.sum(self.c)

    self.r = np.arange(1,14)

def draw_card(self):
    if self.s <= 0: ### Enter a new deck
        self.c = np.asarray([4]*13)
        self.s = np.sum(self.c)

    card = choice( self.r, p = self.c/self.s )
    self.c[card-1] -= 1
    self.s -= 1 

    return card

def throw_cards(self,num=3):

    ### assert num > 0, "Number of cards to be thrown away is zero!"

    if num <= 0:
        return

    if self.s >= num:
        for n in xrange(num):
            card = choice( self.r, p = self.c/self.s )
            self.c[card-1] -= 1
            self.s -= 1
    else: 
        ### self.s < num; number of remaining cards < number of cards to be thrown away
        ### Enter a new deck 
        self.c = np.asarray([4]*13) 
        ### a length-13 list containing the number of remaining cards of each number i.e. A,2,3,...,13
        self.s = np.sum(self.c)
    return 

def exp_sum(self,num=3,maxiter=200):
    es = 0
    it = 0
    while it < maxiter:
        it += 1

        card = self.draw_card()
        es += card 
        if card == 1:
            break 
        else: ### card != 1
            self.throw_cards(num)

    ### Reset self.c and self.r
    self.c = np.asarray([4]*13) 
    self.s = np.sum(self.c)
    return es