Suppose random variables $X_1$ and $X_2$ contain approximately the same information about a third random variable $\Lambda$, i.e. both of the following diagrams are satisfied to within approximation $ϵ$:

We call $\Lambda$ a "redund" over $X_1,X_2$, since conceptually, any information $\Lambda$ contains about $X$ must be redundantly represented in both $X_1$ and $X_2$ (to within approximation).

Here's an intuitive claim which is surprisingly tricky to prove: suppose we construct a new variable ${\Lambda }^{\prime }$ by sampling from $P\left[\Lambda |X_2\right]$, so the new joint distribution is 

$P[X_1=x_1,X_2=x_2,{\Lambda }^{\prime }={\lambda }^{\prime }]=P[X_1=x_1,X_2=x_2]P[\Lambda ={\lambda }^{\prime }|X_2=x_2]$

By construction, this "resampled" variable satisfies one of the two redundancy diagrams perfectly: $X_1\to X_2\to {\Lambda }^{\prime }$. Intuitively, we might expect that ${\Lambda }^{\prime }$ approximately satisfies the other redundancy diagram as well; conceptually, ${\Lambda }^{\prime }$ (approximately) only contains redundant information about $X$, so $X_2$ contains (approximately) the same information about ${\Lambda }^{\prime }$ as $X$ does, so the resampling operation should result in (approximately, in some sense) the same distribution we started with and therefore (approximately) the same properties.

In this post, we'll prove that claim and give a bound for the approximation error.

Specifically:

Theorem: Resampling (Approximately) Conserves (Approximate) Redundancy

Let random variables $X_1,X_2$, $\Lambda$ satisfy the diagrams $X_1\to X_2\to \Lambda$ and $X_2\to X_1\to \Lambda$ to within $ϵ$, i.e.

$ϵ\ge D_{KL}\left(P\right[X_1,X_2,\Lambda \left]||P\right[X_1,X_2\left]P\right[\Lambda |X_2\left]\right)$

$ϵ\ge D_{KL}\left(P\right[X_1,X_2,\Lambda \left]||P\right[X_1,X_2\left]P\right[\Lambda |X_1\left]\right)$

Also, assume $P[X,\Lambda ]>0$.

Construct ${\Lambda }^{\prime }$ by sampling from $P\left[\Lambda |X_2\right]$, so $P[X_1,X_2,{\Lambda }^{\prime }]=P[X_1,X_2]P[\Lambda ={\lambda }^{\prime }|X_2]$. Then $X_1\to X_2\to {\Lambda }^{\prime }$ is perfectly satisfied by construction, and $X_2\to X_1\to {\Lambda }^{\prime }$ is satisfied to within $9ϵ$, i.e.

$9ϵ\ge D_{KL}\left(P\right[X_1,X_2,{\Lambda }^{\prime }\left]||P\right[X_1,X_2\left]P\right[{\Lambda }^{\prime }|X_1\left]\right)$

---

In diagrammatic form:

Notation

We will use the shorthand $D_{KL}(<\text{diagram over X}>)$ to mean $D_{KL}\left(P\right[X\left]||{\prod }_{i}P\right[X_i|X_{pa\left(i\right)}\left]\right)$. For instance, $D_{KL}(X_1\to X_2\to \Lambda )$  is shorthand for $D_{KL}\left(P\right[X_1,X_2,\Lambda \left]||P\right[X_1\left]P\right[X_2|X_1\left]P\right[\Lambda |X_2\left]\right)$, which is equivalent to $D_{KL}\left(P\right[X,\Lambda \left]||P\right[X\left]P\right[\Lambda |X_2\left]\right)$.

We will work with nats for mathematical convenience (i.e. all logarithms are natural logs).

Proof

The proof proceeds in three steps:

• From $\Lambda$, we can construct a new variable $\Gamma$ which is equal to $\Lambda$ with probability $p$ and is otherwise a constant. Then the errors on all diagrams in the theorem for $\Gamma$ are the same as the corresponding errors for $\Lambda$, but scaled down by factor $p$. This allows us to focus only on the regime of arbitrarily small errors, and obtain a global bound from that regime.
• Within the regime of arbitrarily small errors, $D_{KL}\left(P||Q\right)$ is approximately (to second order) equal to twice the Hellinger distance, $2{\sum }_X(\sqrt{P\left[X\right]}-\sqrt{Q\left[X\right]}{)}^2$. Hellinger distance is a straightforward Euclidean distance metric, so we can use standard geometric reasoning on it.
• The Hellinger distance between $P\left[\Lambda |X_2\right]$ and $P\left[\Lambda |X\right]$, between $P\left[\Lambda |X\right]$ and $P\left[\Lambda |X_1\right]$, and between $P\left[\Lambda |X_1\right]$ and $P\left[{\Lambda }^{\prime }|X_1\right]$ are all small, so end-to-end the Hellinger distance between $P\left[\Lambda |X_2\right]$ and $P\left[{\Lambda }^{\prime }|X_1\right]$ is small. That yields the bound we're after.

