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

<p>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?</p>

<p>Thank you.</p>

CC BY-SA 3.0
2012-07-19T05:40:13.330Z
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
CC BY-SA 3.0
2012-07-19T15:19:54.343Z
do you mean that the only dependence is imposed by conditioning on $\sum{r_i} = 0$?
Sasho Nikolov
CC BY-SA 3.0
2012-07-19T17:41:56.947Z
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
CC BY-SA 3.0
2012-07-19T22:53:33.970Z
@Sasho Nikolov: yes, I ment that the only dependence is imposed by conditioning $\sum_i r_i=0$.
David
CC BY-SA 3.0
2012-07-19T22:54:28.867Z
@Suresh Venkant: What is JL embeddings? Could you provide some literature, please. Thank you.
David
CC BY-SA 3.0
2012-07-20T00:59:53.487Z
JL = Johnson-Lindenstrauss
Sasho Nikolov
CC BY-SA 3.0
2012-07-20T17:21:28.557Z
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
CC BY-SA 3.0
2013-03-22T05:51:17.790Z
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
<linear-algebra><pr.probability>
application for the Kchinchine inequality in Computer Science
David
# application for the Kchinchine inequality in Computer Science

(Asked by: username_0 on 2012-07-19)

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.

**Tags:** linear-algebra, pr.probability

> **Comments:**
> **username_1**: 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.  
> **username_1**: do you mean that the only dependence is imposed by conditioning on $\sum{r_i} = 0$?  
> **username_2**: 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.  
> **username_0**: @username_1: yes, I ment that the only dependence is imposed by conditioning $\sum_i r_i=0$.  
> **username_0**: @Suresh Venkant: What is JL embeddings? Could you provide some literature, please. Thank you.  
> **username_1**: JL = Johnson-Lindenstrauss  
> **username_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.  
> **username_3**: 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...  

---

## 0 answers

