Passing between measures

From Polymath1Wiki
Revision as of 08:47, 6 March 2009 by Ryanworldwide (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

In this article we show how to pass between dense sets under the uniform measure on [math][3]^n[/math] and dense sents under the equal-slices measure on [math][3]^n[/math], at the expense of localising to a combinatorial subspace.

Let's first show how to pass between two product distributions. Given [math]p_1 + p_2 + p_3 = 1[/math], let [math]\mu^n_{p_1,p_2,p_3}[/math] denote the product distributions on [math][3]^n[/math] where each coordinate is independently chosen to be [math]j[/math] with probability [math]p_j[/math], [math]j=1,2,3[/math].

Let [math]A \subseteq [3]^n[/math], which we can think of as a set or as an event. We are interested in [math]A[/math]'s probability under different product distributions; say, [math]\mu = \mu^n_{p_1,p_2,p_3}[/math] and [math]\mu' = \mu^n_{p'_1,p'_2,p'_3}[/math].

By definition, [math]|\mu(A) - \mu'(A)| \leq d_{TV}(\mu, \mu')[/math], where [math]d_{TV}[/math] denotes total variation distance. Since the measures are product measures, it's more convenient to work with Hellinger distance [math]d_{H}[/math] (see this article for background information). It is known that [math]d_{TV} \leq d_{H}[/math].

The convenient aspect of Hellinger distance is that if [math]\nu = \nu_1 \times \nu_2[/math], [math]\lambda = \lambda_1 \times \lambda_2[/math] are any two product distributions then we have the "triangle inequality"

[math]d_H^2(\nu, \lambda) \leq d_H^2(\nu_1, \lambda_1) + d_H^2(\nu_2, \lambda_2)[/math].

Hence [math]d_H(\mu, \mu') \leq \sqrt{n} d_H(\mu^1_{p_1,p_2,p_3}, \mu^1_{p'_1,p'_2,p'_3})[/math]. In particular, if the Hellinger distance between the two 1-coordinate distributions is small compared to [math]1/\sqrt{n}[/math], the overall total variation distance is small.

To bound these 1-coordinate Hellinger distances we can use the fact that [math]d_H \leq \sqrt{2 d_{TV}}[/math]. Or if you are desperate to save small constant factors, one can check:

Fact: If the 1-coordinate distribution [math](p'_1, p'_2, p'_3)[/math] is a mixture of the 1-coordinate distributions [math](p_1,p_2,p_3)[/math] and [math](1/3, 1/3, 1/3)[/math], with mixing weights [math]1-\epsilon[/math] and [math]\epsilon[/math], then [math]d_{H}(\mu^1_{p_1,p_2,p_3}, \mu^1_{p'_1,p'_2,p'_3}) \sim \sqrt{\epsilon}[/math] for small $\epsilon$, and is always at ost \leq \sqrt{2\epsilon}</math>.