Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The classical Kchinchine inequality states that for vector $a=(a_1, \ldots, a_{2m})\in R^{2m}$, for $p\geq 2$, and for independent Rademacher random variables $r_1, \ldots, r_{2m}$, one has $$ E(|\sum_{i=1}^{2m}r_ia_i|^p)^{1/p}\leq C\sqrt{p}\|a\|_2, $$ where $C$ is some (known) constant. Note, Rademacher random variables are such that $P(r_i=1)=P(r_i=-1)=1/2, i=1, \ldots 2m$.

My question: Suppose we have dependent Rademacher random variables. Say, we have extra assumption that the sum $\sum_{i=1}^{2m}r_i=0$. Is there some application in the Computer Science of the Khinchine inequality with this extra condition on the dependence of the Rademacher random variables?

Thank you.

share|cite|improve this question
2  
I do not understand. The inequality does not hold at all with dependent variables. Suppose w.p. 1/2 $r_1 = \ldots = r_m = 1$ and the rest of $r_i$ are -1, and w.p. 1/2 the other way around. – Sasho Nikolov Jul 19 '12 at 5:40
3  
do you mean that the only dependence is imposed by conditioning on $\sum{r_i} = 0$? – Sasho Nikolov Jul 19 '12 at 15:19
1  
JL = Johnson-Lindenstrauss – Sasho Nikolov Jul 20 '12 at 0:59
1  
An observation that may be obvious: if you replace the rademacher r.v. with standard gaussians (and Khintchine is known to hold for any sub-gaussian r.v.), then conditioning of this kind is equivalent to projecting to a lower dimensional space. as a projected standard guassian is a standard gaussian, the conditioning only strengthens the inequality: $\|a\|_2$ can be replaced by $\|\Pi a\|_2$ where $\Pi$ is the projection operator onto the space orthogonal to the all-1s vector. – Sasho Nikolov Jul 20 '12 at 17:21
1  
Well, you can apply it to partition/discrepancy: Imagine you have a set of n elements with weights, and you would like to partition them into two sets, each of exactly n/2 elements, and you would like to minimize the imbalance between the two sets sizes (+1 on one side, -1 on the other side). The above inequality tells you that the higher moments of this RV are concentrated. The problem is that you can get similar bounds by extended versions of Chernoff inequality (I think) and people in computer science know about this stuff... – Sariel Har-Peled Mar 22 '13 at 5:51

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.