$A$: set of Alice's frieds, $B$: Bob's friends, $C$: all people. Find $P(A \subseteq B)$ and $P(A \cup B = C)$

Question

(Introduction to Probability, Blitzstein and Nwang, p.80)

Alice, Bob, and 100 other people live in a small town. Let C be the set consisting of the 100 other people, let A be the set of people in C who are friends with Alice, and let B be the set of people in C who are friends with Bob. Suppose that for each person in C, Alice is friends with that person with probability 1/2, and likewise for Bob, with all of these friendship statuses independent.

(a) Let D $\subseteq$ C. Find P (A = D).

(b) Find P (A $\subseteq$ B).

(c) Find P (A $\cup$ B = C).

My general approach to those problems was conditioning on the set sizes. Part b) must be certainly false.

a)

• $P(A=D) = \sum_{k=0}^{100} P(A=D \mid |A|=k) * P(|A|=k)$

• $P(|A|=k) = \binom{100}{k} \left(\frac{1}{2}\right)^{100}$

• \begin{align} P(A=D \mid |A| = k) &= \sum_{j} P(A=D \mid |A| = k, |D|=j) * P(|D|=j)\\ &= P(A=D \mid |A|=|D|=k) * P(|D|=k)\\ &= \binom{100}{k}^{-1} * \frac{1}{101} \end{align}

• \begin{align} \sum_{k=0}^{100} \binom{100}{k}^{-1} * \frac{1}{101} * \binom{100}{k} * \left(\frac{1}{2}\right)^{100} = \left(\frac{1}{2}\right)^{100} \doteq 0 \end{align}

b) \begin{align} P(A \subseteq B) &= \sum_{k\leq j} P(A \subseteq B \mid |A| = k, |B|=j) * P(|A| = k, |B|=j)\\ &= \sum_{k\leq j} \frac{\binom{k}{j}}{\binom{100}{k}\binom{100}{j}} * \binom{100}{j} \left(\frac{1}{2}\right)^{j} * \binom{100}{k} \left(\frac{1}{2}\right)^{k}\\ &= \sum_{k\leq j} \binom{k}{j} \left(\frac{1}{2}\right)^{k+j} = 4 \end{align}

c)

\begin{align} P(A \cup B = C) &= \sum_{k=0}^{100} P(A \cup B = C \mid |A|=k, |B|=100-k) * P(|A|=k, |B|=100-k)\\ &= \sum_{k=0}^{100} \frac{1}{\binom{100}{k}} * \binom{100}{k} \left(\frac{1}{2}\right)^{100} * \binom{100}{100-k} \left(\frac{1}{2}\right)^{100}\\ &= \sum_{k=0}^{100} \binom{100}{k} \left(\frac{1}{2}\right)^{200} \doteq 0 \end{align}

Am I principally doing the right thing? Any help with this?

Answer 1

on a)

$A=D$ iff every person in $D$ is a friend of Alice (each has probability $\frac{1}{2}$ to be so) and every person in $C-D$ is not a friend of Alice (again each probability $\frac{1}{2}$ to be so).

There are $100$ persons in $D\cup(C-D)=C$ and if there is independence when it concerns their eventual friendship with Alice then $P(A=D)=(\frac{1}{2})^{100}$. The cardinality of $D$ is not relevant here because 'being a friend Alice' or 'not being a friend of Alice' have the same probability.

on b)

Give the persons in $C$ distinct numbers in $\left\{ 1,\dots,100\right\} $.

Let $A_{i}=1$ if person $i$ is a friend of Alice and let $A_{i}=0$ otherwise.

Let $B_{i}=1$ if person $i$ is a friend of Bob and let $B_{i}=0$ otherwise.

Then $A\subseteq B\iff A_{i}\leq B_{i}$ for each $i\in\left\{ 1,\dots,100\right\} $ .

$P\left(A_{i}\leq B_{i}\right)=P\left\{ A_{i}=0\right\} +P\left\{ A_{i}=1\wedge B_{i}=1\right\} =P\left\{ A_{i}=0\right\} +P\left\{ A_{i}=1\right\} P\left\{ B_{i}=1\right\} =\frac{1}{2}+\left(\frac{1}{2}\right)^{2}=\frac{3}{4}$

Then $P\left(A\subseteq B\right)=\left(\frac{3}{4}\right)^{100}$.

on c)

$A\cup B=C\iff A_{i}+B_{i}>0$ for each $i\in\left\{ 1,\dots,100\right\} $

So $P(A\cup B=C)$ can be found as $P(A_1 +B_1>0)^{100}$.

Here $P(A_1 +B_1>0)=1-P(A_1=0\wedge B_1=0)=1-P(A_1=0)P(B_1=0)=1-(\frac{1}{2})^2=\frac{3}{4}$