# Probability that a random distance function is metric

Take a random $n \times n$ nonnegative symmetric matrix $D$ with zero diagonal. What is the probability that it is an abstract distance matrix, i.e. satisfies $D_{xy}+D_{yz} \geq D_{xz}$ for all index triples $x,y,z$?

In other words: what is the probability that a nonnegative function on $V \times V$, where $V$ is some finite set, defines a finite metric space?

-
I added "pr." to probability, to use an existing tag rather than to create a new one, and added the random-matrices as it seems to fit. Other question, is it clear how you 'pick' such a matrix at random or are you interested in results for any way of doing this. – user9072 Mar 4 '13 at 15:05
Do you want to impose $D_{xx}=0$ for each $x$, and that $D_{xy}=D_{yx}$? – Anthony Quas Mar 4 '13 at 16:22
@quid: Any way is interesting. Thanks for the edit! – Felix Goldberg Mar 5 '13 at 11:27
@AnthonyQuas: Yes, thanks. – Felix Goldberg Mar 5 '13 at 11:27

Since you haven't given a distribution, let me make an observation giving the right form of the answer in the case where the $D_{xy}$ are independent uniform $[0,1]$ random variables.
I want to claim that the probability, $p$, that the matrix defines a metric satisfies $\alpha^{n^2}\le p\le \beta^{n^2}$ for constants $\alpha$ and $\beta$.
First, notice that if all the $\binom n2$ edge lengths are in $[\frac12,1]$, then the triangle inequality is satisfied, so that $p\ge 2^{-\binom n2}$.
Conversely, consider the triples $(b,b+a,b+2a)$ where $a$ is an odd number in the range $1$ to $\frac n4$ and $1\le b\le a$. Notice that no two of these triples contain two elements in common. There are $\Theta(n^2)$ such triples. For such a triple, consider the event $E_{a,b}$ that $D_{b,b+2a}\le D_{b,b+a}+D_{b+a,b+2a}$. These events all have the same probability that is strictly less than 1. They are also independent, since no edge occurs in two events. Hence we obtain the upper bound.
The lower bound argument works also if all distances are in $[\frac13,\frac23]$, or more generally in $[a,2a]$; perhaps one can find a better bound this way? – Joel David Hamkins Mar 5 '13 at 11:56
For other distributions, the logarithm of the probability is either $0$ or $\Theta(n^2)$ by essentially the same argument. – Douglas Zare Mar 5 '13 at 12:56