**Exercise 2.18:** The following approach is often called *reservoir sampling. *Suppose we have a sequence of item passing by one at a time. We want to maintain a sample of one item with the property that it is uniformly distributed over all the items that we have seen at each step. Moreover, we want to accomplish this without knowing the total number of items in advance or storing all of the items that we see.

Consider the following algorithm, which store just one item in memory at all times. When the first item appears, it is stored in the memory. When the th item appears, it replaces the item in memory with probability . Explain why this algorithm solves the problem.

We will prove that right after the th item had been replaced the item in memory with probability , the item in memory is equally likely to be any of the items had appeared so far, that is the probability of the th item be the item in memory is for .

The statement can be proved by induction.

For , the st item will be the item in memory with probability .

Then suppose the statement is true for some , that is after the th item has been replaced the item in memory with probability , the probability of the th item be the item in memory is for .

We will prove that the statement is also true for , that is after the th item has been replaced the item in memory with probability , the probability of th item be the item in memory is for .

Indeed, after being replaced, the item in memory can be:

– the new th item with probability .

– the same item as the previous turn with probability . But the same old item can be any item from st to th with probability , therefore the item in memory in this case can be any item from st to th item with probability .

So the probability of th item be the item in memory is for , thus by induction yields the rightness of the statement.

**Exercise 2.19: **Suppose that we modify the reservoir sampling algorithm so that, when the th item appears, it replaces the item in memory with probability . Describe the distribution of the item in memory.

In this version of the algorithm, let be random variable which is equal to if and only if the item in memory is the th item.

We have the following probability distribution on :

.

**Exercise 2.21:** Let be a random permutation of , equally likely to be any of the possible permutations. When sorting the list , the element must move a distance of places from it current position to reach its position in the sorted order. Find

,

the expected total distance the elements will have to be moved.

**Solution: **

Now we calculate .

Because the input is equally likely to be any of permutations, the position of is equally likely to be any number from to . In other words,

Then

.

Therefore

.

Posted by Anonymous on May 26, 2012 at 11:21 pm

My answer for ex 21 is (n^2-1)/3

Posted by Anonymous on June 7, 2017 at 5:21 pm

My is the same as yours.

Posted by Anonymous on November 17, 2014 at 8:12 am

your answer for 2.21 seems wrong. P[ |a_i -i | = 1 ] may be 2/n because i have two elements at that distance( one on the left and one on the right ).

Posted by Solution Manual on May 28, 2017 at 3:39 am

Thanks for another informative website. The place else could

I am getting that type of information written in such a

perfect manner? I have a mission that I’m just now working on, and I’ve been at the glance

out for such info.