Randomized agorithm for selecting a $m$-subset out of a $n$-set

The question has been discussed here but unfortunately is closed.

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?

1 Answer

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.