Let R=(1,2,...,n) be a set with n elements. Let S be a set of all subsets. There are 2^n such subsets. Pick 2 at random call A and B. Show probability that A contained in B is (3/4)^n

- June 21st 2010, 06:00 AMteramariesProbablitity Proof: Let R=(1,2,...,n) be a set with n elements ....
Let R=(1,2,...,n) be a set with n elements. Let S be a set of all subsets. There are 2^n such subsets. Pick 2 at random call A and B. Show probability that A contained in B is (3/4)^n

- June 21st 2010, 06:42 AMANDS!
Something to help you get started: if S is the power set on R, then for any two randomly selected subsets A and B there are four possibilities: A is a subset of B, B is a subset of A, A is equal to B and A and B are disjoint sets (meaning they have no intersection - for example S= {1,2,3}, A could be {1} and B could be {2,3} - both subsets on S, neither containing the other).

Hopefully that is a step in the right direction. - June 21st 2010, 10:58 AMHallsofIvy
- June 21st 2010, 11:37 AMundefined
I think the question can be answered like this.

I assume A and B are not necessarily distinct sets.

Let mean powerset of a set . So in the question statement, . Not to be confused with which I'll use for probability of event .

So for randomly selected subset of , there is a probability that , a probability that , etc.

Suppose . How many (not necessarily proper) supersets does have that are in ? It is . (Each element in the complement of can be either in the superset, or not.) So the probability that is a superset of is .

So we have

Someone please help me with the last step: How to prove that ? I'm guessing it's easy for people more used to working with sums of this nature.. - June 21st 2010, 12:38 PMPlato
- June 21st 2010, 02:31 PMawkward
Nice indeed. Here is another approach: induction over n.

The case n=1 is easy to verify.

Suppose that when A and B are randomly chosen subsets of a set of size n that .

Now consider the case where there are n+1 elements , and suppose A and B are randomly chosen subsets. We know , and the events and are independent.

If and , which happens with probability 1/4, then by the inductive hypothesis.

If and , which happens with probability 1/4, then .

If and , which happens with probability 1/4, then .

If and , which happens with probability 1/4, then .

Putting all these cases together,

,

which completes the proof.