Let $X$ be a random variable and $Y=f(X)$ where $f$ is a deterministic function. Moreover, assume that there exists a deterministic function $g(.)$ such that the following probability is small. \begin{align} \mathbb{P}[g(Y)\neq X]\leq\delta. \end{align} Assume that $X'$ is another random variable which is close to $X$ in terms of total variation distance, i.e., $\|p_X-p_{X'}\|_1\leq\epsilon$. What can be said about the following possibility? \begin{align} \mathbb{P}[g(f(X'))\neq X']\leq?. \end{align}


2 Answers 2


$\newcommand\de\delta\newcommand\ep\epsilon$Let $h:=g\circ f$, so that $g(Y)=h(X)$ and $g(f(X'))=h(X')$. Let $A:=\{x\colon h(x)\ne x)$. Then the condition $P(g(Y)\ne X)\le\de$ can be written as $$\int_A p_X\le\de.$$

So, $$P(g(f(X'))\ne X')=P(h(X')\ne X')=\int_A p_{X'} \\ =\int_A p_X+\int_A (p_{X'}-p_X) \le\int_A p_X+\|p_X-p_{X'}\|_1\le\de+\ep.$$

Here we used the inequalities $\int_A (p_{X'}-p_X)\le\int_A |p_{X'}-p_X|\le\|p_X-p_{X'}\|_1$.

Working slightly harder and letting $u_+:=\max(0,u)$, we can write $$\int_A (p_{X'}-p_X)\le\int_A (p_{X'}-p_X)_+ \le\int (p_{X'}-p_X)_+=\frac12\,\int|p_X-p_{X'}| \\ =\frac12\,\|p_X-p_{X'}\|_1.$$ (The penultimate inequality above follows because $|p_X-p_{X'}|=(p_{X'}-p_X)_+ + (p_X-p_{X'})_+$, $p_X-p_{X'}=(p_X-p_{X'})_+ - (p_{X'}-p_X)_+$, and $\int(p_X-p_{X'})=0$, so that $\int(p_X-p_{X'})_+=\int(p_{X'}-p_X)_+=\frac12\,\int|p_X-p_{X'}|$.) So, we get $$P(g(f(X'))\ne X')\le\de+\ep/2.$$


While your question already has an answer, I'm including the following purely as you have tagged this question "information theory", and from an information-theoretic perspective the answer to your question is "this immediately follows from DPI (data processing inequality)". Details follow.

For distributions on $\Omega$, define $F: \Omega\to\{0,1\}$ by $$F(x) = \begin{cases} 1 & (g\circ f)(x) \neq x\\ 0 & \text{else} \end{cases}.$$

Write $\Delta(X, Y) = \frac{1}{2}\lVert X - Y\rVert_1$ for the total variation distance. Then by the Data-Processing Inequality

$$\Delta(F(X), F(X')) \leq \Delta(X, X') = \frac{\lVert X-X'\rVert_1}{2}.$$

Note that each of $F(X), F(X')$ are Bernoulli random of parameter $p, p'$, where $p, p'$ are the probabilities you want to bound. It is straightforward to compute that

$$\Delta(F(X), F(X')) = \left|p-p'\right|.$$

It then follows that $|p-p'| \leq \frac{\lVert X-X'\rVert_1}{2}$, and therefore

\begin{align*} \max(p,p') - \min(p,p') &= |p-p'| \\ &\leq \frac{\lVert X-X'\rVert_1}{2}\\ \implies p' \leq \max(p,p') &\leq \frac{\epsilon}{2}+\delta. \end{align*}

Note that this immediately implies that you get something similar whenever you have a bound on $D_f(X||X')$, where $D_f(\cdot||\cdot)$ is an $f$-divergence, though instead of the expression $\Delta(F(X), F(X')) = |p-p'|$ you will get the expression $p'f\left(\frac{p}{p'}\right)+(1-p') f\left(\frac{1-p}{1-p'}\right)$. This reduces to the claimed expression when $f(x) = |x-1|$ (as for this $f$ $\Delta(X,Y) = D_f(X||Y)$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.