What makes a distance?

Question

In the answers to my previous question, I learned that there are different concepts of distance, that is of distance-like functions with the usual metric being only the most popular and important one.

All distance-like functions seem to agree in being

• nonnegative: $d(x,y) \geq 0$
• symmetric: $d(x,y) = d(y,x)$
• reflexive: $d(x,x)=0$

– let me call such functions proto-metrics – but differ in other respects:

• a pseudo-metric fulfills the usual triangle inequality, but allows $d(x,y)=0$ for $x \neq y$.

• an ultra-metric has $d(x,y)=0$ only for $x = y$, but fulfills a stronger triangle inequality, namely $d(x,z) \leq \text{max}(d(x,y),d(y,z))$

• a dissimilarity function – conceived as some kind of distance, e.g. in a property space – is just any proto-metric, i.e. fulfills nothing but the core conditions above, esp. no triangle inequality at all.

One might ask whether such a dissimilarity function deserves its name, because it violates a strong intuition on dissimilarity (resp. distance) by allowing – without any restriction – two objects which are very similar (= close) to a third object to be arbitrarily dissimilar (= far away) from each other.

Given that a distance-like function has to fulfill some kind of triangle inequality, my question boils down to:

Which conditions does a function $F$ have to fulfill such that

$$d(x,z) \leq F(d(x,y),d(y,z))\qquad(*)$$

can be seen as a reasonable triangle inequality, thus making the proto-metric $d$ distance-like?

Some conditions on $F$ seem to spring to mind:

