TIFR CSE 2014 | Part B | Question: 6

Question

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?

• A. $O (1)$
• B. $H_{n}=\sum ^{n}_{i=1} 1/i$
• C. $\sqrt{n}$
• D. $n/2$
• E. $n$

Comments

We can use conditional expectation here to arrive.Let the expectation of finding the minimum of n numbers be E(Xn).Xn 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(Xn/Last element is min)= E(Xn-1)+1.because we need to do 1 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(Xn/Last element not a min=E(Xn-1)

Conbining both we get

E(Xn)=1/n(E(Xn-1)+1)+(n-1)/n(E(Xn-1))

E(Xn)=1/n+E(Xn-1)

Recursively expand to get answer
@Shrestha,@Arjun,@Shaik Masthan sir can you please check this.Also improvements to the notations will be helpful.

Answer 1

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 .

Comments

This question is really easy if you can understand the question itself and which is not easy.

---

There will be $\mathbf 3$ swaps in the $\mathbf{4^{th}}$ row as well.

---

@JEET

It will be 2 only. 4 th row contains,

 2 3 1

Now, checking one by one,

2 3 1  [ min=2 , MU=1]

2 3 1  [min=2 , MU=1]

2 3 1  [min=1, MU=2]

PS : here MU are minimum no. of times min is updated till now. 

Answer 2

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$

Comments

yes, thank you for the algo

Then question it updated 4 times

right?

because, it is checking decreasing sequence

---

yes mam, my mistake !

---

nice proof!

Answer 3

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

Comments

exactly my approach too

---

Yes you did the same as well.