This is from my class. Can I have an explanation of what going on in the last equality (i.e. $\operatorname{Var}\left(\varepsilon_{i}\right) s_{i}^{2}=\frac{1}{4} \sum_{i=1}^{k} s_{i}^{2}$)?
- Let $S=\left\{s_{1}, s_{2}, \ldots, s_{k}\right\} \subseteq[n]$ be a largest set with distinct sums (i.e. the sums of elements in all $T \subset S$ are all different).
- Let $X$ be a uniformly random sum from $S$.
- $\Rightarrow X=\sum_{i=1}^{k} \varepsilon_{i} s_{i},$ where each $\varepsilon_{i}$ is independent, uniform on {0,1}.
- Let $\mu:=\mathbb{E}[X]=\sum_{i=1}^{k} \mathbb{E}\left[\varepsilon_{i} s_{i}\right]=\frac{1}{2} \sum_{i=1}^{k} s_{i}$. (Actual value is unimportant)
- Variables $\varepsilon_{i}$ are independent
- $\Rightarrow \operatorname{Var}(X)=\operatorname{Var}\left(\sum_{i=1}^{k} \varepsilon_{i} s_{i}\right)=\sum_{i=1}^{k} \operatorname{Var}\left(\varepsilon_{i}\right) s_{i}^{2}=\frac{1}{4} \sum_{i=1}^{k} s_{i}^{2} \leq \frac{1}{4} n^{2} k$
It follows from the definition. Since $\varepsilon_i$ is a uniform r.v. on $\{0, 1\}$, we have $$ \mathbb E[\varepsilon_i] = \sum_{x \in \{0, 1\}} x \mathbb P(\varepsilon_i = x) = 0\cdot \frac 1 2 + 1 \cdot \frac 1 2 = \frac 1 2, $$ and we similarly obtain $\mathbb E[\varepsilon_i^2] = \frac 1 2$, so $$ \mathrm{Var}(\varepsilon_i) = \mathbb E[\varepsilon_i^2] - \mathbb E[\varepsilon_i]^2 = \frac 1 2 - \frac 1 4 = \frac 1 4. $$ This constant is then taken outside of the sum.