## Notes of Ron Peled’s talk

${k}$-wise independence and the moment problem

Let ${X}$, ${Y}$ be ${\{ 0,1 \}^n}$-valued random variables, ${Y}$ fully independent (say uniformly distributed), and ${X}$ ${k}$-wise independent. Which Boolean functions are fooled by ${X}$, i.e. ${\mathop{\mathbb P}_{X}(f=1)}$ is close to ${\mathop{\mathbb P}_{Y}(f=1)}$ ?

1. ${k}$-wise independence

1.1. Definition

Definition 1 Say ${X}$ is ${k}$-wise independent with marginal ${p}$ if for every ${i_1 ,\ldots, i_k}$, ${X_{i_1} ,\ldots, X_{i_k}}$ are independent, and ${\mathop{\mathbb P}(X_i =1)=p}$. The set of ${k}$-wise independent distributions is denoted by ${A(n,k,p)}$.

Note ${A(n,k,p)}$ is a convex set.

Example 1 Let ${X_i}$, ${i=1,\ldots,n-1}$, be ${\{ 0,1 \}}$-valued, independent, and set ${X_n =\sum_{i=1}^{n-1} X_i}$ mod ${2}$. Then ${X\in A(n,n-1,p)}$.

1.2. Construction

Let ${p=\frac{1}{2}}$. Let ${U}$ be a ${k}$-dimensional linear subspace of ${{\mathbb Z}_2^n}$. Let ${X}$ be ${U}$-valued and uniformly distributed in ${U}$. Assume that ${X}$ is ${k}$-wise independent. Then every projection of ${U}$ to ${k}$ coordinates is onto. In particular, every vector in ${U^{\bot}}$ has at least ${k}$ entries equal to ${1}$. In other words, ${U^{\bot}}$ is an error correcting code with distance ${k+1}$.

1.3. Independence sensitivity

Let ${f:\{ 0,1 \}^n \rightarrow\{ 0,1 \}}$. The independence sensitivity of ${f}$ is the ratio ${\max/\min}$ of values of ${\mathop{\mathbb P}(f=1)}$ over ${A(n,k,p)}$.

Example 2 ${f=}$ percolation, i.e. detects

How does it behave under ${k}$-wise independence ? Ori will tell tomorrow.

Example 3 ${f=}$ parity is very sensitive to independence, since our example of ${n-1}$-independent distribution makes ${\mathop{\mathbb P}(f=1)}$ fall to ${0}$.

Linear functions are sensitive, in general.

Example 4 ${f=}$ majority is independence stable.

Proposition 2 If ${X_n \in A(n,k_n,\frac{1}{2})}$ and ${k_n}$ tends to infinity, then ${\mathop{\mathbb P}(f(X_n)=1)}$ tends to ${\frac{1}{2}}$.

Nevertheless, Ori will decribe tomorrow a function, close to Majority, which is noise stable, but not independence stable.

Proof: The first ${k}$ moments of ${S_n =\frac{\sum X_i -n/2}{\sqrt{n/4}}}$ coincide with those of an independent variable. By central limit theorem, if ${k_n}$ tends to infinity, all its moments tend to the moments of ${N(0,1)}$. Since ${N(0,1)}$ is determined by its moments, ${S_n}$ converges to ${N(0,1)}$ in law. $\Box$

Here is a quantitative version.

Theorem 3

$\displaystyle \begin{array}{rcl} \frac{C}{\sqrt{k\log k}}\leq\max_{A(n,k,p)}\mathop{\mathbb P}(Maj=1)-\frac{1}{2}\leq \frac{C}{\sqrt{k}}. \end{array}$

Example 5 Tribes is independence stable.

2. The And function

Example 6 And ${=1_{\{X=(0,0,\ldots,0)\}}}$. If ${X}$ comes from an error-corrector code ${C}$, then ${\mathop{\mathbb P}(\textrm{And}(X)=1)=\frac{|C|}{2^n}}$.

For ${p\geq \frac{1}{2}}$ and for all ${k\leq n-1}$, ${m(n,k,p):=\min_{A(n,k,p)}\mathop{\mathbb P}(X=(0,0,\ldots,0))=0}$.

Theorem 4 For ${p< \frac{1}{2}}$, define

$\displaystyle \begin{array}{rcl} n_c (k,p):=\min\{n\,;\,m(n,k,p)=0\}. \end{array}$

Then

