[Solved]: Expected number of updates of minimum

Problem Detail: 

I came across the following problem in a exam.

We choose a permutation of n elements $[1,n]$ uniformly at random. Now a variable MIN holds the minimum value seen so far at it is defined to $\infty$ initially. Now during our inspection if we see a smaller value than MIN, then MIN is updated to the new value.

For example, if we consider the permutation,

$$5\ 9\ 4\ 2\ 6\ 8\ 0\ 3\ 1\ 7$$ the MIN is updated 4 times as $5,4,2,0$. Then the expected no. of times MIN is updated?

I tried to find the no. of permutations, for which MIN is updated $i$ times, so that I can find the value by $\sum_{i=1}^{n}iN(i)$, where $N(i)$, is the no. of permutations for which MIN is updated $i$ times.

But for $i\geq2$, $N(i)$ is getting very complicated and unable to find the total sum.

Asked By : Phani Raj

Answered By : Yuval Filmus

The trick is to use linearity of expectation. Let $E_k$ be the event that the $k$th input is a left-to-right minimum (i.e., requires an update), and let $X_k$ be an indicator variable for $E_k$, that is, $X_k$ is $1$ if $E_k$ happens and $0$ otherwise. Let $U = X_1 + \cdots + X_n$ be the number of updates. The expected number of updates is $$ \mathbb{E}[U] = \sum_{k=1}^n \mathbb{E}[X_k] = \sum_{k=1}^n \Pr[E_k]. $$ It remains to compute $\Pr[E_k]$. We can construct a random permutation $\pi$ of $[n] = \{1,\ldots,n\}$ in the following way: take a random permutation of $[n]$, and randomly permute the first $k$ elements. This shows that the probability that $\pi(k) = \min(\pi(1),\ldots,\pi(k))$ is exactly $1/k$, and so $\Pr[E_k] = 1/k$. All in all, we get $$ \mathbb{E}[U] = \sum_{k=1}^n \Pr[E_k] = \sum_{k=1}^n \frac{1}{k} = H_n, $$ the $n$th Harmonic number. It is well-known that $H_n = \ln n + \gamma + O(1/n)$ (Wikipedia contains the entire asymptotic expansion).

We can also compute the variance in this way: $$ \begin{align*} \mathbb{E}[U^2] &= \sum_{k=1}^n \mathbb{E}[X_k^2] + 2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \mathbb{E}[X_k X_\ell] \\ &= \sum_{k=1}^n \Pr[E_k] + 2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \Pr[E_k \land E_\ell], \end{align*} $$ where $\land$ is logical AND. We already know that $\Pr[E_k] = 1/k$. In order to compute $\Pr[E_k \land E_\ell]$ (where $k < \ell$), we follow the same route as before. With probability $1/\ell$, $\pi(\ell)$ is a left-to-right minimum. Given that, the probability that $\pi(k)$ is a left-to-right minimum is $1/k$. Therefore $\Pr[E_k \land E_\ell] = 1/(k\ell)$, and so $$ \begin{align*} 2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \Pr[E_k \land E_\ell] &= 2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \frac{1}{k\ell} \\ &= \left(\sum_{k=1}^n \frac{1}{k}\right)^2 - \sum_{k=1}^n \frac{1}{k^2} \\ &= H_n^2 - \sum_{k=1}^n \frac{1}{k^2}. \end{align*} $$ Therefore $$ \begin{align*} \mathbb{E}[U^2] &= H_n + H_n^2 - \sum_{k=1}^n \frac{1}{k^2}, \\ \mathbb{V}[U] &= H_n - \sum_{k=1}^n \frac{1}{k^2} = \ln n + \gamma - \frac{\pi^2}{6} + O\left(\frac{1}{n}\right). \end{align*} $$ We can compute all other moments in a similar way using (essentially) the inclusion-exclusion principle and the formula $$ \mathbb{E}[U^d] = \sum_{i_1,\ldots,i_d=1}^n \prod_{i \in \{i_1,\ldots,i_d\}} \frac{1}{i}. $$ If we are careful enough then we can probably establish the asymptotic normality of $U$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23295