# Passing between measures

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

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

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

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

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

$d_H^2(\nu, \lambda) \leq d_H^2(\nu_1, \lambda_1) + d_H^2(\nu_2, \lambda_2)$.

Hence $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})$. In particular, if the Hellinger distance between the two 1-coordinate distributions is small compared to $1/\sqrt{n}$, the overall total variation distance is small.

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

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