Learn / Library / Expected value

Record highs in a sequence

Expected valueHard

$8$ trades with distinct prices arrive in a uniformly random order. A trade is a record if its price is higher than all earlier prices, so the first trade is always a record. What is the expected number of records? Give a fraction a/b in lowest terms.

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

Hint

For position $k$ , only the relative order of the first $k$ prices matters. Where must the largest of them be?

Solution

Position $k$ is a record exactly when the largest of the first $k$ prices sits in position $k$ .
By symmetry, that largest price is equally likely to be in any of the first $k$ positions, so the probability is $\frac{1}{k}$ .
By linearity the expectation is $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8}$ .
Over the common denominator $840$ the numerators are $840 + 420 + 280 + 210 + 168 + 140 + 120 + 105 = 2283$ , so the sum is $\frac{2283}{840}$ .
In lowest terms this is $\frac{761}{280}$ .

Answer: $\frac{761}{280}$

Next question Back to the library