# Effect of small change in probability distribution on error probability

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}

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