Choose M numbers from N with equal probability for all
Puzzle: How do you pick M numbers from an array of N integers such that probability of choosing each one of them is the same?
Solution: Let us choose just one number first.
Probability of the first number being picked up is 1/N
If we follow the same approach for the next number, then its probability of being chosen is:
= (N-1)/ N2
This is not what we want.
To choose the second element with same probability, we can do the following:
With this approach, the probability of second element becomes:
= (N-1)/N * 1/(N-1)
Similarly, probability for 3rd element becomes:
= (N-1)/N * (N-2)/(N-1) * 1/(N-2)
|Email:||(Your email is not shared with anybody)|