Solution: 2022 Winter Final - 24

Author: Michiel Smid

Question

Let $n\ge 2$ be an integer and let $x_1,\ldots,x_n$ be a random permutation of $\{1,\ldots,n\}$. Define the random variable \[ I=\min\left(\{n+1\}\cup\{i\ge 2:x_i > x_1\}\right) \enspace . \] What is $ E(I)$?

(a)

$n/2$

(b)

$H_n$

(c)

$H_{n-1}$

(d)

$H_{n+1}$

(e)

$3$

Solution

The notation is a little rough, but from what I understand this is a simpler explanation:

$I$ = the minimum value from the following permutation of values:
- The set containing the $n + 1$ value.
- The set from a permutation of values $x_1, x_n$ where a value after the 1st value is larger than the 1st value.

So the expected value that we are trying to find, is the expected value from this set, containing two “parts”. \ \

We know that $n + 1$ cannot be the minimum value unless we have a permutation where $x_1$ is the largest number and every number after it is smaller than

The probability that the 1st number is the “minimum” value is: $\frac{1}{i}$, where $2 \leq i \leq n$. \ \