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 $igeq2$, $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] + 2sum_{k=1}^{n-1} sum_{ell=k+1}^n mathbb{E}[X_k X_ell] &= sum_{k=1}^n Pr[E_k] + 2sum_{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/(kell)$, and so $$ begin{align*} 2sum_{k=1}^{n-1} sum_{ell=k+1}^n Pr[E_k land E_ell] &= 2sum_{k=1}^{n-1} sum_{ell=k+1}^n frac{1}{kell} &= 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} + Oleft(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
