Tell me more ×
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.
up vote 1 down vote favorite

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|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
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
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
show 4 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.