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<t<b} 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.

 

Advertisements

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s