Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E2-48'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 2-48

Question

You are given a set S of n numbers. You must pick a subset S' of k numbers from S such that the probability of each element of S occurring in S' is equal (i.e., each is selected with probability k/nk/n). You may make only one pass over the numbers. What if n is unknown?

Solution

FIrst, prepare indices i=0..n.

Then, pick the indices one by one (totally k-times picking).

The probability for index m to be picked at lth picking trial is:

P(m)=(∏i=1l−1n−in−i+1)⏟(A)∗1n−l+1⏟(B)=1n\begin{equation} P(m)=\underbrace{(\prod_{i=1}^{l-1}\frac{n-i}{n-i+1})}_\text{(A)}*\underbrace{\frac{1}{n-l+1}}_\text{(B)}=\frac{1}{n} \end{equation}

(A) denotes the probability that between first trial and (l-1)th trial index m is not picked.
(B) denotes the probability that at lth picking m is picked.

So the probability for index m to be picked between first and kth trial is:

k∗1n=kn\begin{equation} k*\frac{1}{n}=\frac{k}{n} \end{equation}

Arbitrary index has the probability above, there is no bias.

Next, traverse the set S and at the same time start counting.

If the counter value is included in the picked indices, take the number to S'.

Finally, when traverse is end, S' is filled with numbers whose occurrence is equal.