Posted 12 Dec 2013 Given a set X with n elements, and sets A and B which are subsets of X, what is the probability of A being a subset of B? 0 Share this post Link to post Share on other sites

0 Posted 13 Dec 2013 (edited) We aren't told anything about how subsets A and B are constituted. So let's make as few assumptions as possible about their formation, requiring only that all the elements of each subset are chosen by a single uniform process. Let A's elements be chosen from X by flipping a biased coin that is successful with probability a. Let B be formed with a different biased coin with success probability b. The probability that an element of X is chosen for A but not B is thus q = a(1-b). We seek the probability that this did not happen for any of X's n elements. Since the coin flips are independent events, the individual probabilities can be multiplied. Thus, p(A sub B) = (1-q)^{n}. Edit: in case memberships are determined by fair coin flips, p(A sub B) = (0.75)^{n}. Edited 13 Dec 2013 by bonanova Added special case 0 Share this post Link to post Share on other sites

0 Posted 15 Dec 2013 If, by the problem you mean that, if we pick subsets in such a way that every subset is equally likely to be chosen as any other subset, and we label them A and B randomly, then you have Bonanova's case where a=b=1/2 for the probability that A⊆ B which, I agree with Bonanova, is (0.75)^{n}. If, on the other hand, you mean that, if we pick subsets in such a way that every subset is equally likely to be chosen as any other subset, and we label them A and B and we ask what is the probability that A⊆ B or B⊆ A (in other words, whether the smaller subset is a subset of the larger), then the probability is (3^{n}-2^{n-1})/2^{2n-1}. 0 Share this post Link to post Share on other sites

Posted

Given a set X with n elements, and sets A and B which are subsets of X, what is the probability of A being a subset of B?

## Share this post

## Link to post

## Share on other sites