Skip to main content
MathOverflow

Return to Answer

deleted 1 character in body
Source Link
John Jiang
John Jiang
  • 4.5k
  • 25
  • 47

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\} + 2 |x_i - y_i| = \max\{x_i, y_i\}$$\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|$.

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\} + 2 |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|$.

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

added 28 characters in body
Source Link
John Jiang
John Jiang
  • 4.5k
  • 25
  • 47

As suggested by Suvritmy 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\} + 2 |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|$.

As suggested by Suvrit, 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\} + 2 |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 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|$.

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\} + 2 |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|$.

Source Link
John Jiang
John Jiang
  • 4.5k
  • 25
  • 47

As suggested by Suvrit, 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\} + 2 |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 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|$.