2
$\begingroup$

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!

1 Answers 1

2

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$.

  • 0
    Thanks for this, it's very clear now. I should have noticed that a non-positive correlation actually helped!2012-07-19