• symmetry: $F(x,y)=F(y,x)$
• monotonicity: $F(x,y) \leq F(x',y)$ for $x\leq x'$
• scale-invariance: $\alpha F(x,y) \leq F(\alpha x, \alpha y)$ for $\alpha > 0$
• associativity: $F(x,F(y,z)) = F(F(x,y),z)$ (Did I understand this correctly, Will Sawin? Where does this intution come from?)
• $F(x,0)=x$ (Thanks to David Feldman)

Is there hope to fix a set of conditions $\mathcal{C}$, such that one will be willing to accept any proto-metric $d$ to be distance-like if it fulfills $(*)$ for an $F$ that fulfills $\mathcal{C}$?

Answer 1

A longish comment follows below.

Sometimes we are more interested in measuring "directed distances" or "dissimilarity" functions. A notable example of such functions is the Bregman divergence.

$\newcommand{\rr}{\mathbb{R}}$ Definition Let $\varphi : S \subseteq \rr^n \to \rr$ be a strictly convex function over a convex set $S$. The Bregman divergence $D_\varphi : S \times S \mapsto \rr_+$ is defined by: $$D_\varphi(x,y) := \varphi(x)-\varphi(y) - \langle\nabla \varphi(x), x-y\rangle.$$ From strict convexity of $\varphi$ it follows that:

1. $D_\varphi(x,y) \ge 0$ with equality iff $x=y$.
2. $D_\varphi(x,y)$ is a strictly convex function of $x$

Notice that $D_\varphi$ is almost always asymmetric, but it is still a very useful "distance-like" function that is heavily used in optimization, information-theory, statistics. Specific examples include:

1. $\varphi(x)=x^Tx$ yields the squared Euclidean distance
2. $\varphi(x)=\sum_i x_i\log x_i$ yields the famous Kullback-Leibler Divergence
3. $\varphi(x)=-\sum_i \log x_i$ yields the so-called Burg-divergence

In optimization, it turns out that the convergence analysis of a certain convex optimization algorithm (Bregman's method) becomes simpler when judging convergence using $D_\varphi$, instead of Euclidean distance.

In statistics, there is a very nice bijection between (modulo minor technicalities) between Bregman divergences and the exponential family (e.g., Gaussians correspond to the squared Euclidean divergence, etc.)

My point about mentioning this example is that some of "evident" requirements on a distance that are laid out in the question, are not necessarily the only "right thing", both mathematically as well as philosophically.

Answer 2

Thinking about – and inspired by – an insightful example by Aaron Meyerowitz I found a convincing argument that there is probably no generally agreed upon concept of distance-likeness involving a sensibly generalized triangle inequality. The argument goes like this:

Consider a world of non-intersecting disks in the plane. Let the distance $d$ between two disks be the smallest Euclidean distance between any two points on their respective boundaries. This involves that any two touching disks have distance 0 and that the distance-law d(x,y)=0 iff x=y is violated. I assume that it is nevertheless generally agreed upon that this is a sensible distance.

But any sensible triangle inequality is violated, too. That's because for every two non-touching disks $x,z$ that touch a common disk $y$ we have

$$d(x,z) > d(x,y) + d(y,z) = 0$$

and $d(x,z)$ can be arbitrarily large (depending on the radius of disk $y$) and thus greater than $F(0,0)$ for any function $F(u,v)$.

The question arises for what specific reasons we nevertheless do believe that $d$ is a sensible distance?

Note, that for a given maximal disk radius $r$_max we may get a sensible version of the triangle inequality (due to Aaron's example) and with $r$_max $\rightarrow 0$ we get the usual triangle inequality.

Answer 3

What is the motivation for fixing boundaries on what is and is not a "distance". Sometimes one runs into multiple situations where the same type of theorems and proofs apply and then abstracts the pertinent properties which allow a theory. What to you actually want to do?

The article to which you link gives a particular meaning to dissimilarity which might be something like distance but not all the way to a distance. If it was exactly the same, why use a new word? I can imagine having distance $d(x,y)=0$ means close enough that it counts as the same. One can imagine situations where $d(x_i,x_{i+1})=0$ for $1 \le i \le n$ but $d(x_1,x_n) \gt 0.$ In that case, if in addition all distances are integral, we might have $d(x,z) \le d(x,y)+d(y,z)+1.$

Incidentally, sometimes a distance could fail to be symmetric, say in a directed graph.

I like thinking about the question but philosophically, what is the criterion for when we stop using distance? The universe can make a difference too. Suppose that we are on the unit sphere with ordinary points and we use the ordinary $\mathbb{R}^3$ Euclidean difference (We live on the surface but can run wires through the interior.) This seems like a pretty fair Space/distance pair. By my calculations $F(u,v)=u\sqrt{1-(\frac{v}{2})^2}+v\sqrt{1-(\frac{u}{2})^2}.$ For small $u,v$ this is just a bit less than $u+v$. It is associative but not scale invariant. Also, one could say $F(u,v)=\min(1,u\sqrt{1-(\frac{v}{2})^2}+v\sqrt{1-(\frac{u}{2})^2}).$ Then it is not associative.

As a perspective, what properties are required for a multiplication? Usually (but see below) a binary operation and it should help (some group of people who communicate with each other) to think of it as a multiplication. But when it doubt we say " a commutative and associative multiplication with cancelation" and spell out what can be assumed. Matrix multiplication is not always commutative. The cross product in $\mathbb{R}^3$ is not associative but it does distribute over vector addition. Multiplication of octonians is not associative but it is when restricted to the sub-algebra generated by any two elements and it extends the multiplication. There is the concept of a non-associative Algebra. so maybe that there is an addition to distribute over? Of course given a set with a multiplication operator we can define a formal addition which the multiplication should distribute over.

The distributive law says that the multiplication (in whatever context) is linear in each variable (with respect to the addtion). There is multilinear algebra with operators linear in each variable. The determinant is a multiplication of $n$ vectors in $\mathbb{R}^n.$ Given $n-1$ vectors $v_1,v_2,\cdots,v_{n-1}$ in $\mathbb{R}^n$ there is a unique $w \in \mathbb{R}^n$ so that for any $v_n$ the dot product $w \cdot v_n$ is the signed volume (determinant) determined by $v_1,\cdots,v_n.$ So here we have that $(v_1,\cdots,v_{n-1}) \mapsto w$ is a "generalized cross-product."