FreeProbabilityMedium

Cards Until Two Colours Remain

Asked atSusquehanna International GroupJane Street

A deck has $35$ green, $25$ blue and $40$ red cards, shuffled uniformly at random. You draw cards one at a time without replacement, and stop as soon as one colour has run out, so that only two colours are left in the deck.

(a) What is the expected number of cards left in the deck?

(b) What is the expected number of cards drawn?

Solution

Try it yourself first. Open a hint if you get stuck.

Hint 1

Don't try to find when you stop. Instead, for one card, ask: what has to happen for it to still be in the deck at the end? Then add up over all cards.

Hint 2

A green card is still in the deck exactly when all the blue cards, or all the red cards, were drawn before it. Look at that green card together with the $25$ blue cards: in a random shuffle it is equally likely to be anywhere among these $26$ cards. What is the chance it comes last?

Show solution

Step 1: When is a card still in the deck? You stop right after the last card of some colour is drawn. So a card is still in the deck exactly when some other colour was completely drawn before it. (Its own colour can't be the one that ran out, since the card itself is still there.)

So by linearity of expectation,

E[\text{cards left}] = \sum_{\text{cards}} P(\text{a whole other colour comes before this card}).

Step 2: One green card. Two things can put a green card after a whole colour:

All 25 blue cards come before it. Look only at this green card and the $25$ blue cards. In a random shuffle, the green card is equally likely to be in any of the $26$ places among them, so it is last with probability $\tfrac{1}{26}$ .
All 40 red cards come before it: probability $\tfrac{1}{41}$ , by the same argument.
Both happen, all $65$ blue and red cards before it: probability $\tfrac{1}{66}$ .

By inclusion–exclusion,

P(\text{a green card is left}) = \frac{1}{26} + \frac{1}{41} - \frac{1}{66} \approx 0.04770.

Step 3: Blue and red cards, the same way.

P(\text{a blue card is left}) = \frac{1}{36} + \frac{1}{41} - \frac{1}{76} \approx 0.03901,

P(\text{a red card is left}) = \frac{1}{36} + \frac{1}{26} - \frac{1}{61} \approx 0.04985.

Step 4: Add up over all $100$ cards.

E[\text{cards left}] \approx 35(0.04770) + 25(0.03901) + 40(0.04985) \approx 1.66951 + 0.97525 + 1.99383 \approx 4.63860.

Answers:

(a) $E[\text{cards left}] \approx 4.63860$ .

(b) Every card is either drawn or left, so $E[\text{cards drawn}] = 100 - 4.63860 \approx 95.36140$ .

In general, with $g$ , $b$ and $r$ cards of the three colours,

E[\text{cards left}] = g\Big(\tfrac{1}{b+1} + \tfrac{1}{r+1} - \tfrac{1}{b+r+1}\Big) + b\Big(\tfrac{1}{g+1} + \tfrac{1}{r+1} - \tfrac{1}{g+r+1}\Big) + r\Big(\tfrac{1}{g+1} + \tfrac{1}{b+1} - \tfrac{1}{g+b+1}\Big).

Why so few cards are left: each colour's last card is usually near the bottom of the deck, so even the first colour to run out does so late.

Question

Solution