# 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 sets under the equal-slices measure on $[3]^n$, at the expense of localising to a combinatorial subspace.

## Passing between product distributions

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

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

## A product distribution slightly corrupted

Suppose $\mu = \mu_{p_1,p_2,p_3}$ is our basic product measure, and $\mu' = \mu_{p_1',p_2',p_3'}$ is defined by $(p_1',p_2',p_3') = (1-\epsilon)(p_1,p_2,p_3) + \epsilon(q_1,q_2,q_3)$. Then one can calculate that the $\Delta_i$ above equals $-\epsilon(1-q_i/p_i)$, and hence one gets:

Proposition: $d_{TV}(\mu, \mu') \leq a(p,q) \cdot \epsilon\sqrt{n}$, where
$a(p,q) = \sqrt{-1 + \sum_{i=1}^3 q_i^2/p_i}$.

One can bound $a(p,q)$ crudely by

$a(p,q) = \sqrt{-1 + \sum_{i=1}^3 q_i^2/p_i} \leq \sqrt{\sum_{i=1}^3 1/p_i} \leq \sum_{i=1}^3 1/\sqrt{p_i}$.

Recall that the Equal Slices distribution $\overline{\nu}$ is given by first choosing $(p_1, p_2, p_3)$ from the simplex, and then drawing from the product distribution $\mu_{p_1,p_2,p_3}$. Since

$\int_{p_1+p_2+p_3 = 1} (\sum_{i=1}^3 1/\sqrt{p_i}) = O(1)$

(it's $48/5$, I believe), we conclude the following:

Proposition: Let $\gamma$ be the distribution on $[3]^n$ given by the following procedure: (a) pick a random subset $S \subseteq [n]$ by including each coordinate with probability $\epsilon$; (b) draw from the product distribution $\mu_{q_1, q_2, q_3}$ on the $S$ coordinates; (c) draw from $\mu_{p_1, p_2, p_3}$ on the $[n] \setminus S$ coordinates. Then $d_{TV}(\overline{\nu}, \gamma) \leq O(\epsilon \sqrt{n})$.
Corollary: The same would be true if in (b) we drew from Equal Slices on $[3]^S$; this is because Equal Slices is a mixture of product distributions.

In fact, I'm quite certain it would be true if we put any distribution whatsoever on the $S$ coordinates, since $a(p,q)$ could be upper-bounded independently of the $q_i$'s. If we need this later, we can fill in the details.

## Passing from uniform to equal-slices

We will be interested in the case when $(p_1,p_2,p_3) = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ generates the uniform distribution and $(p'_1, p'_2, p'_3)$ is a slight mixture with another distribution. Specifically, say

Definition: $(p'_1, p'_2, p'_3) = (1-\epsilon)(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}) + \epsilon(q_1, q_2, q_3)$.

Then we can calculate:

$\sum_{j=1}^3 p_j \Delta_j^2 = 3(q_1^2 + q_2^2 + q_3^2 - 1/3) \epsilon^2 \leq 3\epsilon^2.$

Hence:

Proposition: In this scenario, $d_{TV}(\mu, \mu') \leq \sqrt{3} \epsilon\sqrt{n}$ independently of $(q_1, q_2, q_3)$.

Recall that equal-slices measure is gotten by first drawing $(q_1, q_2, q_3)$ from the simplex and then drawing from the product distribution generated by $\mu^1_{q_1,q_2,q_3}$. Since the above proposition holds for every choice of $(q_1, q_2, q_3)$, it holds when we average these choices over the simplex. It would also hold if we averaged over $(q_1, q_2, 0)$ drawn from the 2-simplex $q_1 + q_2 = 1$. We conclude:

Theorem: Suppose $\lambda$ is the distribution on $[3]^n$ generated as follows: First we draw a random restriction in which each coordinate is free with probability $\epsilon$ and fixed uniformly with probability $1-\epsilon$. Next, we draw the free coordinates from the equal-slices measure. Then $d_{TV}(\mathrm{uniform}, \lambda) \leq \sqrt{3}\epsilon \sqrt{n}$. Furthermore, this is also true for $\lambda'$, defined in the same way except that the free coordinates are drawn form the equal-slices measure on $[2]^n$.

Corollary: Suppose we change $\lambda$ slightly by also conditioning on at least $\epsilon n/2$ coordinates being left free initially and hence drawn from an equal-slices distribution. Then $d_{TV}(\mathrm{uniform}, \lambda) \leq \sqrt{3}\epsilon \sqrt{n} + \exp(-\Omega(\epsilon n))$. The analogous statement is true for $\lambda'$.

Proof: This follows because the probability of getting too few free coordinates is at most $\exp(-\Omega(\epsilon n))$, by a standard large-deviation bound.

## Passing from equal-slices to uniform

This is a bit easier, which is convenient as we'll want to prove something stronger.

Suppose $A \subseteq [3]^n$ has $\Pr_{\nu}[A] = \delta$, where again $\nu$ denotes equal-slices measure. Recall that we can think of $\nu$ as first choosing $(p_1,p_2,p_3)$ from the simplex and then drawing from the product distribution $\mu^n_{p_1,p_2,p_3}$. The following is easy to check:

Fact: Any distribution $\mu^1_{p_1,p_2,p_3}$ on $[3]$ can be written as a mixture distribution $\alpha \mu^1_{1/3,1/3,1/3} + (1-\alpha) \lambda$, where $\alpha = 3\min\{p_1,p_2,p_3\}$ and $\lambda$ is some other distribution.

Corollary: We can express a draw from $\mu^n_{p_1,p_2,p_3}$ as: (i) forming a set $S \subseteq [n]$ by including each coordinate with probability $1-\alpha$, independently; (ii) fixing the coordinates in $S$ to some string $x$, according to the product distribution $\lambda$; (iii) drawing $y$ uniformly at random from the combinatorial subspace formed by $(x,S)$.

Hence, using the notation $A_x$ for the restriction of $A$ to the combinatorial subspace defined by fixing $x$ into the coordinates $S$, we have

$\delta = \Pr_{\nu}[A] = \mathbf{E}_{p_1+p_2+p_3 = 1} \mathbf{E}_{S,x} \Pr_{y \text{ uniform}}[y \in A_{x}]$.

Hence for any $\eta \gt 0$ we have that with probability at least $\eta$ over the formation of the combinatorial subspace determined by $x$, the uniform measure of $A_x$ is at least $\delta - \eta$.

The only thing that could go somewhat wrong here is that $S$ might be all of $[n]$, or nearly so. But this is quite unlikely. Specifically, one easily calculates that the probability that $\min\{p_1,p_2,p_3\} \leq \eta/8$ is at most $\eta/4$. Assuming this doesn't happen we have $\alpha \geq (3/8)\eta$; thus we expect the number of free coordinates in our combinatorial subspace to be $(3/8)\eta n$, and it will be at least $(\eta/4) n$ except with probability $\exp(-\Omega(\eta n))$. Overall, the probability that everything goes right is at least $\eta - \eta/4 - \exp(-\Omega(\eta n))$. This is positive if $\eta \gg (\log n)/n$.

We conclude:

Theorem: Suppose the set $A$ has equal-slices density $\delta$. Assume that $\eta \geq O(\log n / n)$. Then there exists a combinatorial subspace with at least $(\eta/4) n$ free coordinates on which $A$ has uniform density at least $\delta - \eta$.

### Relative density version

It will useful to have also a "relative density" version of this:

Theorem: Let $\nu$ denote equal-slices measure and let $\mu$ denote uniform measure. Suppose that $A \subseteq B \subseteq [3]^n$, with $\nu(B) = \gamma$, $\nu(A) \geq \delta \nu(B)$. Assume $\eta$ is such that $\eta \gamma \geq O(\log n / n)$. Then there exists a combinatorial subspace with at least $(\eta \gamma / 4) n$ free coordinates on which $\mu(B) \geq \eta \gamma/2$ and $\mu(A) \geq (\delta - \eta) \mu(B)$.

Proof: As in the previous section, think of $\nu$ as first drawing the combinatorial subspace defined by $x$ and then drawing from $\mu$ on this subspace. With regard to the draw of $x$, let $H$ event that either $\mu(B_x) \leq \eta \gamma/2$ or $x$ leaves fewer than $(\eta \gamma/4) n$ coordinates free. We have

$\delta \gamma \leq \mathbf{E}_x[\mu(A_x)] = \Pr[H] \cdot \mathbf{E}_x[\mu(A_x) \mid H] + \Pr[\overline{H}] \cdot \mathbf{E}_x[\mu(A_x) \mid \overline{H}].$

The first summand on the right contributes at most $\eta \gamma/2$ (from when $\mu(B_x) \leq \eta \gamma/2$) plus $\eta\gamma/4 + \exp(-\Omega(\eta \gamma n)) \leq \eta \gamma/2$ (from when $x$ leaves too few coordinates free, by the same argument as in the previous section). Subtracting $\eta \gamma$ from both sides we get

$(\delta - \eta) \gamma \leq \Pr[\overline{H}] \cdot \mathbf{E}_x[\mu(A_x) \mid \overline{H}].$

But since $\gamma = \mathbf{E}_x[\mu(B_x)] \geq \Pr[\overline{H}] \cdot \mathbf{E}_x[\mu(B_x) \mid \overline{H}]$, we have

$\Pr[\overline{H}] \cdot \mathbf{E}_x[(\delta - \eta) \mu(B_x) \mid \overline{H}] \leq \Pr[\overline{H}] \cdot \mathbf{E}_x[\mu(A_x) \mid \overline{H}].$

Clearly then there exists some $x$ for which both $H$ does not occur and

$\mu(A_x) \geq (\delta - \eta) \mu(B_x)$.

This completes the proof.

## An older version of passing from equal-slices to uniform

Suppose we define $\nu$ to be the distribution on $[3]^n$ gotten by first drawing $(p_1, p_2, p_3)$ from the simplex and then drawing from $\mu^n_{p_1,p_2,p_3}$.

Fact: The distribution $\nu$ is the equal-slices measure on $[3]^n$.

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

Next, define $\nu'$ as follows: first draw $(p_1,p_2,p_3)$ from the simplex, then draw from $\mu^n_{p'_1,p'_2,p'_3}$, where $(p'_1, p'_2, p'_3) = (1 - \epsilon)(p_1, p_2, p_3) + \epsilon(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$.

Using the Fact in the first section, we get

Proposition: $d_{TV}(\mu,\mu') \leq \sqrt{c(p_1,p_2,p_3)} \cdot \epsilon \sqrt{n}$, where

$c(p_1,p_2,p_3) = \frac{1}{9p_1} + \frac{1}{9p_2} + \frac{1}{9p_3} - 1$.

Clearly then,

$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}$
.

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

Proposition 2: $d_{TV}(\nu, \nu') \leq O(\epsilon \sqrt{n})$.

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

By Proposition 2,

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

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

$\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].$

Hence:

Theorem: (Weaker than in the previous section.) Suppose $A$ has equal-slices density $\delta$. Then for any $\epsilon$, there exists a combinatorial subspace $(x,S)$ with $|S| \geq \epsilon n$ on which $A$ has uniform-distribution density at least $\delta - O(\epsilon \sqrt{n}) - \exp(-\Omega(\epsilon n))$.

By the way, f this is done over $[k]^n$, we should only have to change $O(\epsilon \sqrt{n})$ to $O(\epsilon \sqrt{kn})$.