# Bounding Variance of a Convolution

Let $G$ be a group with finite subsets $A,B \subseteq G$. Let $k$ be an integer between $1$ and $|A|$ (or |A|/2 if it helps), and let $C$ be a random subset of $A$ of size $k$, chosen uniformly out of all such sets. We take $\mu_C = \frac{|A|}{k}1_C$ (where $1_X$ is an indicator function for a set $X$).

For $f,g : G \rightarrow \mathbb{C}$, we have the convolution $f*g(x) = \sum_{y \in G}f(y)g(y^{-1}x)$.

I was able to show that $\mathbb{E}\left[\mu_C * 1_B\right] = 1_A * 1_B(x)$, but it's also supposed to be "easy to see" that $\operatorname{Var}(\mu_C * 1_B(x)) \leq \frac{|A|}{k} 1_A*1_B(x)$. The bounds for $\operatorname{Var}(\mu_C * 1_B(x))$ that I can come up with all seem to be off by at least an extra factor of $\frac{|A|}{k}$.

Any help is appreciated, thanks!

-

For each $x$, the convolution $\mu_C*1_B(x)$ is a sum over certain values of $\mu_C$. Since one of these values being non-zero doesn't raise the chance of other values being non-zero (in fact lowers it unless $k=|A|$), the correlation between different terms of this sum is non-positive, so the variance of the sum is at most the sum of the variances, which we get by pulling $*1_B(x)$ out of the variance. Then we just have $\mu_C$, which is $\frac{|A|}k$ times an indicator function, with
$$\operatorname{Var}\mu_C=\langle \mu_C^2\rangle-\langle \mu_C\rangle^2=\left(\frac{|A|}k\right)^2\left(\langle1_C\rangle-\langle 1_C\rangle^2\right)\le\left(\frac{|A|}k\right)^2\langle1_C\rangle=\frac{|A|}k\mu_C\;,$$
and then the convolution with $1_B$ yields $\frac{|A|}k1_A*1_B$.
I don't see why I can "pull $1_B$ out"? – Hans Parshall Jul 18 '12 at 17:26
In fact, I'm pretty sure I can't. This would require the random variables $1_C(y_1)$ and $1_C(y_2)$ to be uncorrelated for any $y_1, y_2 \in G$, which isn't true. – Hans Parshall Jul 18 '12 at 18:03