Skip to main content
3 of 3
added 595 characters in body
Iosif Pinelis
  • 128k
  • 8
  • 107
  • 229

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

Iosif Pinelis
  • 128k
  • 8
  • 107
  • 229