# Find $\inf_{P_{X_1,X_2}}P_{X_1,X_2}(\|X_1-X_2\| > 2\alpha)$ , where $\alpha > 0$ and inf is over couplings

Let $$\mathcal X$$ be a seperable Banach space with norm $$\|\cdot\|$$, and let $$X_1$$ and $$X_2$$ be random vectors on $$\mathcal X$$ with finite means.

Question. Given $$\alpha > 0$$, what is value of, or an alternative expression for $$h(\alpha):=\inf_{P_{X_1,X_2}}P_{X_1,X_2}(\|X_1-X_2\| > 2\alpha),$$ where the infimum is taken over all joint distributions $$P_{X_1,X_2}$$ of $$X_1$$ and $$X_2$$ ?

Motivation. It's well-known that $$\text{TV}(X_1,X_2) = \inf_{P_{X_1,X_2}}P_{X_1,X_2}(X_1 \ne X_2)$$. Thus, $$h(0)=\text{TV}(X_1,X_2)$$ in particular.

Conjecture. $$h(\alpha) =\inf_{\|z\| \le \alpha}\text{TV}(X_1-z,X_2+z)$$.

# Edit: Proof of weaker form of conjecture: an upper bound

In the comments to this question and answers, many users have pointed out counter-examples to my Conjecture. Here, I'll settle to proof a weaker version: an inequality. For simplicity of notation, let $$P_k$$ be the distribution of $$X_k$$. Viz,

Theorem. $$h(\alpha) \le \inf_{\|z\| \le \alpha}TV(P_1-z,P_2+z)$$.

User Iosif has established that

$$h(\alpha) = \sup\{P_1(U)-P_2(U^{2\alpha})\mid U \subseteq \mathcal X\text{ open}\},$$

where $$U^{\delta} = \{x_1 \in \mathcal X \mid d(x_1,U) \le \delta\}$$ is the $$\delta$$-neighborhood of $$U$$, and $$d(x_1,U) := \inf_{x_2 \in U}\|x_1-x_2\|$$ is the distance of $$x_1$$ from the set $$U$$. I'll use this to proof the above theorem (the TV upper bound).

Now, for every $$z \in \mathcal X$$, we may translate all the open sets $$U$$ in the above formula without changing it. Indeed the invariance $$\{U-z \mid U \subseteq \mathcal X\text{ open}\} = \{U \mid U \subseteq X\text{ open}\}$$ is trivial to show. Thus, $$h(\alpha) = \sup\{P_1(U-z)-P_2((U-z)^{2\alpha})\mid U \subseteq \mathcal X\text{ open}\}.$$ On the other hand, it is clear that $$U+z \subseteq (U-z)^{2\alpha}$$ whenever $$\|z\| \le \alpha$$. Indeed, $$x=u + z \in U + z \implies d(x,U-z) = d(u, U-2z) \le d(u,u-2z) = 2\|z\| \le 2\alpha.$$ Thus $$P_1(U-z)-P_2((U-z)^{2\alpha}) \le P_1(U-z)-P_2(U+z)$$ $$\forall$$ open $$U \subseteq \mathcal X$$ and $$\|z\| \le \alpha$$.

$$\therefore h(\alpha) \le \inf_{\|z\| \le \alpha}\sup\{P_1(U-z)-P_2(U+z)\mid U \subseteq \mathcal X\text{ open}\} = \inf_{\|z\| \le \alpha}TV(P_1-z,P_2+z).$$ This completes the proof of the theorem.

Let $$\mathcal X$$ be a separable Banach space. Let $$\mu$$ and $$\nu$$ be the distributions of $$X_1$$ and $$X_2$$, respectively. Then, by Theorem 11 (pp. 436-437) of Strassen (used with $$\omega=\{(x_1,x_2)\in\mathcal X\times\mathcal X\colon\|x_1-x_2\|\le2\alpha\}$$), $$h(\alpha)=\sup\{\nu(U)-\mu(U^{2\alpha})\colon U\subseteq\mathcal X, U\text{ is open}\},$$ where $$U^\delta$$ is the $$\delta$$-neighborhood of $$U$$.

In particular, it follows that indeed $$h(0)=TV(\mu,\nu)$$.

• Thanks for the answer (upvoted). This Strassen is formula only synthetic and appears dreadful to "compute" with :). I was hoping for something more analytic. Concerning my small conjecture (which would be a bit more analytic), any thoughts ? Or maybe a modifed identity of tha ilk holds ? Thanks in advance. – dohmatob Jul 31 '19 at 17:19
• I think this expression for $h(\alpha)$ is about as "dreadful" as the definition $TV(\mu,\nu):=\sup\{\nu(U)-\mu(U)\colon U\subseteq\mathcal X, U\text{ is Borel}\}$ of the TV distance. As for you conjecture, I don't think it can be true; you can try checking the case of two real-valued normal (or uniform) random variables. – Iosif Pinelis Jul 31 '19 at 17:41
• The difference is that TV has other equivalent forms (e.g $TV = L_1/2$, etc.) which might more useful (at times) for doing certain "computations". I was wondering whether your expression for $h(\alpha)$ has any interesting alternative expressions ? Concerning the conjecture, maybe it's an inequality rather equality. I'll check. – dohmatob Jul 31 '19 at 17:47
• Using your formula, I've proven a weaker version of my conjecture; see edit to my question. – dohmatob Aug 1 '19 at 9:17
• @dohmatob : I am glad you found this answer to be of use. – Iosif Pinelis Aug 1 '19 at 17:11

As Iosif wrote, the conjecture does not hold. Suppose $$\alpha=1$$ and $$X_1$$ takes the values 0,1,2 with equal probability and $$X_2$$ takes the values 0,2 with equal probability. Then $$h(1)=0$$ but translates of these variables have TV distance at least $$1/3$$.

• Yes, sure. Shouldn't this post be a comment ? Taking $2\alpha=1$, $P_1 = \delta_0$, and $P_2 = (1/2)\delta_{-1} + (1/2)\delta_1$ also gives another counter example... – dohmatob Aug 1 '19 at 7:19
• Thanks for the input. This should have really been a comment. I've upvoted it anyways. Also, I've proven a weaker version of my conjecture, see below. – dohmatob Aug 1 '19 at 9:17
• @dohmatob: "The result you conjectured is false" seems like a perfectly sound answer to me. – Mateusz Kwaśnicki Aug 1 '19 at 15:00
• Well, such an answer is not a very significant as this (falsity) had been noticed in the comments to Iosif's answer already. Writing this up would fit the bill for a comment, but no an "answer" I guess... – dohmatob Aug 1 '19 at 16:53
• I think this is a useful answer: Whereas I just said "I don't think it can be true" about the conjecture, Yuval disproved it. – Iosif Pinelis Aug 1 '19 at 17:09