I am trying to understand the following solution to CLRS 5.3-7: http://clrs.skanev.com/05/03/07.html Question description is on the page. I understood the part where m-element subset is constructed out of m-1 element subset when the m-element subset includes the last element n. But why does the probability of randomly choosing m-1 elements from a set of n-1 elements differs in the case when we don't include the last element? Doesn't the invariant state that we choose m-1 elements at random from n-1 elements?

  • 2
    $\begingroup$ Please edit your question to make it self-contained, without needing to refer to external resources to understand the question. Note that you can use Latex on this site to format equations and mathematics. Also, edit your question to tell us what you've tried on your own. Have you tried working through a small example, for a few small values of $m,n$? We expect you to make a serious effort on your own before asking and to show us what you have tried in the question. $\endgroup$
    – D.W.
    Jun 29 '14 at 13:37

Here is the recursive algorithm for selecting a random set $S \in \binom{[n]}{m}$ (the set of all $m$-subsets of $[n] = \{1,\ldots,n\}$):

  1. If $m = 0$, return the empty set.
  2. Generate a random set $S \in \binom{[n-1]}{m-1}$ recursively.
  3. Let $i \in [n]$ be chosen uniformly at random.
  4. If $i \notin S$, return $S \cup \{i\}$.
  5. If $i \in S$, return $S \cup \{n\}$.

To show that this works, we prove that the probability to get any set in $\binom{[n]}{m}$ is exactly $1/\binom{n}{m}$, by induction on $n$. This is clear when $m = 0$, so assume $m > 0$. Let $S \in \binom{n}{m}$ be given. We consider two cases: $n \notin S$ and $n \in S$.

Case 1, $n \notin S$. For each $i \in S$, the probability that the recursive step generates $S \setminus \{i\}$ is $1/\binom{n-1}{m-1}$, and so in that case $S$ is produced with probability $1/n$. In total, the probability is $$ \frac{m}{n} \frac{1}{\binom{n-1}{m-1}} = \frac{1}{\binom{n}{m}}. $$

Case 2, $n \in S$. In that case, the recursive step must generate $S \setminus \{n\}$, and then $S$ is produced with probability $m/n$ (since we either hit $n$ or any element in $S \setminus \{n\}$), obtaining the same expression as above.


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