# Alternative olution to generalized version of second part

For simplicity of notation, let $\varepsilon := \alpha/2$. I'll only consider the second part of the problem, but generalized so that the base space is a Banach space $\mathcal X$ with norm $\|.\|$ (in the statement of my problem, I considered $\mathcal X = \mathbb R$, equiped with the absolute-value norm. Also, $\Omega := \{(x',x) \in \mathcal X^2 \mid \|x'-x\| > 2\varepsilon\}$.

**Lemma.** We have the identity
\begin{eqnarray}
c_\Omega(x',x) = \inf_{\|z\| \le \varepsilon}\delta(x'-z,x+z),\;\forall x',x \in
\mathcal X.
\end{eqnarray}

*Proof.*
We show that $\|x'-x\| > 2\varepsilon$ iff $x'-z \ne x + z$ for all $z \in
\mathbb B_\varepsilon(0)$. Indeed, if $x'-z = x + z$ for some $z \in
\mathcal B_\varepsilon(0)$, then $\|x'-x\| = 2\|z\| \le 2\epsilon$.

Conversely, if $\|x'-x\| \le 2\varepsilon$, we may take $z=(x'-x)/2 \in \mathbb
B_\varepsilon(0)$ and note that $x'-x = x + z = (x' + x) / 2$. $\quad\quad\quad\quad\Box$

Given a distribution $P$ on $\mathcal X$ and a point $z \in \mathcal X$, let
$P+z$ be the translation of $P$ by $z$. Alternatively, if $X$ is a random
variable with distribution $P$, then $P+z$ corresponds to the distribution of
the r.v $X + z$.

**Theorem.** We have the inequality
\begin{eqnarray}
c_\Omega(P_1,P_2) \le \inf_{\|z\| \le \varepsilon}\text{TV}(P_1 - z, P_2 + z)
\end{eqnarray}

*Proof.* One computes
$$
\begin{split}
c_\Omega(P_1,P_2) &:= \inf_{\gamma \in \Pi(P_1,P_2)}\int_{\mathcal X^2} c_\Omega(x',x)d\gamma(x',x)
\overset{(a)}{=} \inf_{\gamma \in \Pi(P_1,P_2)}\int_{\mathcal X^2}\inf_{\|z\| \le
\varepsilon}\delta(x'-z,x+z)d\gamma(x',x)\\
&\overset{(b)}{\le}\inf_{\gamma \in \Pi(P_1,P_2)}\inf_{\|z\| \le \varepsilon}\int_{\mathcal
X^2}\delta(x'-z,x+z)d\gamma(x',x)\\
&\overset{(c)}{=}\inf_{\|z\| \le \varepsilon}\inf_{\gamma \in \Pi(P_1,P_2)}\int_{\mathcal
X^2}\delta(x'-z,x+z)d\gamma(x',x)\\
&\overset{(d)}{=}\inf_{\|z\| \le \varepsilon}\inf_{\gamma \in \Pi(P_1-z,P_2+z)}\int_{\mathcal
X^2}\delta(x',x)d\gamma(x',x) \overset{(e)}{=} \inf_{\|z\| \le \varepsilon}\text{TV}(P_1-z,P_2+z),
\end{split}
$$
where

*(a)* is by the above Lemma
*(b)* inequality due to interchange of integral and inf
*(c)* is nothing special
*(d)* is a simple change-of-variable formula
*(e)* is simply the definition of total-variation distance. $\quad\quad\quad\quad\Box$

## Special case of multivariate Gaussians

The following is a direct corollary.

**Corollary.** In $\mathbb R^p$ with $\Omega := \{(x',x) \in \mathbb R^p \mid \|x'-x\| > 2\varepsilon\}$, we have
\begin{eqnarray}
c_\Omega(\mathcal N(\mu_1,\Sigma),\mathcal N(\mu_2,\Sigma)) = 2\Phi(\Delta(\varepsilon))-1,
\end{eqnarray}
where $\Delta(\varepsilon):=\inf_{\|z\| \le \varepsilon}\|z-\mu\|_{\Sigma^{-1}}$, $\mu
:= \mu_1-\mu_2$, and $\|z-\mu\|_{\Sigma^{-1}} := \sqrt{(z-\mu)^T\Sigma^{-1}(z-\mu)}$.

*Proof.* Follows from the above Theorem and the well-known fact that fact that
$$
\text{TV}(\mathcal N(\mu_1,\Sigma),\mathcal N(\mu_2,\Sigma)) =
\Phi(\|\mu\|_{\Sigma^{-1}})-\Phi(-\|\mu\|_{\Sigma^{-1}}) =
2\Phi(\|\mu\|_{\Sigma^{-1}})-1. \quad\quad\Box
$$

## Special case of 1d Gaussians

In one dimension ($p=1$), $\Sigma = \sigma^2$, the common variance, and we have the closed-form formula $\Delta(\varepsilon) = \sigma^{-1}(\mu-\varepsilon)_+$, which is the result obtained by user Mateusz.