If we have, for example, a universe with 15 elements {1..15}, and 3 subsets defined as: A{1,2,3,4}, B{3,4,7,8}, C{9,10,11}

Now I start drawing random elements from the universe without replacements, and stop once my sequence covers 1 or more of my subsets. I want to know how I can calculate the probability that {1} is the last element drawn.

I have found the answer using the inclusion exclusion principle. A number from subset A or B holds for $\frac{1}{4}$ of 15! permutations. A number from subset C holds for $\frac{1}{3}$ of 15! permutations. However, in those permutations for A, we also count permutations where B or C might have been drawn already. So by the inclusion exclusion principle, I subtract the intersection of A and B ($\frac{1}{6}$), and the intersection of A and C ($\frac{1}{7}$) and then add the intersection of A,B,C ($\frac{1}{9}$).

So for "1" this gives me a probability of $\frac{1}{4}$ - ($\frac{1}{6}$ + $\frac{1}{7}$) + $\frac{1}{9}$ = 0,05159. For "9" this gives me $\frac{1}{3}$ - $\frac{2}{7}$ + $\frac{1}{9}$ = 0.15873. For "3" and "4" it gets a bit more complicated. I take the probability for an element from A, add the probability for an element from B, but since both A and B hold element "3" I also determine the probability that both A and B are covered. So that would be $\frac{1}{6}$ - $\frac{1}{9}$ = 0,05555. These 3 together: 0,05159 + 0,05159 + 0,05555 = 0,15873. I have verified this in a simulation.

My problem arises when the number of subsets increases to, for example, 50 subsets. By inclusion/exclusion I would have to determine the intersections of ${50 \choose 1}$, ${50 \choose 2}$, ... ${50 \choose n}$ combinations. The lengthy iteration over all those combinations costs too much time.

For my usecase I would require a method that could calculate (or estimate with around 3% accuracy) this probability within seconds on a modern webserver for up to 4000 subsets. During my search on the web I've found numerous methods, formula's or theories but these are quite often explained by fancy notations I do not understand. Due to this, I find it hard to determine if such a method would solve my problem.

So the question is, is there a method that gives the desired result within the desired time which I can start researching? An explanation of such method projected on the numbers above would be much appreciated.

Thank you.

  • $\begingroup$ Nobody who can give me a push in the right direction? $\endgroup$ – Gwannalan Jan 27 '17 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.