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





NEXT QUESTION


Return to Table of Content