• 0

Simple Probability Problem?

Question

Posted · Report post

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

2 answers to this question

  • 0

Posted (edited) · Report post

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
Added special case
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.