Step 1: Scaling Down The Errors

First we construct the new variable $\Gamma$ as a stochastic function of $\Lambda$. Specifically, $\Gamma$$=\Lambda$ with probability $p$, else $\Gamma$ is a constant $C$, where $C$ is outside the support of $\Lambda$ (so when we see $\Gamma =C$, we gain no information about $\Lambda$).

A little algebra confirms that $\Gamma$'s errors are simply $\Lambda$'s errors scaled down by $p$:

$D_{KL}\left(P\right[X,\Gamma \left]||P\right[X\left]P\right[\Gamma |X_i\left]\right)$

$=E_X\left[P\right[\Gamma =C\left]\right(lnP[\Gamma =C|X]-lnP[\Gamma =C|X_i])+{\sum }_{\lambda }P[\Gamma =\lambda |X\left]\right(lnP[\Gamma =\lambda |X]-lnP[\Gamma =\lambda |X_i]\left)\right]$

$=E_X\left[\right(1-p\left)\right(ln(1-p)-ln(1-p))+{\sum }_{\lambda }pP[\Lambda =\lambda |X\left]\right(ln\left(pP\right[\Lambda =\lambda |X\left]\right)-ln\left(pP\right[\Lambda =\lambda |X_i\left]\right)\left)\right]$

$=p{E}_X\left[{\sum }_{\lambda }P\right[\Lambda =\lambda |X\left]\right(ln\left(P\right[\Lambda =\lambda |X\left]\right)-ln\left(P\right[\Lambda =\lambda |X_i\left]\right)\left)\right]$

$=p{D}_{KL}\left(P\right[X,\Lambda \left]||P\right[X\left]P\right[\Lambda |X_i\left]\right)$

Similarly, constructing ${\Gamma }^{\prime }$ just like ${\Lambda }^{\prime }$ (i.e. $P[X,{\Gamma }^{\prime }]=P\left[X\right]P[\Gamma ={\gamma }^{\prime }|X_2]$) is equivalent to constructing ${\Gamma }^{\prime }$ as a stochastic function of ${\Lambda }^{\prime }$ where ${\Gamma }^{\prime }={\Lambda }^{\prime }$ with probability $p$, else ${\Gamma }^{\prime }$ is $C$. So, by the same algebra as above,

$D_{KL}\left(P\right[X,{\Gamma }^{\prime }\left]||P\right[X\left]P\right[{\Gamma }^{\prime }|X_i\left]\right)=p{D}_{KL}\left(P\right[X,{\Lambda }^{\prime }\left]||P\right[X\left]P\right[{\Lambda }^{\prime }|X_i\left]\right)$

The upshot: if there exists a distribution over variables $X_1,X_2,\Lambda$ for which

$D_{KL}(X_2\to X_1\to {\Lambda }^{\prime })>n\cdot \text{max}\left(D_{KL}\right(X_1\to X_2\to \Lambda ),D_{KL}(X_2\to X_1\to \Lambda \left)\right)$

then there also exists a distribution satisfying the same inequality with all $D_{KL}$'s arbitrarily small^[1]. Flipping that statement around: if there does not exist any distribution for which the $D_{KL}$'s are all arbitrarily small and the inequality is satisfied, then there does not exist any distribution for which the inequality is satisfied.

In other words: if we can show

$D_{KL}(X_2\to X_1\to {\Lambda }^{\prime })\le n\cdot \text{max}\left(D_{KL}\right(X_1\to X_2\to \Lambda ),D_{KL}(X_2\to X_1\to \Lambda \left)\right)\le nϵ$

in the regime where all the $D_{KL}$'s are arbitrarily small, then the same inequality is also established globally, proving our theorem. The rest of the proof will therefore show

$D_{KL}(X_2\to X_1\to {\Lambda }^{\prime })\le n\cdot \text{max}\left(D_{KL}\right(X_1\to X_2\to \Lambda ),D_{KL}(X_2\to X_1\to \Lambda \left)\right)$

in the regime where all the $D_{KL}$'s are arbitrarily small. In particular, we'll use a second order approximation for the $D_{KL}$'s.

Step 2: Second Order Approximation

Validity

Before we can use a second order approximation of the $D_{KL}$'s, we need to show that small $D_{KL}$ implies that second order approximationis valid.

For that purpose, we use the Hellinger-KL inequality:

$D\left(P||Q\right)\ge 2ln\frac{2}{2-H^2(P,Q)}$

