(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.


  • $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}


\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?

  • $\begingroup$ Concerning a) I suspect that set $D$ is fixed here. How do you come to factor $\frac{1}{101}$? $\endgroup$
    – drhab
    Commented Dec 10, 2014 at 18:47
  • $\begingroup$ Actually it is not mentioned in the exercise what D exactly is, only that it's some subset of the people. So I just assumed it could be any subset of size 0 to 100. This should yield a higher probability than fixing it at some size. $\endgroup$ Commented Dec 10, 2014 at 18:56
  • $\begingroup$ The fact that nothing was mentioned about it is an indication that it is a fixed set. Btw, I think that the cardinality of $D$ is not relevant here. See my answer for that. $\endgroup$
    – drhab
    Commented Dec 10, 2014 at 19:02

1 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}$

  • $\begingroup$ Yes you're right, the probability is the same for all cardinalities. Do you have any idea about b) and c)? $\endgroup$ Commented Dec 10, 2014 at 19:09
  • $\begingroup$ Check me on mistakes. I will be back later. $\endgroup$
    – drhab
    Commented Dec 10, 2014 at 19:52
  • $\begingroup$ Nice approach. I couldn't find any mistake. $\endgroup$ Commented Dec 10, 2014 at 20:28
  • $\begingroup$ @drhab Would you be able to find a flaw with this solution that is different than your solution? I understand your solution, but I am unsure why mine is wrong: $P(A \cup B = C)$ can be thought as one minus the probability that any of the people in $C$ are not befriended. Let $P_i$ mean that neither $A$ nor $B$ befriended person $i$. $ P(A \cup B = C) = 1 - P(P_1 \cup P_2 \cup ... \cup P_{100})$ Now we can use the principal of inclusion and exclusion: $1 - \sum_{i=1}^{100} (-1)^{i + 1}{100 \choose i}(\frac{1}{2})^{2i} = 3.85(10^{-8})$ but $\frac{3}{4} ^ {100} = 3.21(10^{-13})$ $\endgroup$ Commented Sep 13, 2023 at 12:14
  • 1
    $\begingroup$ @nezamjazayeri I think that the expression that you provide is okay. I can rewrite it as:$$\sum_{i=0}^{100}\binom{100}i(-1)^{100-i}(1/4)^i=(-1+1/4)^{100}=(3/4)^{100}$$This is in accordance with my answer. So there must be some flaw in your calculation of the expression. $\endgroup$
    – drhab
    Commented Sep 13, 2023 at 15:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .