Quant Notebook
Quant interview toolkit · order statistics

Finding the maximum: count “all at most k”, then subtract

4 min readprobabilityorder statisticsexpectationinterview prep

“What is the chance the largest of 3 dice is a 5?” Asking for exactly 5 directly is messy. Asking for at most 5 is one line. This page shows why, and how to get the distribution, the expected value and the minimum from that one idea.

1P(max⁡≤k)=P(X1≤k) P(X2≤k)⋯P(Xn≤k)=F(k)nP(\max \le k) = P(X_1 \le k)\,P(X_2 \le k)\cdots P(X_n \le k) = F(k)^n “The biggest is at most k” means “every one is at most k”. Independent, so multiply.
2P(max⁡=k)=P(max⁡≤k)−P(max⁡≤k−1)P(\max = k) = P(\max \le k) - P(\max \le k-1) Everything at most k, minus the cases where nobody actually reached k.
3E[max⁡]=∑kP(max⁡≥k)or∫(1−F(x)n) dxE[\max] = \sum_k P(\max \ge k) \quad\text{or}\quad \int \big(1 - F(x)^n\big)\,dx The tail-sum shortcut. You never need step 2 for the mean.
4P(min⁡≥k)=P(all≥k)=(1−F(k−1))nP(\min \ge k) = P(\text{all} \ge k) = \big(1 - F(k-1)\big)^n The minimum is the mirror image: “the smallest is at least k” means “every one is at least k”.
Example 1 · two dice

Why “≤” is easy and “=” is not

Roll two dice. “max = 4” means at least one die shows 4 and neither is above 4. Counting that directly needs care: (4, anything ≤ 4), (anything ≤ 4, 4), minus the double-counted (4, 4). Instead, look at the picture. The event max ≤ k is a k × k square in the corner. The event max = k is the L-shaped strip between two squares.

Showk =4

Slide k from 1 to 6. The orange strip always has k² − (k−1)² = 2k − 1 cells, so P(max = k) = (2k − 1)/36: 1, 3, 5, 7, 9, 11 out of 36. Bigger values are more likely to be the maximum, which makes sense: a 6 only needs one die to show it.

Example 2 · n dice

The CDF staircase: each jump is P(max = k)

With n dice, P(max ≤ k) = (k/6)ⁿ. Plot it and you get a staircase from 0 to 1. Step 2 of the recipe says the height of the jump at k is exactly P(max = k). As n grows, the staircase stays near zero and then jumps late: with many dice, the maximum is almost surely a 6.

Number of dice n
P(max ≤ k), the staircaseP(max = k), the jump at k
P(max = 6)
most likely max
E[max]
Expected value

E[max] without the distribution: the tail-sum trick

You can always do E[max] = Σ k · P(max = k). But for any random variable that takes values 1, 2, 3, … there is a faster route:

E[X]=P(X≥1)+P(X≥2)+P(X≥3)+⋯E[X] = P(X \ge 1) + P(X \ge 2) + P(X \ge 3) + \cdots

Why: a value of X = 4 gets counted once in each of P(X ≥ 1), P(X ≥ 2), P(X ≥ 3), P(X ≥ 4), so it contributes 4 · P(X = 4). And P(max ≥ k) = 1 − P(max ≤ k−1) comes straight from step 1.

Two dice

E[max⁡]=∑k=16[1−(k−16)2]=6−0+1+4+9+16+2536=6−5536=16136≈4.47\begin{aligned} E[\max] &= \sum_{k=1}^{6} \left[1 - \left(\tfrac{k-1}{6}\right)^2\right] \\ &= 6 - \tfrac{0+1+4+9+16+25}{36} \\ &= 6 - \tfrac{55}{36} = \tfrac{161}{36} \approx 4.47 \end{aligned}

n dice, in general

E[max⁡]=6−0n+1n+⋯+5n6nE[\max] = 6 - \frac{0^n + 1^n + \cdots + 5^n}{6^n}

n = 3 gives 6 − 225/216 ≈ 4.96. n = 4 gives ≈ 5.24. Check these against the cards above.

Sanity check that interviewers love

For two dice, max + min = X + Y, so E[max] + E[min] = 7. That gives E[min] = 7 − 161/36 = 91/36 ≈ 2.53 for free. If your two answers don’t add to 7, something is wrong.

Example 3 · continuous

Max of n uniforms on [0, 1]

Same recipe. For U(0,1), P(U ≤ x) = x, so P(max ≤ x) = xⁿ. In the continuous case there is no “k − 1” to subtract. The difference turns into a derivative: the density is the slope of the CDF.

Fmax⁡(x)=xnfmax⁡(x)=n xn−1E[max⁡]=∫01(1−xn) dx=nn+1F_{\max}(x) = x^n \qquad f_{\max}(x) = n\,x^{n-1} \qquad E[\max] = \int_0^1 (1 - x^n)\,dx = \frac{n}{n+1}
n =3

CDF: P(max ≤ x) = xⁿ

Density: n·xⁿ⁻¹

A good way to remember n/(n+1): n random points cut [0, 1] into n + 1 gaps, and by symmetry every gap has the same average length 1/(n+1). The max sits one gap below 1, and the min sits one gap above 0, so E[min] = 1/(n+1).

