Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

On a complete graph $K_n$, every edge is assigned a random real weight in $[0, 1]$. I am trying to calculate the probability that the weights satisfy the triangle inequality or even bounds on this probability. How about the discrete version where the weights are integers in $[0, k]$?

EDIT: the question was asked and answered here.

share|cite|improve this question
For $n=3$ the probability is $\frac12$. Empirically, for $n=4$ the probability seems to be between $0.141$ and $0.142$ so I doubt there is an easy expression for large $n$. – Henry Jun 14 '12 at 23:15
@Henry I arrived at the same results. I have been trying to even find the rate at which the probability approaches zero, but I am failing at that too.. – aelguindy Jun 15 '12 at 0:15
Also posted on Mathoverflow now, here:… – aelguindy Jun 17 '12 at 0:48

Your Answer


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

Browse other questions tagged or ask your own question.