Back

Question: 2015 Fall Final - 22

Author: Michiel Smid
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$