Solution: 2015 Fall Final - 22

Author: Michiel Smid

Question

Let $S = \{1,2,\dots,n\}$ and let $T$ be a set of $m$ unordered pairs of distinct elements of $S$. Thus, $$ T \subseteq \{\{i,j\} : 1 \leq i < j \leq n\}. $$ Consider a coin that comes up heads with probability 1/3 and, thus, tails with probability 2/3. For each element of $S$, flip the coin, and let $S'$ be the set consisting of all elements of $S$ whose coin flip resulted in heads. Let $T'$ be the set consisting of all elements $\{i,j\}$ in $T$ for which both $i$ and $j$ are in $S'$.
Let $X$ be the size of the set $T'$. What is the expected value $\mathbb{E}(X)$ of $X$?
Hint: Use indicator random variables.

(a)

$m/9$

(b)

$4n/9$

(c)

$4m/9$

(d)

$n/9$

Solution

Let $X_i$ be 1 if the pair ${i,j}$ is in $T$’ and 0 otherwise.

The probability of $i$ and $j$ being in $S$’ is $ Pr(X_i = 1) = \frac{1}{3} \cdot \frac{1}{3} $

$ Pr(X_i = 1) = \frac{1}{9} $

There are $m$ pairs in $T$, and we are calculating the number of pairs in $T$‘.

Since there are $m$ pairs, we \sum it up $m$ times

$ \mathbb{E}(X) = \sum_{i=1}^{m} 1 \cdot Pr(X_i = 1) $

$ \mathbb{E}(X) = \sum_{i=1}^{m} 1 \cdot \frac{1}{9} $

$ \mathbb{E}(X) = \frac{m}{9} $