Interesting probability question

[jay_shark]

Here is a neat question that I haven't figured out yet . I'll think about it some more when I get the chance but here it goes .

Let S =[1,2,3...n} and suppose that A and B and independently likely to be any of the 2^n subsets (including the null set and s itself) of S .

Show that P(A is a subset of B) =(3/4)^n

[ig06]

Here is my solution:
Number of possible combinations of subsets A and B = (2^n)*(2^n)=4^n since A and B are chosen independently and there are 2^n possible subsets.

Number of ways that A can be a subset of B is

Subset_tot=sum from k=0 to n of C(k,n)*2^k

since for there are C(k,n) possible subsets B with k elements and 2^k possible subsets of each of those (the sum C(i,k) from i=0 to k is 2^k).

Noting that the sum from k=0 to n of C(k,n)*r^k is (1+r)^n

Subset_tot=3^n

So there are 3^n ways A can be a subset of B and 4^n ways of picking A and B in total so
Prob(A is a subset of B)=3^n/4^n=(3/4)^n

[Siegmund]

Here's a somewhat simpler way of making the same calculation:

Look at each of the elements 1,2,3...n in turn.

Four different things, equally likely, can happen to Element 1: it can be in neither set, it can be in A but not B, it can be in B but not A, or it can be in both.
One of these four things prevents A from being a subset of B, the other three do not.

[jay_shark]

nice solution !

c(n,k)2^(n-k) {sum from k=0 to n) = (2+1)^n

[ig06]

Thanks Jay :-) I think Siegmund's solution is neater though because its so simple. I understand he is saying for each element there is a probability of 1/2 that it is in A and a probability 1/2 its in B. Hence there is a probability of 1/4 that it is in A but not in B thereby precluding the possibility that A is a subset of B. Since there are n elements in S, the probability that A is a subset of B is therefore (3/4)^n. Nice solution too :-)

[jay_shark]

Yes very nice indeed .

[jay_shark]

It turns out the probability AB is the null set is also 3^n/4^n .

ie 1 is in A but not in B , 1 is in B but not A , 1 is in neither A or B =3 equally likely choices ; finally 1 can be in A and B.

[bigpooch]

That's why I like Siegmund's solution. It follows quickly
that the following all have probability (3/4)^n:

P(A is a subset of B)
P(B is a subset of A)
P(A intersect B is the null set)
P(A union B is S, the "universe").

Also, these have probability (1/2)^n:

P(A=B)
P(A and B are complementary).

In addition, by looking at elements only, not only can you
generalize to more sets (say A, B and C are "random" subsets
of S; then, the probability[A is a subset of B and B is a
subset of C] = (1/2)^n), but you can also generalize the
conditions for which an element is in A or B (perhaps one
wants P(x is in A)=a and P(x is in B)=b) and solve such a
problem relatively easily using the "element approach".

Proposition: If S has n elements and A[1], A[2], ..., A[k]
are "independent uniform random subsets" of S, the
probability that A[j] is a subset of A[j+1] for all integers
j such that 1<=j<=(k-1) is then ((k+1)/(2^k))^n.