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

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 kth item appears, it replaces the item in memory with probability 1/k. Explain why this algorithm solves the problem.

We will prove that right after the kth item had been replaced the item in memory with probability 1/k, the item in memory is equally likely to be any of the items had appeared so far, that is the probability of the ith item be the item in memory is 1/k for i=1,\ldots ,k.
The statement can be proved by induction.

For k = 1, the 1st item will be the item in memory with probability 1/k=1/1=1.

Then suppose the statement is true for some k=n, that is after the nth item has been replaced the item in memory with probability 1/n, the probability of the ith item be the item in memory is 1/n for i=1,\ldots ,n.

We will prove that the statement is also true for k = n+1, that is after the n+1th item has been replaced the item in memory with probability \frac{1}{n+1}, the probability of ith item be the item in memory is \frac{1}{n+1} for i = 0, \ldots ,n+1.
Indeed, after being replaced, the item in memory can be:
–  the new n+1th item with probability \frac{1}{n+1}.
– the same item as the previous turn with probability 1-\frac{1}{n+1}=\frac{n}{n+1}. But the same old item can be any item from 1st to nth with probability \frac{1}{n}, therefore the item in memory in this case can be any item from 1st to nth item with probability \frac{1}{n}\cdot \frac{n}{n+1}=\frac{1}{n+1}.
So the probability of ith item be the item in memory is \frac{1}{n+1} for i= 1, \ldots ,n+1, thus by induction yields the rightness of the statement.

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

In this version of the algorithm, let X be random variable which is equal to i if and only if the item in memory is the ith item.
We have the following probability distribution on i=1,\ldots , n:

Pr(X=i)=(\frac{1}{2})^{n-i}.

Exercise 2.21: Let a_{1},a_{2},\ldots ,a_{n} be a random permutation of \{1,2,\ldots ,n\}, equally likely to be any of the n! possible permutations. When sorting the list a_{1},a_{2},\ldots ,a_{n}, the element a_{i} must move a distance of \mid a_{i} - i\mid places from it current position to reach its position in the sorted order. Find

E[\sum_{i=1}^{n}\mid a_{i}-i\mid ],

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

Solution:

E[\sum_{i=1}^{n} \mid a_{i} -i \mid] = \sum_{i=1}^{n}E[\mid a_{i} - i \mid]

Now we calculate E[\mid a_{i} - i\mid].

Because the input is equally likely to be any of n! permutations, the position of a_{i} is equally likely to be any number from 1 to n. In other words, Pr(a_{i} = j) =\frac{1}{n}\quad j=1,\ldots , n

Then E[\mid a_{i} - i\mid] = \sum_{j=1 ; j \ne i}^{n}\frac{1}{n}j

=\frac{n+1}{2} - \frac{i}{n}.

Therefore

E[\sum_{i=1}^{n}\mid a_{i} - i\mid]

=\sum_{i=1}^{n}(\frac{n+1}{2}- \frac{i}{n})

= \frac{n(n+1)}{2} -\frac{1}{n}\frac{n(n+1)}{2}

= \frac{n^{2}-1}{2}.

Advertisements

4 responses to this post.

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

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

    Reply

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

    Reply

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

    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: