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\}$):


If $m = 0$, return the empty set.
Generate a random set $S \in \binom{[n-1]}{m-1}$ recursively.
Let $i \in [n]$ be chosen uniformly at random.
If $i \notin S$, return $S \cup \{i\}$.
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 &gt; 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.

m-element random sample being equally likely ...(CLRS 5.3-7)?
A dice is being rolled continuously. Suppose you roll a 3 ( or any number ). What is the probability that you will get the next "3" exactly after n rolls?  
