Suppose that $G$ is a $n$-vertex graph with $e(G)=\Theta(n^2)$ edges.

Question

Let $S$ be a random subset of $V(G)$, which is constructed by independently including each vertex $V(G)$ with probability 1/2. Define $X:=e(G[S])$ as the number of edges of $G$ which lie completely within $S$. Calculate $\mathbb{E}X$. I keep getting expectation as $n^2/4$, is that right?

Answer 1

Almost. Let us without loss of generality write $V(G) = \{1,2,\dots,n\}$. Then you can write $$ X = \sum_{1\leq u < v\leq n} \mathbf{1}_{u\in S}\mathbf{1}_{v\in S} $$ where $\mathbf{1}_{u\in S}$ is the indicator random variable indicating that $u$ belongs to the (random) set $S$. We only sum over $u<v$ to avoid $u=v$ (self-loops, not allowed in a simple graph) and double-counting ($(u,v)$ and $(v,u)$ are the same edge). Then, by linearity of expectation, $$ \mathbb{E}[X] = \sum_{1\leq u < v\leq n} \mathbb{E}[\mathbf{1}_{u\in S}\mathbf{1}_{v\in S}] = \sum_{1\leq u < v\leq n} \mathbb{E}[\mathbf{1}_{u\in S}]\mathbb{E}[\mathbf{1}_{v\in S}] = \sum_{1\leq u < v\leq n} \frac{1}{2}\cdot \frac{1}{2} = \boxed{\frac{1}{4}\cdot \binom{n}{2}} $$ where the second inequality comes from independence of $\mathbf{1}_{u\in S}$ and $\mathbf{1}_{v\in S}$ (since $u\neq v$, and the choices to include different vertices in $S$ are independent).

Answer 2

Let $X$ be a random variable denoting the number of vertices selected, and let $Y$ be a random variable denoting the number of edges of $G$ that lie completely within $S$. Note that, under my notation, we want to compute $\mathbb{E}[Y]$ rather than $\mathbb{E}[X]$. Also, let $n$ denote the number of vertices in $G$.

Conditioning on the random variable $X$, we have,

$$\mathbb{E}[Y] = \sum_{x = 0}^{n} \mathbb P(X = x) \cdot {E}[Y \mid X = x] $$

How do we compute $P(X = x)$? The key observation is that we have $X \sim \text{Bin}(n, 0.5)$. Thus, we have,

$$P(X = x) = \frac{1}{2^{n}} {n\choose x}.$$

Now, how do we compute $\mathbb{E}[Y \mid X = x]$? For each edge $e = (u, v)$, we require both vertices $u$ and $v$ be in the set we picked. Since our set has size $x$, this can be done in exactly ${x\choose 2} $ ways. Therefore, we have,

$$\mathbb{E}[Y] = \frac{1}{2^n}\sum_{x = 0}^{n} {n \choose x} {x \choose 2} = \frac{1}{2^n}{n\choose 2} \sum_{x = 0}^{n} {n - 2\choose x - 2} = \frac{1}{2^{n}}{n\choose 2} \cdot 2^{n - 2} = \boxed{\frac{1}{4} {n\choose 2}}$$

Note that I used the combinatorial identities ${n\choose m}{m\choose k} = {n\choose k}{n - k\choose m - k}$ and $\sum_{k=0}^{n} {n\choose k} = 2^{n}$.

---

Also, note that $n^2/4$ cannot be correct. Why? Consider a graph on one vertex. With probability $0.5$, we'll include this vertex, and with probability $0.5$, we won't include this vertex. In either case, we end up with exactly zero edges, so there's no way that the expectation for $n = 1$ can be positive as $n^2/4$ suggests. Note that the expression that I computed above has a root at $n = 1$, so the expectation collapses to $0$, as expected.