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

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.

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 \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 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}] = x_i$ 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.

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