1
$\begingroup$

The question has been discussed here but unfortunately is closed.

Reference : m-element random sample being equally likely ...(CLRS 5.3-7)?

My question is as follows.

Suppose $n = 5, m = 3$. This implies that we need to randomly select a $3$-subset out of $5$ elements. The algorithm makes $3$ recursive calls. The probability of obtaining the set $S_1 = \{1,2,3\}$ is more than that of $S_2 = \{3,4,5\}$ since we can obtain $S_2$ in only one way as follows.

$$ 3 = RANDOM(1,3) \\4 = RANDOM(1,4)\\ 5 = RANDOM(1,5) $$

But in case of $S_1$ we have $3! = 6$ ways of obtaining it, two of them being as follows.

$$ 3 = RANDOM(1,3) \\2 = RANDOM(1,4)\\ 1 = RANDOM(1,5) $$ $$ 2 = RANDOM(1,3) \\3 = RANDOM(1,4)\\ 1 = RANDOM(1,5) $$

Now, how can the output of each $3$-subset is equally likely as claimed in the question?

$\endgroup$
1
$\begingroup$

There are actually only two random steps in this case:

  1. Start with $\{1,2,3\}$.
  2. With probability $3/4$, replace a random element with $4$.
  3. With probability $3/5$, replace a random element with $5$.

You get $\{1,2,3\}$ if you don't insert $4$ or $5$, which happens with probability $$\left(1-\frac{3}{4}\right)\left(1-\frac{3}{5}\right) = \frac{1}{4} \cdot \frac{2}{5} = \frac{1}{10}.$$

You get $\{3,4,5\}$ in two cases:

  1. You replace $1$ with $4$ and then $2$ with $5$.
  2. You replace $2$ with $4$ and then $1$ with $5$.

The probability that you replace a specific element with $4$ is $(3/4)(1/3)=1/4$, and the probability that you replace a specific element with $5$ is $(3/5)(1/3)=1/5$. In total, the probability that we get $\{3,4,5\}$ is

$$ \frac{1}{4}\cdot \frac{1}{5} + \frac{1}{4}\cdot \frac{1}{5} = \frac{1}{10}. $$

So both probabilities are the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.