Bounding the probability Jaccard distance with total variation distance

Question

Let $\Delta_n$ be the set of all probability vectors on $n$ points, also known as the $n$-simplex. Let $x, y \in \Delta_n$ be two probability vectors, that is, $\sum_{i=1}^n x_i = 1$ and $x_i \geq 0$, and similarly for y.

Define the well-known total variation distance between $x$ and $y$ to be $TV(x, y) = \frac{1}{2} \sum_i |x_i - y_i|$.

The equally well-known Jaccard similarity between two sets $A, B$ is defined by $\frac{|A \cap B|}{|A \cup B|}$. When $|A| = |B|$, this can be viewed as similarity between two probability vectors $x$ and $y$, given by $x_i = \frac{1}{|A|} 1_{i \in A}$ and $y_i = \frac{1}{|B|} 1_{i \in B}$.

The most natural generalization of Jaccard similarity to all pairs of probability vectors is given in this paper by

$$J_P(x, y) = \sum_{i: x_i y_i > 0} \left( \sum_j \max\{\frac{x_j}{x_i}, \frac{y_j}{y_i}\} \right)^{-1}. $$

While total variation distance has an alternative definition in terms of pairwise coupling,

$$TV(x, y) = \inf_{X \sim x, Y \sim y} \mathbb{P}[X \neq Y],$$ $J_P$ can also be defined in terms of a particular coupling scheme, that works for all probability vectors at once (i.e., not just a specific pair of them):

$$ J_P(x, y) = \mathbb{P}[\arg\min_i \frac{- \log h_i}{x_i} = \arg\min_i \frac{- \log h_i}{y_i}],$$

where $h_i \sim \mathbb{U}([0, 1])$ are i.i.d. uniform random variables in $[0, 1]$, that are shared among all probability vectors in $\Delta_n$. In other words, $J_P$ can be viewed as the collision probability between two Gumbel softmax random variables. Note that $\mathbb{P}[\arg\min_i \frac{- \log h_i}{x_i} = j] = x_j$ so indeed the above is a coupling collision probability.

Let's define $JD(x, y) = 1 - J_P(x, y)$. By the coupling definition of $TV$, we trivially have $JD(x, y) \geq TV(x, y)$.

On the other hand, for $x_i = 1_{i \in A}$ and $y_i = 1_{i \in B}$ with $|A| = |B| = k$ and $|A \cup B| = n$, we have $TV(x, y) = \frac{n-k}{k}$ and $ JD(x, y) = 1 - \frac{|A \cap B|}{|A \cup B|} = \frac{2n - 2k}{n}$, so

$$JD(x, y) = \frac{2 TV(x, y)}{ 1 + TV(x, y)}.$$

My simulation shows that this is indeed an upper bound of $JD$ in terms of $TV$. In other words, the following elegant relation is conjectured: $$ TV(x, y) \leq JD(x, y) \leq \frac{2 TV(x, y)}{ 1 + TV(x, y)}. $$ But I don't know how to prove it. Help is greatly appreciated.

Answer 1

As suggested by my coauthor, and proved in the same paper linked in the question, the conjectured upper bound is indeed true. I reproduce the proof here for completeness:

Let $p = TV(x, y)$. We want to show $J_P(x, y) \geq \frac{1-p}{1 +p}$, since $1 - \frac{2p}{1 + p} = \frac{1-p}{1 +p}$.

Observe first that $p = 1 - \sum_i \min\{x_i, y_i\}$. Indeed, write $1 = \frac{1}{2} \sum_i (x_i + y_i)$ (since $x$, $y$ are both probability vectors), the claim follows from $x_i + y_i - 2\min\{x_i, y_i\} = |y_i - x_i|$.

Next we have $1 + p = \sum_i \max\{x_i, y_i\}$ since $\min\{x_i, y_i\} + |x_i - y_i| = \max\{x_i, y_i\}$. Thus $ \frac{1 - p}{1 + p} = \sum_i \min\{x_i, y_i\} / \sum_i \max \{x_i, y_i\}$. This already looks very similar to the definition of $J_P(x, y)$.

Finally we have $$ \frac{1-p}{1+p} = \sum_{i: x_i y_i > 0} \left( \sum_j \frac{\max\{x_j, y_j\} }{\min\{x_i, y_i\}}\right)^{-1} \le \sum_{i: x_i y_i > 0} \left( \sum_j \max\{\frac{x_j}{x_i}, \frac{y_j}{y_i}\}\right)^{-1}.$$

Note that $\frac{1-p}{1+p}$ is known as weighted Jaccard similarity, $J_W$. $1-J_W$ is precisely the Steinhaus transform (see Suvrit’s comment) of the total variation distance $TV$ extended to all non-negative probability vectors, with respect to the $\vec{0}$ vector, defined by $TV(x, y) = \frac12 \sum_i |x_i - y_i|$.