where $H^2(P,Q):={\sum }_X(\sqrt{P\left[X\right]}-\sqrt{Q\left[X\right]}{)}^2$ is the squared Hellinger distance.^[2]

Using standard logarithm inequalities, we can weaken the Hellinger-KL inequality to

$D\left(P||Q\right)\ge H^2(P,Q)$

So, as $D_{KL}\left(P||Q\right)$ goes to 0, the Hellinger distance goes to 0, and therefore $\sqrt{P}$ and $\sqrt{Q}$ are arbitrarily close together in standard Euclidean distance. Since $D_{KL}$ is smooth (for strictly positive distributions, which we have assumed), we can therefore use a second order approximation (with respect to $\sqrt{P}-\sqrt{Q}$) for our arbitrarily small $D_{KL}$'s.

Expansion

Now for the second order expansion itself.

Our small quantity is $\delta \left[X\right]:=\sqrt{P\left[X\right]}-\sqrt{Q\left[X\right]}$. Then

$D_{KL}\left(P||Q\right)={\sum }_{X}P\left[X\right]\left(lnP\right[X]-2ln\sqrt{Q\left[X\right]})$

$={\sum }_{X}P\left[X\right]\left(lnP\right[X]-2ln(\sqrt{P\left[X\right]}-\delta \left[X\right]\left)\right)$

$={\sum }_{X}P\left[X\right]\left(lnP\right[X]-2ln(\sqrt{P\left[X\right]})+2\frac{\delta \left[X\right]}{\sqrt{P\left[X\right]}}+2\frac{1}{2}(\frac{\delta \left[X\right]}{\sqrt{P\left[X\right]}}{)}^2)+o({\delta }^3)$

$={\sum }_{X}2\sqrt{P\left[X\right]}\delta \left[X\right]+\delta [X{]}^2+o({\delta }^3)$

To simplify that further, we can use the sum-to-1 constraints on the distributions: $\sqrt{Q\left[X\right]}=\sqrt{P\left[X\right]}-\delta \left[X\right]$ implies

${\sum }_{X}Q\left[X\right]={\sum }_X(\sqrt{P\left[X\right]}-\delta [X]{)}^2={\sum }_{X}P[X]-2\sqrt{P\left[X\right]}\delta [X]+\delta [X{]}^2$

so ${\sum }_{X}2\sqrt{P\left[X\right]}\delta \left[X\right]={\sum }_X\delta [X{]}^2$. That simplifies our second order approximation to

$D_{KL}\left(P||Q\right)=2{\sum }_X\delta [X{]}^2+o({\delta }^3)$

$=2{\sum }_X(\sqrt{P\left[X\right]}-\sqrt{Q\left[X\right]}{)}^2+o({\delta }^3)$

i.e. in the second order regime $D_{KL}$ is twice the Hellinger distance.

Combining this with Step 1, we've now established that if we can prove our desired bound for Hellinger distances rather than $D_{KL}$, then the bound also applies globally for $D_{KL}$ errors. So now, we can set aside the notoriously finicky KL divergences, and work with good ol' Euclidean geometry.

Step 3: Good Ol' Euclidean Geometry

Writing everything out in the second order regime, our preconditions say

$ϵ\ge 2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_2\right]}{)}^2]$

$ϵ\ge 2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_1\right]}{)}^2]$

and we want to bound

$2E_X\left[{{\sum }_{\Lambda }}^{\prime }\right(\sqrt{P\left[{\Lambda }^{\prime }|X\right]}-\sqrt{P\left[{\Lambda }^{\prime }|X_1\right]}{)}^2]$

$=2E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X_2\right]}-\sqrt{{\sum }_{X_2^{\prime }}P\left[\Lambda |X_2^{\prime }\right]P\left[X_2^{\prime }|X_1\right]}{)}^2]$

That last expression has a Jensen vibe to it, so let's use Jensen's inequality.

Jensen

We're going to use Jensen's inequality on the squared Hellinger distance, so we need to establish that squared Hellinger distance is convex as a function of the distributions $P,Q$.

Differentiating $(\sqrt{p}-\sqrt{q}{)}^2$ twice with respect to $(p,q)$ yields the Hessian

$\frac{1}{2}\frac{1}{\sqrt{pq}}\left(\begin{array}{cc}\frac{q}{p}& -1\\ -1& \frac{p}{q}\end{array}\right)$

Note that one column is the other column multiplied by $-\frac{p}{q}$, so one of the eigenvalues is 0. The trace is positive, so the other eigenvalue is positive. Thus, the function is (non-strictly) convex.

Now, we'll use Jensen's inequality on

$ϵ\ge E_X\left[{\sum }_{\Lambda }\right(\sqrt{P\left[\Lambda |X\right]}-\sqrt{P\left[\Lambda |X_2\right]}{)}^2]$