edited by
2,576 views
31 votes
31 votes

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 $\left \langle 1,....,n \right \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?

  1. $O (1)$
  2. $H_{n}=\sum ^{n}_{i=1} 1/i$
  3. $\sqrt{n}$
  4. $n/2$
  5. $n$
edited by

3 Answers

Best answer
37 votes
37 votes

Let us consider $3$ numbers $\{1,2,3\}$

We will consider the permutation along with min no of times MIN is updated.
$$\begin{array}{c|c} \hline \textbf{Permutation} & \textbf{Minimum of times} \\
& \textbf{ MIN is updated} \\\hline
 1,2,3 & 1 \\ 1,3,2 & 1 \\ 2,1,3 & 2\\ 2,3,1 & 2 \\ 3,1,2 & 2 \\ 3,2,1 & 3   \end{array}$$
Total number of times MIN updated is  : $11$.

Average no of times MIN updated is  : $(11/6)$

Now going by the options i am getting B .   

$H_3 = 1 + 1/2 + 1/3 = 11/6$ .

$H_3$ is the answer and that is option B .

edited by
15 votes
15 votes
We first suppose that $X$ is the random variable equal to the number of MIN updates made by this algorithm to find the minimum element of a list $a_{1}, a_{2}, ..., a_{n}$ of n distinct numbers. Then $E(X)$ is the average number of updates made. We let $X_{i}$ be a random variable such that $X_{i}$ = $\begin{cases} & 1 \text{ if } a_{i} < min\\ & 0 \text{ otherwise} \end{cases}$

That is, $X_{i}$ has value 1 if and only if it is the smallest element seen so far, in which case there will be an update. Then it is clear that $ X = X_{1} + X_{2} + ... + X_{n}$. We can use the linearity of expectations to conclude that,

$E(X) = E(X_{1} + X_{2} +  ... + X_{n}) = E(X_{1}) + E(X_{2}) + ... + E(X_{n}). $

Now, notice that the position of elements in the list is completely random, so for any given set of positions in the list, it is equally likely for any of them to be holding the smallest element. Hence,

$P(a_{1} < min) = 1$, because $min = \infty$

$P(a_{2} = min(a_{1}, a_{2})) = 1/2$

$P(a_{3} = min(a_{1}, a_{2}, a_{3})) = 1/3$

$.\\.\\.$

$P(a_{n} = min(a_{1}, a_{2}, ..., a_{n})) = 1/n$.

Expectation for a single $X_{i}$ can be calculated as:  $E(X_{i}) = 1.P(X_{i} = 1) + 0.P(X_{i} = 0)$.

Then, their sum is: $E(X) = 1.(1) + 1. (1/2) + 1.(1/3) + ... + 1.(1/n)$ = $\sum_{i=1}^{n} 1/i$
edited by
4 votes
4 votes
$\mathbf{\underline{Answer:B}}$

$\mathbf{\underline{Explanation:}}$

$\mathbf{\underline{Proof:}}$

$\mathbf{\underline{Using\;Conditional\;Expectation}}$

Assume the expectation of finding the minimum from the $\mathbf n$ numbers be $\mathbf{E(X_n)}$.

Here, $\mathbf {X_n = Random\;Variable}$, that can accept values from $\mathbf 1$ to $\mathbf n$ representing minimum number of swaps.

$\text{Probability that the rightmost element $\underline{\color{green}{\textbf{is a minimum element}}}$} = \color{blue}{\mathbf{\dfrac{1}{n}}}\tag{i}$.

$\therefore \mathbf{E(X_n | Last \;element \; \color{green}{\underline{is\; minimum}}) = \color{blue}{E(X_{n-1}) + 1}}\tag{ii}\;\;\text{[$\because$ an additional swap is needed after finding the minimum element.]}$

$\therefore \text{The probability this element $\color{green}{\underline{\textbf{is not a minimum element}}}$} =\color{blue}{\mathbf{\dfrac{n-1}{n}}}\tag{iii}$

$\mathbf{E(X_n | Last\;element\;\color{green}{\underline{not\;a\;minimum}}) = \color{blue}{E(X_{n-1}})}\tag{iv}$

From$\mathbf{(i), (ii), (iii), \;and\;(iv)},$ we get:

$\mathrm{E(X_n) = \dfrac{1}{n}(E(X_{n-1}) + 1) + \dfrac{n-1}{n}E(X_{n-1})}$

$\mathrm{E(X_n) = \dfrac{1}{n} + E(X_{n-1})}$

$\bbox[orange,5px,border: 20x dotted red]{\mathbf{E(X_n) = \sum_{i=1}^n \dfrac{1}{i}}}$

$\therefore \mathbf B$ is the right option.
edited by
Answer:

Related questions

49 votes
49 votes
7 answers
2