Source: TIFR 2014
Consider the problem of computing the minimum of a set of $n$ distinct numbers. We choose a permutation uniformly at random (i.e., each of the $n!$ permutations of $\langle 1,....,n\rangle$ is chosen with probability $(1/n!)$ and we inspect the numbers in the order given by this 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 our inspection, then MIN is updated. For example, in the inspection given by the following sequence, MIN is updated four times.
$$5\ 9\ 4\ 2\ 6\ 8\ 0\ 3\ 1\ 7$$
What is the expected number of times MIN is updated?
My Approach: We can use conditional expectation here to arrive.Let the expectation of finding the minimum of $n$ numbers be $E(X_n)$. $X_n$ is a random variable that can take values from $1$ to $n$ denoting number of swaps
Lets look at the last position.That is right most.
Probability that this is a min element is $1/n$. So $$E(X_n\mid \text{Last element is min})= E(X_{n-1})+1$$ because we need to do one more additional swap after finding minimum element from $1$ to $n-1$
Probability that this is not a min element is $(n-1)/n$. So $$E(X_n\mid \text{Last element not a min})= E(X_{n-1})$$
Conbining both we get
$$E(X_n) = \frac 1n(E(X_{n-1}) +1) + \frac {n-1}nE(X_{n-1})\\E(X_n) = \frac 1n + E(X_{n-1})\\E(X_n) = \sum_{i=1}^n \frac 1i$$ Recursively expand to get answer Please check if my idea is correct.Also improvements to the notations will be helpful