Probability and Computing: Chapter 2 Exercises (Cont. 3)

Exercise 2.22: Let $a_{1},a_{2},\ldots ,a_{n}$ be a list of $n$ distinct numbers. We say that $a_{i}$ and $a_{j}$ are inverted if $i but $a_{i}>a_{j}$. The Bubblesort algorithm swaps pairwise adjacent inverted numbers in the list until their are no more inversions, so the list is sorted in order. Suppose that the input to Bubblesort is a random permutation, equally likely to be any of the $n!$ permutations of the $n$ distinct numbers. Determine the expected number of inversions that need to be corrected by Bubblesort.

Solution: Let $X$ be the expected number of swaps that need to be done by Bubblesort. With $i < j$, let $X_{ij}$ be random variables that take on value $1$ if $a_{i} > a_{j}$, $0$ otherwise.

Observe that if $i < j$ and $a_{i} > a_{j}$ then there must be exactly one swap to correct this invertion regardless which and how other swaps are made (since swaps are only applied between adjacent elements).

Thus we have $X = \sum_{i =1}^{n-1}\sum_{j = i + 1}^{n}X_{ij}$

therefore $E[X] = E[\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{ij}]$

$= \sum_{i=1}^{n-1}\sum_{j = i +1}^{n}E[X_{ij}]$.

Now we will calculate $E[X_{ij}] \quad (i < j)$

Since $X_{ij}$ is a $0$$1$ random variable, $E[X_{ij}] = Pr(X_{ij} = 1)$

We have $Pr(X_{ij}=1) = Pr(a_{i} > a_{j}) = \frac{1}{2}$

This yields $E[X_{ij}] = \frac{1}{2}$.

Therefore $E[X] = \sum_{i = 1}^{n-1}\sum_{j = i +1}^{n}\frac{1}{2}$ $=\frac{1}{2}\sum_{j=1}^{n-1}j$

$=\frac{n(n-1)}{4}$.

The average number of swaps needed by Bubblesort is $\frac{n(n-1)}{4}$

(we can do this cleanly thanks to the linearity of expectation. We can tell more about how efficient Bubblesort is if we know how “stable” the sort is, which is a thing we can say if we have the variance. I wonder if there is a way to calculate $Var[X]$ other than directly calculate $E[X^{2}]$, which is already not an easy task. )

Exercise 2.23: Linear insertion sort can sort any array of number in place. The first and second numbers are compared; if they are out of order, they are swapped so that they are in sorted order. The third number is then placed in the appropriate place in the sorted order. It is first compared with the second; if it is not in the proper order, it is swapped and compared with the first. Iteratively, the $k$th number is handled by swapping it downward until the first $k$ numbers are in sorted order. Determine the expected number of swaps that need to be made with a linear insertion sort when the input is a random permutation of $n$ distinct numbers.

Solution: Let $X$ be the number of swaps that need to be made with a linear selection sort in sorting $a[1..n]$. Let $X_{i}$ be the number of swaps needed when $a[i]$ is handled.

We have $X=\sum_{i=2}^{n}X_{i}$, thus $E[X] = E[\sum_{i=2}^{n}X_{i}] = \sum_{i=2}^{n}E[X_{i}]$

We now calculate $E[X_{i}]$, the expected number of swaps needed when we handle the $a[i]$.

Observe that when we handle $a[i]$, number of swaps needed is equal to the number of elements greater than $a[i]$ in the range $a[1]...a[i-1]$.

Let $Y_{j}$ be a random variable takes on value $1$ if $a[j] > a[i]$, $0$ otherwise.

Since $Y_{j}$ is a $0$$1$ random variable, we have $E[Y_{j}] = Pr(Y_{j} = 1) = Pr(a[j] >a[i]) = \frac{1}{2}$.

We can express $X_{i}$ in terms of $Y_{j}$ as followed.

$X_{i} = \sum_{j=1}^{i-1}Y_{j}$.

Thus

$E[X_{i}]=\sum_{j=1}^{i-1}Y_{j}=\sum_{j=1}^{i-1}\frac{1}{2} = \frac{1}{2}(i-1)$

Therefore $E[X] = \sum_{i=2}^{n}\frac{1}{2}(i-1) = \frac{1}{2}\sum_{i=1}^{n-1}i = \frac{n(n-1)}{4}$

(The average number of swaps of the Insertion sort is equal to that of the Bubble sort ??)

Exercise 32: You need a new staff assistant, and you have $n$ people to interview. You want to hire the best candidate for the position. When you interview a candidate, you can give them a score, with the highest score being the best and no ties being possible. You interview the candidates one by one. Because of your company’s hiring practices, after you interviewed the $k$th candidate, you either offer the candidate the job before the next interview or you forever lose the chance to hire that candidate. We suppose the candidate are interviewed in a random order, chosen uniformly at random from all $n!$ possible ordering.
We consider the following strategy. First, interview $m$ candidates but reject them all; these candidate give you an idea of how strong the field is. After the $m$th candidate, hire the first candidate you interview who is better than all of the previous candidates you have interviewed.

(a) Let $E$ be the event that we hire the best assistant, and let $E_{i}$ be the event that $i$th candidate is the best and we hire him. Determine $Pr(E_{i})$, and show that

$Pr(E) = \frac{m}{n}\sum_{j=m+1}^{n}\frac{1}{j-1}$.

