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}



Effect of small change in probability distribution on error probability
$\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.$$


