Expected number of updates during scanning of all permutations of $n$ distinct numbers

Question

Consider the problem of computing the minimum of a set of $\mathbf{n}$ distinct numbers. We choose a permutation uniformly at random ($i.e$ each of $n!$ permutations of $\langle1,2,\ldots, n\rangle$ is chosen with probability $\frac{1}{n!}$) and we inspect the numbers in the order given by the permutation.

We maintain a variable $MIN$ that holds the minimum value seen so far. $MIN$ is initialized to $\infty$, and if we see a value smaller than $MIN$ during the scan, then $MIN$ is updated. For example, in the inspection given by the following sequence, $MIN$ is updated $4$ times. $$\underline{5}\ ,9,\underline{4}\ ,\underline{2}\ ,6,8,\underline{0}\ ,3,1,7$$

What is the expected number of times $MIN$ is updated ?

$5$ choices are given as follows:

$i)\ \ \ \ \ O(1)\ i.e\ constant\\ii)\ \ \ \ H_n=\sum_{i=1}^{n} \frac{1}{i}\\iii)\ \ \sqrt n\\iv)\ \ \frac{n}{2}\\v)\ \ \ \ n$

Answer 1

Let $1\leqslant k\leqslant n$. The variable MIN is updated when looking at the $k$th number if and only if this $k$th number is the smallest one of the $k$ initial ones. By symmetry, this happens with probability $\frac1k$.

Thus the mean number of times MIN is updated is $H_n=\sum\limits_{k=1}^n\frac1k$.

One might keep in mind that $H_n$ the $n$th harmonic number is equivalent to $\log n$ when $n\to\infty$.

Answer 2

Maybe they were looking for a recurrence here. Say $M_n$ is the expected value. Then we have the recurrence $$M_n = \frac{1}{n}\times (1+M_{n-1}) + \frac{n-1}{n} \times M_{n-1}.$$ This is because $n$ contributes an update to $M_n$ iff it is at the front of the permutation, which has probability $1/n.$ This simplifies to $$M_n = \frac{1}{n} + \left(\frac{1}{n}+\frac{n-1}{n}\right)M_{n-1} = \frac{1}{n} + M_{n-1}.$$ Now use the fact that $M_1=1$ to conclude that $$M_n = \sum_{k=1}^n \frac{1}{k} = H_n.$$