12
$\begingroup$

I'm wondering where the relative probabilistic distance or Jaccard distance was first studied: $$d(A,B) =\mathbb P(\overline A\cup\overline B\mid A\cup B)$$ where $\overline A$ is the complement of $A$.

A web search turned up this:

@TechReport{Yianilos91,
  author =   "Peter N. Yianilos",
  title =    "Normalized Forms for Two Common Metrics",
  institution =  "NEC Research Institute",
  year =     {1991,2002}
}

which contains a detailed proof that $d $ obeys the triangle inequality, but surely that was discovered prior to 1991?

On a seemingly related note, Cathy O'Neil mentions at 5:00 in Deciphering recommendation engines, http://youtu.be/lzavwJy1SgQ that $$\mathbb P(A\mid A\cup B)$$ is a mathematically interesting notion of closeness.

Improve this question
$\endgroup$
4
  • $\begingroup$ I am puzzling by the terminology distance. If $B=A$, don't we have $d(A,B)={\mathbb P}(\bar A|A)=0$ ? $\endgroup$
    – Denis Serre
    Commented Jan 6, 2015 at 7:39
  • 3
    $\begingroup$ @DenisSerre Yes, that's right $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jan 6, 2015 at 7:46
  • 1
    $\begingroup$ It is also Exercise 8.4.1(b) in Li and Vitanyi's book Kolmogorov complexity and its applications, 3rd edition. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jan 11, 2015 at 2:06
  • $\begingroup$ Is it known when / how it got that name? $\endgroup$
    – Francois Ziegler
    Commented Nov 21, 2018 at 10:36

1 Answer 1

Reset to default
5
$\begingroup$

If I remember correctly, it was by Menger, in this series of papers.

Menger, 1942(12), statistical metrics, PNAS 28(12):535-537.

Menger, 1951(3), probabilistic theory of relations, PNAS 37(3):178-180.

Menger, 1951(4), probabilistic geometry, PNAS 37(4):226-229.

Menger et al, 1959(au), probabilistic metrics and numerical metrics with probability, czechoslovakian mathematical journal 9(3):459-466.

If each pair of coordinates points is supposed to nowhere exist strictly a distance $x$ apart, for all possible $x$, and they only have a probability $z$ of being separated by such a distance (or by a lesser distance), then special cases exist, one per distinguishable $x$:---probabilities for one and only one $x$ are defined in each case and undefined for other distances. There the $z$ corresponding to each pair of points is itself FAPP a distance between any two such points. From each such metric, at most one further constraint is required for a metric of the sort in the question title to result.

[The formal part of this answer, I agree it needs rewriting, temporarily gone. Also, I'm checking another possible source, slightly more recent, where the desired metric is explicitly stated unless my memory is wrong.]

Improve this answer
$\endgroup$
4
  • $\begingroup$ It's not quite the same thing but closely related in the way above, worth citing. I also am looking for the metric you mentioned in Eddington's Fundamental Theory, because I remember seeing it there explicitly (but I could be wrong):---if it's there, I'll update my answer again with the chapter. $\endgroup$
    – Gottfried William
    Commented Jan 6, 2015 at 13:21
  • $\begingroup$ I've summarized the basic idea. BTW, I agree, the (1) (2) (3) edit needed rewriting (and correction, as one of the conditions to reduce to the special case was unnecessary, I now think). $\endgroup$
    – Gottfried William
    Commented Jan 7, 2015 at 2:33
  • $\begingroup$ OK thanks, looking forward to any further details $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jan 7, 2015 at 2:35
  • $\begingroup$ Only got around to it today, still checking. Two publications to check, one from 1969, one from 1946. $\endgroup$
    – Gottfried William
    Commented Jan 11, 2015 at 16:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .