Effect of small change in probability distribution on error probability

Question

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}

Answer 1

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

Answer 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)$).