Section 10.3

Distinct Values

The expected number of distinct outcomes (cards, floors, birthdays) in n draws, and choices that optimise it.

Toolkit

Linearity of expectation reduces “expected number of distinct values” to a sum over possible values of the indicator that each value appears at least once. For $n$ independent draws uniform over $k$ categories,

\mathbb{E}[\text{distinct values seen}] = \sum_{j=1}^k \mathbb{P}(\text{value } j \text{ appears}) = k\left(1-\left(1-\tfrac1k\right)^n\right),

since $(1-1/k)^n$ is the probability a fixed value is missed by all $n$ draws. The same indicator trick handles non-uniform or dependent setups: write the quantity as $\sum_j \mathbb{1}[\text{value }j\text{ occurs}]$ and compute $\mathbb{P}(\text{value }j\text{ occurs})$ individually, then sum — no need for joint distribution of occurrences. For optimisation questions (choosing $n$ , or splitting draws among categories), treat $k(1-(1-1/k)^n)$ as a function of the parameters and analyse monotonicity or compare marginal gains.

Problems

10.28 Elevator Stops+4 variations Easy Free