Solution: 2015 Winter Final - 20

Author: Michiel Smid

Question

Let $G = (V,E)$ be a graph with vertex set $V$ and edge set $E$, let $n$ be the size of $V$, and let $m$ be the size of $E$. For each vertex of $V$, flip a fair and independent coin. Let $V'$ be the subset of $V$ consisting of all vertices of $V$ whose coin flip resulted in heads. Let $E'$ be the set consisting of all edges $(u,v)$ in $E$ for which both $u$ and $v$ are in $V'$. Define the random variable $X$ to be the number of edges in $E'$. What is the expected value of $X$?

(a)

$m/2$

(b)

$m/16$

(c)

$m/8$

(d)

$m/4$

Solution

Let $X_i$ be 1 if the $i$th edge is in $E’$ and 0 otherwise.

For an edge to be in $E’$, both of its vertices must be in $V’$

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

Now, we need to check how many edges in $E$ are in $E’$ based on the vertices in $V’$

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

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

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

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