$\displaystyle \begin{array}{rcl} n_c (k,p)\geq \frac{k}{2p}+1 \textrm{ if$

If ${p=\frac{1}{q}}$, ${q}$ a prime power, then

$\displaystyle \begin{array}{rcl} n_c (k,p)\leq C\frac{k}{p}\log\frac{1}{p}. \end{array}$

Define ${M(n,k,p):=\min_{A(n,k,p)}\mathop{\mathbb P}(X=(0,0,\ldots,0))}$.

Proposition 5 For ${k\ll n}$,

$\displaystyle \begin{array}{rcl} M(n,k,p)\leq (\frac{c(1-p)k}{pn})^{\lfloor k/2 \rfloor}. \end{array}$

Proof: One estimates ${\mathop{\mathbb P}(\sum_{i=1}^n X_i =0)}$. $\Box$

Conversely, error correcting codes provide lower bounds ${M(n,k,p)\geq (\frac{ck}{n})^K}$, ${K>\lfloor k/2 \rfloor}$. So upper and lower bounds match only when ${p=\frac{1}{2}}$. Where is the truth ?

Theorem 6

$\displaystyle \begin{array}{rcl} M(n,k,p)\sim\frac{(1-p)^n}{\mathop{\mathbb P}(Bin(n,p)\leq k/2}. \end{array}$

The proof relies on the theory of the moment problem.

3. Crash course on the moment problem

3.1. Symmetrization

Given random variable ${X}$, define ${X^s}$ as follows: Sample ${X}$ and then apply a random permutation to it. Then ${\mathop{\mathbb P}(X^s =0)=\mathop{\mathbb P}(X=0)}$ and ${X^s}$ is ${k}$-wise independent if ${X}$ is. Observe that the distribution of ${X^s}$ is entirely determined by the distribution of ${S=\sum_{i=1}^n X_i^s}$. Its ${k}$ first moments coincide with those of the binomial distribution. Conversely, any such distribution gives a symmetric ${k}$-wise independent distribution ${X^s}$. So ${M(n,k,p)}$ can be computed by maximizing the linear function ${\mathop{\mathbb P}(S=0)}$ over all distributions with prescribe ${k}$ first moments. By LP duality,

$\displaystyle \begin{array}{rcl} M(n,k,p)=\min \mathop{\mathbb E}(P(Bin(n,p))) \end{array}$

over all polynomials ${P}$ of degree at most ${k}$ such that ${P(0)=1}$, ${P(i)\geq 0}$ for all ${i\in [n]}$.

3.2. The classical moment problem

Reference books: Krein-Nutelmann, Karlin-Studden.

Given interval ${[a,b]}$ and real numbers ${m_1 ,\ldots,m_k}$, consider all probability distributions ${X}$ supported on ${[a,b]}$ with ${\mathop{\mathbb E}(X^j)=m_j}$ for all ${j\leq k}$. Study ${\mathop{\mathbb P}(X=t)}$ or ${\mathop{\mathbb P}(X\geq t)}$.

We are interested in the interior of the space of distributions with prescribed moments ${m_1 ,\ldots,m_k}$. Define index function to be ${2}$ on ${(a,b)}$ and ${1}$ on ${a}$ and ${b}$. The index of a random variable is the sum of indices of numbers in its support.

1. There are exactly two distributions with index ${k+1}$ (known as principal respresentations), and none with lower index.
2. There is exactly a ${1}$-parameter family of index ${\leq k+2}$ distributions (known as canonical representation).

They maximize ${\mathop{\mathbb P}(X=t)}$: ${\max\mathop{\mathbb P}(X=t)}$ is achieved by the canonical representation if ${a and by the principal representation if ${t=a}$ or ${t=b}$.

The Chebyshev-Markov-Stieltjes inequality states that

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(S_t >t)\leq \mathop{\mathbb P}(S>t)\leq \mathop{\mathbb P}(S\geq t)\leq \mathop{\mathbb P}(S_t \geq t). \end{array}$

It follows that ${\mathop{\mathbb E}(f(S))}$ is extremal on principal representations for a large class of functions ${f}$.

Explicit expressions are given in terms of orthogonal polynomial (Krawtchouk polynomials for ${Bin(n,p)}$).

Theorem 7

$\displaystyle \begin{array}{rcl} \max_{X}\mathop{\mathbb P}(X=t)\leq\frac{1}{} \end{array}$

3.3. Application

We get upper bounds on ${M(n,k,p)}$, not quite sharp since our random variables are integer valued.

We also get lower bounds.

Theorem 8 (Markov, Lukacs) Every polynomial which is nonnegative on ${[a,b]}$ is of the form

$\displaystyle \begin{array}{rcl} P(X)=Q(X)^2 +(X-a)(b-X)R(X)^2 . \end{array}$

Using this,

$\displaystyle \begin{array}{rcl} \max_{S}\mathop{\mathbb P}(S=t)\leq \min_{Q,\,Q(t)=1} \mathop{\mathbb E}(Q(S)^2) \end{array}$

which is expressible in terms of orthogonal polynomials. We can go through the whole calculation (Krawtchouk polynomials) and obtain Theorem 6.