Card Game - First Ace

Editorials
1

[Jump to Topic]

Problem Statement

What is the expected number of cards that need to be turned over in a regular 52-card deck in order to see the first ace?

Solution

This problem elegantly demonstrates the power of indicator random variables and linearity of expectation. The key insight is to consider the position of each non-ace card relative to the aces.

Step 1: Set Up the Problem

In a standard 52-card deck:

  • There are 4 aces

  • There are 48 non-ace cards

We want to find the expected position of the first ace when cards are turned over sequentially.

Step 2: Define Indicator Variables

Let’s label the 48 non-ace cards as card 1, card 2, …, card 48.

For each non-ace card i (where i = 1, 2, \ldots, 48), define an indicator random variable:

X_i = \begin{cases} 1 & \text{if card } i \text{ is turned over before all 4 aces} \\ 0 & \text{otherwise} \end{cases}

Step 3: Express the Total in Terms of Indicators

The total number of cards turned over to see the first ace can be expressed as:

X = 1 + \sum_{i=1}^{48} X_i

The “1” accounts for the first ace itself. The sum counts how many non-ace cards appear before the first ace.

Step 4: Apply Linearity of Expectation

By linearity of expectation:

E[X] = E\left[1 + \sum_{i=1}^{48} X_i\right] = 1 + \sum_{i=1}^{48} E[X_i]

Since X_i is an indicator variable, E[X_i] = P(X_i = 1).

Step 5: Calculate P(X_i = 1)

To find P(X_i = 1), we need to determine the probability that card i appears before all 4 aces.

Key Insight: Consider the relative ordering of card i and the 4 aces. When we randomly arrange these 5 cards (1 non-ace card + 4 aces), card i is equally likely to be in any of the 5 positions:

\text{A} \quad \text{card } i \quad \text{A} \quad \text{A} \quad \text{A}

The 5 positions are separated by the 4 aces. Card i appears before all aces if and only if it is in the first position.

Since all 5 positions are equally likely:

P(X_i = 1) = \frac{1}{5}

Therefore:

E[X_i] = \frac{1}{5}

Step 6: Compute the Final Answer

Substituting into our expression:

E[X] = 1 + \sum_{i=1}^{48} \frac{1}{5} = 1 + 48 \cdot \frac{1}{5} = 1 + 9.6 = 10.6

Alternatively, as a fraction:

E[X] = 1 + \frac{48}{5} = \frac{5 + 48}{5} = \frac{53}{5}

Final Answer

The expected number of cards that need to be turned over to see the first ace is 10.6 or \frac{53}{5}.

Alternative Interpretation

We can think of this as: on average, you’ll see about 10.6 cards before encountering the first ace. This means:

  • Approximately 9.6 non-ace cards will appear before the first ace

  • Then the first ace appears (the “+1” in our formula)

Key Insights

  1. Indicator Variables: Using indicator variables X_i allows us to break down a complex counting problem into simpler probability calculations.

  2. Symmetry Argument: The key insight is that each non-ace card is equally likely to appear in any of the 5 positions relative to the 4 aces. This symmetry simplifies the calculation dramatically.

  3. Linearity of Expectation: Even though the X_i variables are dependent (they’re not independent), linearity of expectation still applies, making the calculation straightforward.

  4. The “+1” Term: Don’t forget to add 1 for the first ace itself! This is a common oversight.

  5. General Pattern: This technique works for any “first occurrence” problem where we want to find the expected position of the first special item among many items.

Generalization

General Problem: In a random ordering of m ordinary cards and n special cards, what is the expected position of the first special card?

Solution: Using the same indicator variable approach:

  • For each of the m ordinary cards, define X_i = 1 if card i appears before all n special cards

  • P(X_i = 1) = \frac{1}{n+1} (card i is equally likely to be in any of n+1 positions relative to the n special cards)

  • E[X] = 1 + \sum_{i=1}^{m} \frac{1}{n+1} = 1 + \frac{m}{n+1} = \frac{m + n + 1}{n+1}

For our specific problem: m = 48, n = 4:

E[X] = 1 + \frac{48}{4+1} = 1 + \frac{48}{5} = \frac{53}{5}

Alternative Derivation: Direct Counting

We can also solve this by directly computing the expected position:

Let P_k be the probability that the first ace appears at position k.

For the first ace to appear at position k:

  • The first (k-1) cards must all be non-aces

  • The k-th card must be an ace

P_k = \frac{\binom{48}{k-1}}{\binom{52}{k-1}} \cdot \frac{4}{52-(k-1)} = \frac{\binom{48}{k-1} \cdot 4}{\binom{52}{k-1} \cdot (53-k)}

Then:

E[X] = \sum_{k=1}^{49} k \cdot P_k

This is more complex but yields the same result: E[X] = \frac{53}{5}.

Numerical Verification

For a 52-card deck with 4 aces:

  • Minimum cards: 1 (if first card is an ace)

  • Maximum cards: 49 (if all 48 non-aces come first, then an ace)

  • Expected: 10.6 cards

This makes intuitive sense: with 4 aces in 52 cards, we expect roughly 1 ace per 13 cards, so the first ace should appear around position 10-11 on average.

Applications

  1. Quality Control: Expected number of items inspected before finding the first defective item

  2. Search Algorithms: Expected position of first match in random search

  3. Sampling Theory: Expected sample size before first success

  4. Card Games: Understanding probabilities in various card game scenarios

  5. Combinatorics: Pattern matching and first occurrence problems

Common Pitfalls

  1. Forgetting the “+1”: The formula is 1 + \sum E[X_i], not just \sum E[X_i]. The 1 accounts for the first ace itself.

  2. Incorrect probability: The probability is \frac{1}{n+1}, not \frac{1}{n} or \frac{1}{m+n}. There are n+1 positions (before all aces, or between/after them).

  3. Confusing with independence: The X_i are not independent, but linearity of expectation doesn’t require independence.

  4. Wrong denominator: When calculating P(X_i = 1), we consider only the relative positions of card i and the aces, not all 52 cards.

Summary

The expected number of cards to see the first ace is \frac{53}{5} = 10.6. This elegant solution uses indicator variables and the symmetry argument that each non-ace card is equally likely to appear before all aces. The key formula is E[X] = 1 + \frac{m}{n+1} where m is the number of ordinary items and n is the number of special items, demonstrating the power of linearity of expectation even when dealing with dependent indicator variables.

1 Like