Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
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. –  quid Mar 4 '13 at 15:05
3  
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
    
add comment

1 Answer

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.

share|improve this answer
    
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
    
@Douglas: Just saw your answer (almost identical to the above) to a previous incarnation of this question (on which I commented). –  Anthony Quas Mar 5 '13 at 13:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.