Passing between measures

In this article we show how to pass from dense sets under the uniform measure on [math]\displaystyle{ [3]^n }[/math] to dense sets under the equal-slices measure on [math]\displaystyle{ [3]^n }[/math], at the expense of localising to a combinatorial subspace. The other direction is possible too; it should be filled in at some point.

---

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. The following basic fact about total variation between product distributions appears, e.g., as Exercise 21 here:

Fact: If we write [math]\displaystyle{ p'_j = (1+\Delta_j) p_j }[/math], then [math]\displaystyle{ d_{TV}(\mu, \mu')^2 \leq (1+(\sum_{j=1}^3 p_j \Delta_j^2))^n - 1 }[/math], and hence [math]\displaystyle{ d_{TV}(\mu,\mu') \leq \sqrt{\sum_{j=1}^3 p_j \Delta_j^2}\sqrt{n} }[/math].

In particular, suppose that [math]\displaystyle{ (p'_1, p'_2, p'_3) = (1 - \epsilon)(p_1, p_2, p_3) + \epsilon(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}) }[/math]. Then we get

Proposition 2: [math]\displaystyle{ d_{TV}(\mu,\mu') \leq \sqrt{c(p_1,p_2,p_3)} \cdot \epsilon \sqrt{n} }[/math], where

[math]\displaystyle{ c(p_1,p_2,p_3) = \frac{1}{9p_1} + \frac{1}{9p_2} + \frac{1}{9p_3} - 1 }[/math]

Next, suppose that we define [math]\displaystyle{ \nu }[/math] to be the distribution on [math]\displaystyle{ [3]^n }[/math] gotten by first drawing [math]\displaystyle{ (p_1, p_2, p_3) }[/math] from the simplex and then drawing from [math]\displaystyle{ \mu^n_{p_1,p_2,p_3} }[/math]. Define [math]\displaystyle{ \nu' }[/math] in the analogous way.

Fact: The distribution [math]\displaystyle{ \nu }[/math] is the equal-slices measure on [math]\displaystyle{ [3]^n }[/math].

This fact is a consequence of the "type 1 Dirichlet integral".

Clearly,

[math]\displaystyle{ d_{TV}(\nu, \nu') \leq \left(\int_{p_1+p_2+p_3 = 1} \sqrt{c(p_1,p_2,p_3)}\right) \cdot \epsilon \sqrt{n} }[/math].

It is elementary to check that the integral is finite; in fact, it should be [math]\displaystyle{ O(\sqrt{k}) }[/math] when we have the analogous situation over [math]\displaystyle{ [k]^n }[/math]. So:

Proposition 2: [math]\displaystyle{ d_{TV}(\nu, \nu') \leq O(\epsilon \sqrt{n}) }[/math].

---

We can view a draw from [math]\displaystyle{ \nu' }[/math] as follows: First, we choose a random set of wildcards [math]\displaystyle{ S }[/math] by including each coordinate independently with probability [math]\displaystyle{ \epsilon }[/math]. Next, choose [math]\displaystyle{ (p_1,p_2,p_3) }[/math] at random from the simplex. Next, choose a string [math]\displaystyle{ x \in [3]^{[n] \setminus S} }[/math] from [math]\displaystyle{ \mu_{p_1,p_2,p_3} }[/math]. Finally, choose [math]\displaystyle{ y \in [3]^n }[/math] uniformly, and output [math]\displaystyle{ (x,y) }[/math].

By Proposition 2,

[math]\displaystyle{ \Pr_\nu[A] - O(\epsilon \sqrt{n}) \leq \Pr_{\nu'}[A] = \mathbf{E}_{S} \mathbf{E}_{p,x} \Pr_y [A]. }[/math]

By a large-deviation bound, the probability that [math]\displaystyle{ |S| \lt \epsilon n / 2 }[/math] is at most [math]\displaystyle{ \exp(-\Omega(\epsilon n)) }[/math]. Renaming [math]\displaystyle{ \epsilon }[/math] as [math]\displaystyle{ 2\epsilon }[/math] for simplicity, we conclude that

[math]\displaystyle{ \Pr_\nu[A] - O(\epsilon \sqrt{n}) - \exp(-\Omega(\epsilon n)) \leq \Pr_{\nu'}[A] = \mathbf{E}_{S}[\mathbf{E}_{p,x} \Pr_y [A] \mid |S| \geq \epsilon n]. }[/math]

Hence:

Theorem: Suppose [math]\displaystyle{ A }[/math] has equal-slices density [math]\displaystyle{ \delta }[/math]. Then for any [math]\displaystyle{ \epsilon }[/math], there exists a combinatorial subspace [math]\displaystyle{ (x,S) }[/math] with [math]\displaystyle{ |S| \geq \epsilon n }[/math] on which [math]\displaystyle{ A }[/math] has uniform-distribution density at least [math]\displaystyle{ \delta - O(\epsilon \sqrt{n}) - \exp(-\Omega(\epsilon n)) }[/math].

As mentioned, if this is done over [math]\displaystyle{ [k]^n }[/math], we should only have to change [math]\displaystyle{ O(\epsilon \sqrt{n}) }[/math] to [math]\displaystyle{ O(\epsilon \sqrt{kn}) }[/math].