#1
|
|||
|
|||
Interesting probability question
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 |
#2
|
|||
|
|||
Re: Interesting probability question
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 |
#3
|
|||
|
|||
Re: Interesting probability question
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. |
#4
|
|||
|
|||
Re: Interesting probability question
nice solution !
c(n,k)2^(n-k) {sum from k=0 to n) = (2+1)^n |
#5
|
|||
|
|||
Re: Interesting probability question
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 :-)
|
#6
|
|||
|
|||
Re: Interesting probability question
Yes very nice indeed .
|
#7
|
|||
|
|||
Re: Interesting probability question
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. |
#8
|
|||
|
|||
Re: Interesting probability question
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. |
|
|