Confusing and challenging Independence Problem

[masterpcus00]

Let S = {1,2,....,n} and suppose that A and B are independently, equally likely to be any of the 2[sup:23lu4cmn]n[/sup:23lu4cmn] subsets (including the null set and S itself) of S.

Show that:

P{A C B} = (3/4)[sup:23lu4cmn]n[/sup:23lu4cmn]

Hint: Let N(B) denote the number of elements in B. Use:

P{A C B} = the sum from i=0 to n of P{A C B | N(B) = i} P{N(B) = i}

Also show that P{AB = empty set} = (3/4)[sup:23lu4cmn]n[/sup:23lu4cmn]

Please help me with this problem, I have no idea where to start

 

[pka]

Let S = {1,2,....,n} and suppose that A and B are independently, equally likely to be any of the 2[sup:40z7vb26]n[/sup:40z7vb26] subsets (including the null set and S itself) of S.
Show that: P{A C B} = (3/4)[sup:40z7vb26]n[/sup:40z7vb26]

Thank you for the most interesting problem.
If \(\displaystyle N( B ) = 0 \Rightarrow B = \emptyset\), thus \(\displaystyle A = \emptyset\) so \(\displaystyle P\left( {A \subseteq B|N( B ) = 0} \right) = \frac{1}{{2^n }}\frac{1}{{2^n }}\).
If \(\displaystyle N( B ) = 2\) then A can be any one of \(\displaystyle 2^2\) subsets of B. So \(\displaystyle P\left( {A \subseteq B|N( B ) = 2} \right) = \frac{{2^2 }}{{2^n }}\frac{{n \choose 2}}{{2^n }}\)

In general, if \(\displaystyle N( B ) = r\) then A can be any one of \(\displaystyle 2^r\) subsets of B. So \(\displaystyle P\left( {A \subseteq B|N( B ) = r} \right) = \frac{{2^r }}{{2^n }}\frac{{n \choose r}}{{2^n }}\).

This gives the sum, \(\displaystyle P\left( {A \subseteq B} \right) = \sum\limits_{r = 0}^n {\frac{{2^r {n \choose r}}}{{4^n }}}\).

To finish we must note that \(\displaystyle 3^n = \left( {2 + 1} \right)^n = \sum\limits_{r = 0}^n {{n \choose r}}\left( 2 \right)^r }\)