Let $S$ = $\{v_1, v_2, ..., v_n\}$ denote a random subset of a Hamming hypercube of dimension $d$, where $n = |S|$ and $n \leq 2^d$. If $v_i$ = $\langle x^i_1x^i_2... x^i_d\rangle$ for all $i \in [1,n]$, then what's the expected sum of all $x^i_1$ (the first "coordinate" of a vertex $v_i$) for all $i \in [1,n]$? Is it $\frac{n}{2}$?

3

$\begingroup$
$\endgroup$

Yes. There is an involution $\phi(x_1,\cdots,x_d)=(1-x_1,\cdots,1-x_d)$ which can extend to subsets by defining $\phi(S)=\{\phi(v_i)\vert v_i\in S\}$. If $X$ is the random variable which takes the value of the sum of all first coordinates then we have $$\mathbb E[X]=\frac{1}{2}\mathbb E[X+\phi(X)]=\frac{n}{2}$$ as expected.