Passing between measures

In this article we show how to pass between dense sets under the uniform measure on [math]\displaystyle{ [3]^n }[/math] and dense sents under the equal-slices measure on [math]\displaystyle{ [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]\displaystyle{ p_1 + p_2 + p_3 = 1 }[/math], let [math]\displaystyle{ \mu^n_{p_1,p_2,p_3} }[/math] denote the product distributions on [math]\displaystyle{ [3]^n }[/math] where each coordinate is independently chosen to be [math]\displaystyle{ j }[/math] with probability [math]\displaystyle{ p_j }[/math], [math]\displaystyle{ j=1,2,3 }[/math].

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

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

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

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

Hence [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ (p'_1, p'_2, p'_3) }[/math] is a mixture of the 1-coordinate distributions [math]\displaystyle{ (p_1,p_2,p_3) }[/math] and [math]\displaystyle{ (1/3, 1/3, 1/3) }[/math], with mixing weights [math]\displaystyle{ 1-\epsilon }[/math] and [math]\displaystyle{ \epsilon }[/math], then [math]\displaystyle{ 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>.