III. HOME WORK PROBLEMS
1. BLIND PICK ALIGNMENT PROBABILITY PROBLEM
If one blindly picks out |S| choices out of N possibilities,
what is the probability that at least k < |S| of the
top-|G| choices will be contained in the set S. Do it first
for the case |S| = |G| and then generalize to |S| not
equal to |G|.
SOLUTION:
Let |S| = |G| = g and the alignment probability be
P(|
| >=
k). Since all possibilities are equal in blind pick, here are
NCg possibilities of picking out g choices
from N alternatives. Of all these picks, the number of possible ways
for i < k of the top-g choices in S is
gCi. For each of these possibilities of i
top-g choices in S, the remaining g-i top-g
choices can be distributed in the remaining N-g slots in
N-gCg-i ways. Thus the fraction of possibilities
of at least k top-g choices in S via blind picking is
given by
Now for g > |S| = s and by the same reasoning
and for s > g