Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
I don't see why I can "pull $1_B$ out"? –  Hans Parshall Jul 18 '12 at 17:26
    
Hmm -- I'm no longer sure you can -- unfortunately I have to go out -- I'll think about it later when I get back -- sorry... –  joriki Jul 18 '12 at 17:36
    
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
1  
@Hans: You're quite right, of course. However, the correlation is non-positive, so the sum of the variances is still an upper bound for the variance of the sum. I've edited the answer accordingly. –  joriki Jul 19 '12 at 1:39
    
Thanks for this, it's very clear now. I should have noticed that a non-positive correlation actually helped! –  Hans Parshall Jul 19 '12 at 13:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.