BrainDen.com - Brain Teasers
• 0

# Simple Probability Problem?

## Question

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?

## 2 answers to this question

• 0

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 by bonanova

##### Share on other sites
• 0

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 (3n-2n-1)/22n-1.

## Create an account

Register a new account