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

  • $\begingroup$ 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. $\endgroup$ – dohmatob Jul 31 '19 at 17:19
  • $\begingroup$ 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. $\endgroup$ – Iosif Pinelis Jul 31 '19 at 17:41
  • $\begingroup$ 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. $\endgroup$ – dohmatob Jul 31 '19 at 17:47
  • $\begingroup$ Using your formula, I've proven a weaker version of my conjecture; see edit to my question. $\endgroup$ – dohmatob Aug 1 '19 at 9:17
  • $\begingroup$ @dohmatob : I am glad you found this answer to be of use. $\endgroup$ – 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$.

  • $\begingroup$ 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... $\endgroup$ – dohmatob Aug 1 '19 at 7:19
  • $\begingroup$ 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. $\endgroup$ – dohmatob Aug 1 '19 at 9:17
  • $\begingroup$ @dohmatob: "The result you conjectured is false" seems like a perfectly sound answer to me. $\endgroup$ – Mateusz Kwaśnicki Aug 1 '19 at 15:00
  • $\begingroup$ 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... $\endgroup$ – dohmatob Aug 1 '19 at 16:53
  • $\begingroup$ 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. $\endgroup$ – Iosif Pinelis Aug 1 '19 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.