Learn / Library / Expected value

Records in a shuffled list

Expected valueEasy

The numbers $1$ to $4$ are placed in a uniformly random order. An entry is a record if it is larger than every entry before it (the first entry counts). What is the expected number of records?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Each position is a record with a probability that depends only on its place.

Solution

Entry number $k$ is the largest among the first $k$ entries with probability $\frac{1}{k}$ .
By linearity the expectation is the sum of these probabilities.
It equals $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} = \frac{25}{12}$ .

Answer: $\frac{25}{12}$

Next question Back to the library