Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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
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
do you mean that the only dependence is imposed by conditioning on $\sum{r_i} = 0$? – Sasho Nikolov Jul 19 '12 at 15:19
I'd go through the dimensionality reduction literature. Constructions of this kind are often used for JL-embeddings, and the dependency comes in if you want to derandomize the method. – Suresh Venkat Jul 19 '12 at 17:41
JL = Johnson-Lindenstrauss – Sasho Nikolov Jul 20 '12 at 0:59
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

Your Answer


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

Browse other questions tagged or ask your own question.