(b) Bound $\sum_{j=m+1}^{n}\frac{1}{j-1}$ to obtain

$\frac{m}{n}(ln(n)-ln(m)) \leq Pr(E) \leq \frac{m}{m}(ln(n-1)-ln(m-1))$.

(c) Show that $m(ln(n)-ln(m))/n$ is maximized when $m = n/e$, and explain why this means $Pr(E) \geq 1/e$ for this choice of $m$.

Solution:

(a) First we have $Pr(E)=\sum_{i=1}^{n}Pr(E_{i})= \sum_{i=m+1}^{n}Pr(E_{i})$.

We will calculate $Pr(E_{i})_{i \ge m + 1}$.

For event $E_{i}$ to happen, the following two independent events must happen:

– The best candidate of $n$ candidates is the $i$th candidate. This event happens with probability $\frac{1}{n}$.

– The best of the first $i-1$ candidates  is within the the first $m$ candidates. This event happens with probability $\frac{m}{i-1}$.

So $Pr(E_{i})=\frac{1}{n}\frac{m}{i-1}$.

Then $Pr(E)=\sum_{i = m +1}^{n}Pr(E_{i})=\sum_{i=m+1}^{n}\frac{m}{n(i-1)} = \frac{m}{n}\sum_{i=m+1}^{n}\frac{1}{i-1} . \qquad \square$

(b) $Pr(E) =\frac{m}{n}\sum_{i=m}^{n-1}\frac{1}{i}$.

In the text it has been shown that

$ln(n) \le \sum_{i=1}^{n}\frac{1}{i} \le ln(n) + 1$.

Applying this inequality yields

$ln(m-1) \le \sum_{i=1}^{m-1}\frac{1}{i} \le ln(m-1) + 1$

$ln(n-1) \le \sum_{i=1}^{n-1}\frac{1}{i} \le ln(n-1) + 1$

Thus $ln(n-1) - ln(m-1) - 1\le \sum_{i=m}^{n-1}\frac{1}{i} \le ln(n-1)-ln(m-1) + 1$

[not completed]

11 responses to this post.

1. Posted by L.G. on January 15, 2012 at 2:57 am

I calculated the variance of Bubble-sort and I have Var[X] = 2n+5/18 * E[X]. Is that plausible ?

P.S. I cannot find the solutions for other chapters (>=4) of “Pr. & Comp.” ;(. Would you continue to post the solutions here ? 🙂

2. Posted by thethong on January 15, 2012 at 9:33 am

Did you get the same answer for $E[X]$ as mine in Exercise 2.22 (and 2.23)?
$E[X_{ij}^2]$ is expectation of a Bernoulli r.v so it is easy to calculate. $E[X_{ij}X_{kl}] = Pr(X_{ij}X_{kl} = 1) = Pr(X_{ij} = 1,X_{kl} = 1) = Pr(X_{ij} = 1 | X_{kl} = 1)Pr(X_{kl} = 1)$ so may be $E[X_{ij}X_{kl}]$ can be calculated (not sure). If we have $E[X_{ij}^2]$ and $E[X_{ij}X_{kl}]$, then $E[X^2]$ follows. How did you calculate $Var[X]$?
(The unit for E[X] is “number of swap”. So I think the unit for Var[X] is “square of number of swap”. I am not sure whether $Var[X]$ can be of the same order of $E[X]$ as in your answer.)

3. Posted by L.G. on January 15, 2012 at 9:09 pm

Before I answer you, I would just like to know how can I write down here the maths environment, so that it would be easer to read for you. Is the maths environment is the same as in LaTex ?

4. Posted by thethong on January 15, 2012 at 11:41 pm

Yes, it is almost the same. A WordPress Latex command starts with $and ends with$

5. Posted by thethong on January 15, 2012 at 11:52 pm

sorry, Latex code starts with $latex and ends with$ (remove the space between \$ and latex)

6. Posted by L.G. on January 19, 2012 at 2:31 am

Sorry, for delay – I was not able to respond earlier.

So, we need to find $Var[X]$ and thus $E[X^2]$ which is the main difficulty.
Let’s start from explicit writing of $E[X^2]$ :

$\[ \mathbb{E}(X^{2}) = \underbrace{\sum_{i

where we use the linearity of expectation, the definition of expectation of Bernoulli variables, and the fact that

$\mathbb{P}(X_{ij}X_{jk} = 1)} = \mathbb{P}(X_{jk}X_{ij} = 1)}$

So now we have to calculate those probabilities and the correspondent number of exchanges done by algorithms.
Let me stop here for a second to see if I worked latex mode properly.

7. Posted by L.G. on January 19, 2012 at 2:33 am

it seems like it doesn’t support \mathbb. 2nd try :
$\E(X^{2}) = \underbrace{\sum_{i

8. Posted by L.G. on January 19, 2012 at 2:36 am

Ok, I have some problems here with latex, and I do not want to flood your blog (you can delete the comments above) – can I send you an email with solution in pdf, please (you can post any part of it here later) ?

• Posted by thethong on January 19, 2012 at 3:51 pm

I did these exercises more than 2 years ago, but stopped halfway. If you have solutions for the other chapters or unanswered exercises, it is great if you can share them in the comment or send me at thong_pham_the at gmail.com (remove all _ ). If you send an pdf, please send it together with the latex file (if you allow me to post your solution). Thanks!