The Deranged Letters

Derangement
ProbabilityEasy

You're sending hard copies of job applications to 5 firms: Millenium, Renaissance, Citadel, Two Sigma, Jane Street. You have 5 envelopes on the table with names and addresses of these 5 firms. You also have 5 cover letters personalized to each firm. You were drunk that night and stuffed each cover letter into random envelopes.

Question: What is the probability that all 5 cover letters are mailed to the wrong firms?

Solution

We want the scenario where every letter is in the wrong envelope, This is known as a "derangement" in mathematics

Instead of directly calculating the probability of all wrong matches, it's easier to:

  1. Find the probability of at least one correct match
  2. Subtract this from 1 to get our answer

1. Setting Up the Problem

  1. Let Eᵢ be the event that letter i is in its correct envelope.
  2. We want P(no correct matches) = 1 - P(at least one correct match) = 1 - P(E₁ ∪ E₂ ∪ E₃ ∪ E₄ ∪ E₅)
  3. This is a classic application of the inclusion-exclusion principle (IEP)

2. Venn Diagram

ABCA∩BA∩CB∩CA∩B∩CP(A∪B∪C) = P(A)+P(B)+P(C)−P(A∩B)−P(A∩C)−P(B∩C)+P(A∩B∩C)

3. Applying Inclusion-Exclusion Principle

P(E1∪E2∪E3∪E4∪E5)P(E_1 \cup E_2 \cup E_3 \cup E_4 \cup E_5)=

∑i=15P(Ei)−∑i<jP(Ei∩Ej)+⋯+(−1)6P(E1∩E2∩⋯∩E5)\sum_{i=1}^5 P(E_i) - \sum_{i<j} P(E_{i} \cap E_{j}) + \cdots + (-1)^6P(E_1 \cap E_2 \cap\cdots \cap E_5)

  1. Sum of P(Ei)P(E_i) for individual events
    • Each letter has a 1/5 chance of being in the correct envelope.
    • =\inom51 imes\ rac15=1= \inom{5}{1} \ imes \ rac{1}{5} = 1
  2. Minus sum of P(Ei∩Ej)P(E_{i} \cap E_{j}) for pairs
    • There is a \ rac15 imes\ rac15−1=\ rac120\ rac{1}{5} \ imes \ rac{1}{5-1} = \ rac{1}{20} chance that both letter i and letter j have the correct envelope.
    • =\inom52 imes\ rac120=10 imes\ rac120=\ rac12=\ rac12!= \inom{5}{2} \ imes \ rac{1}{20} = 10 \ imes \ rac{1}{20} = \ rac{1}{2} = \ rac{1}{2!}
  3. Plus sum of P(Ei∩Ej∩Ek)P(E_{i} \cap E_{j} \cap E_{k}) for triples
    • There is a \ rac15 imes\ rac15−1 imes\ rac15−2=\ rac160\ rac{1}{5} \ imes \ rac{1}{5-1} \ imes \ rac{1}{5-2} = \ rac{1}{60} chance that all three letters i, j, k have the correct envelope.
    • =\inom53 imes\ rac160=10 imes\ rac160=\ rac16=\ rac13!= \inom{5}{3} \ imes \ rac{1}{60} = 10 \ imes \ rac{1}{60} = \ rac{1}{6} = \ rac{1}{3!}
  4. Minus sum of P(Ei∩Ej∩Ek∩El)P(E_{i} \cap E_{j} \cap E_{k} \cap E_{l}) for quadruples
    • There is a \ rac15 imes\ rac15−1 imes\ rac15−2 imes\ rac15−3=\ rac1120\ rac{1}{5} \ imes \ rac{1}{5-1} \ imes \ rac{1}{5-2} \ imes \ rac{1}{5-3} = \ rac{1}{120} chance that all four letters i, j, k, l have the correct envelope.
    • =\inom54 imes\ rac1120=5 imes\ rac1120=\ rac124=\ rac14!= \inom{5}{4} \ imes \ rac{1}{120} = 5 \ imes \ rac{1}{120} = \ rac{1}{24} = \ rac{1}{4!}
  5. Plus P(E1∩E2∩E3∩E4∩E5)P(E_1 \cap E_2 \cap E_3 \cap E_4 \cap E_5) for all five
    • There is a \ rac15 imes\ rac15−1 imes\ rac15−2 imes\ rac15−3 imes\ rac15−4=\ rac1120\ rac{1}{5} \ imes \ rac{1}{5-1} \ imes \ rac{1}{5-2} \ imes \ rac{1}{5-3} \ imes \ rac{1}{5-4} = \ rac{1}{120} chance that all five letters have the correct envelope.
    • =\ rac1120=\ rac15!= \ rac{1}{120} = \ rac{1}{5!}
 hereforeP(E1∪E2∪E3∪E4∪E5)=1−\ rac12!+\ rac13!−\ rac14!+\ rac15!=\ rac1930\ herefore P(E_1 \cup E_2 \cup E_3 \cup E_4 \cup E_5) = 1-\ rac{1}{2!}+\ rac{1}{3!}-\ rac{1}{4!}+\ rac{1}{5!} = \ rac{19}{30}

So the probability that all 5 letters are mailed to the wrong firms is

1−P(E1∪E2∪E3∪E4∪E5)=1−\ rac1930=\ rac1130≈0.367 extor36.7%1-P(E_1 \cup E_2 \cup E_3 \cup E_4 \cup E_5) = 1-\ rac{19}{30} = \ rac{11}{30} \approx 0.367 \ ext{ or } 36.7\%

Theoretical Probability Distribution for number of correct matches

Interactive Simulation

✓
Envelope 1
For: Millenium
Contains: Millenium
✓
Envelope 2
For: Renaissance
Contains: Renaissance
✓
Envelope 3
For: Citadel
Contains: Citadel
✓
Envelope 4
For: Two Sigma
Contains: Two Sigma
✓
Envelope 5
For: Jane Street
Contains: Jane Street
0
Total Simulations
0
All Wrong Matches
0%
Observed Probability
36.67%
Expected Probability