Sampling from Near-identical Distributions

In this section we prove a technical lemma that is needed for the proof of Lemma 3.4.

Lemma B.1   Let $P$ and $Q$ be two different distributions over the finite set $X$ such that $\Vert P - Q \Vert _{L_1} \le \varepsilon$, and $p\in X$ is sampled from distribution $P$. Then $q \in X$ can be selected so that its distribution is $Q$, but $\Pr(p \ne q) \le \varepsilon$.

Naturally, $q$ will not be independent from $p$.

Proof. Let us define the sets

$$X^+ := \{ x\in X \mid P(x) > Q(x) \}$$

$$X^- := \{ x\in X \mid P(x) \le Q(x) \}.$$

Furthermore, define the distributions¹¹

$$R(x) := \begin{cases} \frac{Q(x)-P(x)}{ Q(X^-) - P(X^-)} & \text{if $x\in X^-$}, \\ 0 & \text{otherwise} \end{cases}\text{ and}$$

$$S(x) := \begin{cases} 0 & \text{if $x\in X^+$, with probability $Q(p)... ...(P(p)-Q(p))/P(X^+)$}, \\ 0 & \text{if $x\in X^-$}. \end{cases}$$

The denominator in the definition of $R$ is positive, because for all $x \in X^-$, $Q(x)-P(x)$ is non-negative, therefore $Q(X^-)-P(X^-)$ is zero only if $Q(x)=P(x)$ over $X^-$. In this case $Q(x)=P(x)$ over $X^+$ by the same reasoning, which means $P \equiv Q$, but $P$ and $Q$ are different.

It is easy to check that $R$ is indeed a distribution over $X$ (with support set $X^-$).

Let $r$ and $s$ be independent random variables from distributions $R$ and $S$, respectively. Now define $q$ as follows:

$$q := \begin{cases}p & \text{if $p \in X^-$}, \\ p & \text{if $p \in X^+$\ and $s=0$}, \\ r & \text{if $p \in X^+$\ and $s=1$}, \\ \end{cases}$$ (13)

We claim that the such defined $q$ is suitable. Indeed, by Equation 13

$$\Pr(p\!\ne\!q) = \Pr(p \in X^+, s=1) = \sum_{x \in X^+}\Pr(p=x, s=1)$$

$$= \sum_{x \in X^+} \Pr(p = x) \Pr(s=1 \vert p=x)$$

$$= \sum_{x \in X^+} P(x) \cdot \frac{P(x)-Q(x)}{P(x)} \le \Vert P - Q \Vert _{L_1} \le \varepsilon .$$

Furthermore,

$$\Pr(q\!=\!x) = \Pr(q=x \vert p\in X^-) \Pr(p\in X^-)$$

$$+ \Pr(q=x \vert p\in X^+, s=0) \Pr(p\in X^+, s=0)$$

$$+ \Pr(q=x \vert p\in X^+, s=1) \Pr(p\in X^+, s=1)$$

$$= \Pr(p=x \vert p\in X^-) \Pr(p\in X^-)$$

$$+ \Pr(p=x \vert p\in X^+, s=0) \Pr(p\in X^+, s=0)$$

$$+ \Pr(r=x \vert p\in X^+, s=1) \Pr(p\in X^+, s=1).$$

By applying Bayes' Theorem on each term, we get

$$\Pr(q\!=\!x) = \Pr(p\in X^- \vert p=x ) \Pr(p=x)$$ (14)

$$+ \Pr(p\in X^+, s=0 \vert p=x) \Pr(p=x)$$

$$+ \Pr(p\in X^+, s=1 \vert r=x) \Pr(r=x).$$

We calculate each term of Equation 14 separately, both for $x\in X^+$ and $x \in X^-$. First assume that $x \in X^-$. Then

$$\Pr(p\in X^- \vert p=x ) \Pr(p=x) = 1 \cdot P(x),$$

$$\Pr(p\in X^+, s=0 \vert p=x) \Pr(p=x) = \Pr(p\in X^+ \vert p=x) \Pr(s=0 \vert p\in X^+, p=x) P(x)$$

$$= 0 \cdot \Pr(s=0 \vert p\in X^+, p=x) P(x) = 0,$$

$$\Pr(p\in X^+, s=1 \vert r=x) \Pr(r=x) = \Pr(s=1 \vert p\in X^+, r=x) \Pr(p\in X^+ \vert r=x) \Pr(r=x)$$

$$= \Pr(s=1 \vert p\in X^+) \Pr(p\in X^+) \Pr(r=x)$$

$$= \frac{P(X^+) - Q(X^+)}{P(X^+)} \cdot P(X^+) \frac{Q(x)-P(x)}{Q(X^-)-P(X^-)}$$

$$= Q(x)-P(x).$$

Before the last equation we used the definition of $S(x)$, and in the last equation we have used the equality $Q(X^-)-P(X^-) = P(X^+)-Q(X^+)$, which is true because $P(X^-)+P(X^+) = Q(X^-)+Q(X^+) = 1$.

Now let us consider the case $x\in X^+$.

$$\Pr(p\in X^- \vert p=x ) \Pr(p=x) = 0 \cdot P(x) = 0,$$

$$\Pr(p\in X^+, s=0 \vert p=x) \Pr(p=x) = \Pr(p\in X^+ \vert p=x) \Pr(s=0 \vert p\in X^+, p=x) P(x)$$

$$= 1 \cdot \frac{Q(x)}{P(x)} P(x) = Q(x),$$

$$\Pr(p\in X^+, s=1 \vert r=x) \Pr(r=x) = \Pr(p\in X^+, s=1 \vert r=x) \cdot 0 = 0.$$

In both cases we get $\Pr(q=x) = Q(x)$, which was to be proven. $\qedsymbol$