On the probability that finite spaces with random distances are metric spaces (Q2570110): Difference between revisions
From MaRDI portal
Latest revision as of 17:58, 10 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the probability that finite spaces with random distances are metric spaces |
scientific article |
Statements
On the probability that finite spaces with random distances are metric spaces (English)
0 references
26 October 2005
0 references
The purpose of this paper is to start an investigation of the problem: what is the probability that a randomly chosen function on the set of all pairs of elements of a finite set is a metric? The author starts by computing this probability in the case when the set contains \(3\) and \(4\) points and `distances' are chosen independently and uniformly from the set \(\{1,2,\dots, n\}\). The corresponding results for random real distances uniformly distributed over \([0,1]\) follow easily. The complexity of computation for \(4\) points shows that exact computation for \(n\geq 5\) could be extremely difficult. The last result of the paper provides an estimate of the probability for the case of an \(M\)-point set with `distances' distributed independently and uniformly over \([0,1]\).
0 references
finite metric space
0 references
triangle inequality
0 references
random distance
0 references