The minimum

Min works the same way, from the other end

For the max you ask “is everything below?”. For the min you ask “is everything above?”.

Discrete (dice)

P(min⁡≥k)=(7−k6)nP(min⁡=k)=P(min⁡≥k)−P(min⁡≥k+1)E[min⁡]=∑k=16(7−k6)n\begin{aligned} P(\min \ge k) &= \left(\tfrac{7-k}{6}\right)^n \\ P(\min = k) &= P(\min \ge k) - P(\min \ge k+1) \\ E[\min] &= \sum_{k=1}^{6} \left(\tfrac{7-k}{6}\right)^n \end{aligned}

Continuous

P(min⁡>x)=(1−F(x))nFmin⁡(x)=1−(1−F(x))nU(0,1): E[min⁡]=1n+1\begin{aligned} P(\min > x) &= \big(1 - F(x)\big)^n \\ F_{\min}(x) &= 1 - \big(1 - F(x)\big)^n \\ U(0,1):\ E[\min] &= \tfrac{1}{n+1} \end{aligned}

Switch the first grid to min to see it: min ≥ k is a square in the opposite corner, and min = k is again an L-shaped strip.

Where people slip in interviews

  • Not identical? Still multiply, just with different CDFs. Max of a die and a U(0,6): P(max ≤ x) = (⌊x⌋/6)·(x/6).
  • Without replacement? No independence, so count instead. Draw 3 cards from 1–10: P(max ≤ k) = C(k,3)/C(10,3). The subtraction step still works.
  • Off by one in the min. For dice P(min ≥ k) uses 7 − k, not 6 − k. Check k = 1: it must give 1.
  • “At least one 6” is P(max = 6) = 1 − (5/6)ⁿ. Same trick, different words.
  • Continuous “=”. P(max = 0.7) is 0. Questions ask for the density or a range instead.
Practice

Try these before you open the answer

Warm-upRoll 3 dice. What is P(max = 4)?
Show answer
P(max⁡≤4)−P(max⁡≤3)=43−3363=64−27216=37216≈0.171P(\max \le 4) - P(\max \le 3) = \frac{4^3 - 3^3}{6^3} = \frac{64 - 27}{216} = \frac{37}{216} \approx 0.171
Warm-upRoll 4 dice. What is the chance at least one shows a 6?
Show answer
P(max⁡=6)=1−(56)4=6711296≈0.518P(\max = 6) = 1 - \left(\tfrac{5}{6}\right)^4 = \frac{671}{1296} \approx 0.518

This is the classic de Méré bet, slightly better than even.

ExpectationRoll 2 dice. What is E[min]? Do it with the tail sum.
Show answer
E[min⁡]=∑kP(min⁡≥k)=36+25+16+9+4+136=9136≈2.53E[\min] = \sum_k P(\min \ge k) = \frac{36 + 25 + 16 + 9 + 4 + 1}{36} = \frac{91}{36} \approx 2.53

And 161/36 + 91/36 = 252/36 = 7, matching E[X + Y].

InterviewYou may roll a die n times and keep the highest roll. What is the smallest n with E[max] above 5?
Show answer
n=3:6−225216≈4.958n=4:6−9791296≈5.245\begin{aligned} n = 3:&\quad 6 - \tfrac{225}{216} \approx 4.958 \\ n = 4:&\quad 6 - \tfrac{979}{1296} \approx 5.245 \end{aligned}

So n = 4. Each extra roll helps less, because the max can never pass 6.

ContinuousDraw n independent U(0,1). What is the expected range, E[max − min]?
Show answer
nn+1−1n+1=n−1n+1\frac{n}{n+1} - \frac{1}{n+1} = \frac{n-1}{n+1}

For n = 2 that is 1/3, a common one-liner: the expected distance between two random points on a stick.

ContinuousTwo independent U(0,1). What is P(max > 0.8)? What is the density of the max at 0.5?
Show answer
P(max⁡>0.8)=1−0.82=0.36fmax⁡(0.5)=2⋅0.5=1P(\max > 0.8) = 1 - 0.8^2 = 0.36 \qquad f_{\max}(0.5) = 2 \cdot 0.5 = 1
Without replacementPick 3 different numbers from 1 to 10 at random. What is P(largest is 7)?
Show answer
(73)−(63)(103)=35−20120=18\frac{\binom{7}{3} - \binom{6}{3}}{\binom{10}{3}} = \frac{35 - 20}{120} = \frac{1}{8}

Same subtraction, but counting replaces multiplying. Direct check: 7 must be picked, plus 2 of the 6 numbers below it, C(6,2) = 15.

StretchX ~ Exp(λ) and Y ~ Exp(μ) are independent. What is the distribution of min(X, Y)?
Show answer
P(min⁡>t)=P(X>t) P(Y>t)=e−λt e−μt=e−(λ+μ)tP(\min > t) = P(X > t)\,P(Y > t) = e^{-\lambda t}\,e^{-\mu t} = e^{-(\lambda+\mu)t}

So min(X, Y) ~ Exp(λ + μ), with mean 1/(λ + μ). This is why “first of several independent alarms to ring” problems are easy.

Every number on this page is computed exactly from the formulas shown, except the random draw in Example 3.