Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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$.

share|improve this answer

The quantity you are interested in is known as the average number of left-to-right minimima and is well-studied, e.g. by Knuth [1, 1.2.10].

As it turns out, the answer is that

$\qquad\displaystyle H_n - 1 \sim \ln n$

updates happen on average. Find the details in Knuth's book, I can't do a better job explaining than he does. I'll say that the approach he uses is well worth knowing.


  1. The Art of Computer Programming, Volume 1 by D. E. Knuth (1997, 3rd ed)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.