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<j 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 01 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 kth 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 01 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 kth 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 mth 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 ith 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 ith 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]

Advertisements

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 ? 🙂

    Reply

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

    Reply

  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 ?

    Reply

  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

    Reply

  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)

    Reply

  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<j} \mathbb{P}(X_{ij}^{2} = 1) }_{2.1} + \  \underbrace{\sum_{i<j, i<k}  \mathbb{P}(X_{ij}X_{ik} = 1) }_{2.2} + \  \underbrace{\sum_{i<j, k<j}  \mathbb{P}(X_{ij}X_{kj} = 1) }_{2.3} + \  \underbrace{2\sum_{i<j, j<k}  \mathbb{P}(X_{ij}X_{jk} = 1) }_{2.4} + \  \underbrace{\sum_{i<j, i'<j'} \mathbb{P}(X_{ij}X_{i'j'} = 1) }_{2.5} \]

    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.

    Reply

  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<j} P(X_{ij}^{2} = 1) }_{2.1} + \  \underbrace{\sum_{i<j, i<k}  P(X_{ij}X_{ik} = 1) }_{2.2} + \  \underbrace{\sum_{i<j, k<j}  P(X_{ij}X_{kj} = 1) }_{2.3} + \  \underbrace{2\sum_{i<j, j<k}  P(X_{ij}X_{jk} = 1) }_{2.4} + \  \underbrace{\sum_{i<j, i'<j'} P(X_{ij}X_{i'j'} = 1) }_{2.5}

    Reply

  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) ?

    Reply

    • 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!

      Reply

  9. Posted by Anonymous on September 30, 2016 at 12:51 am

    asdf

    Reply

  10. You ought to be a part of a contest for one of the most useful
    sites on the web. I most certainly will recommend this blog!

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: