Integrating a simple exponential over the space of matrices that define a metric

Question

I want to interpret an $n\times n$ matrix $D$ as a set of pairwise distances, and assume that $D$ obeys metric properties. Namely, $D_{ii} = 0$, $D_{ij} \geq 0$, $D_{ij} = D_{ji}$ and $D_{ij} \leq D_{ik} + D_{kj}$ for all $1 \leq i,j,k \leq n$. For convenience, let $\bigtriangleup_n$ denote the set of such matrices.

Now, I need to integrate some "simple" functions over this set. The simplest would be an exponential. Namely, I want to compute something like $\int_{\bigtriangleup_n} \exp\left[-\lambda \sum_{i=1}^n \sum_{j=i+1}^n D_{ij}\right] d D$.

I've been able to work this out for the simplest nontrivial case: namely $n=3$. But for higher $n$, my brute force way of calculation gets really ugly. The approach I've been taking is to basically first integrate over $D_{11}, D_{12}, D_{13}, ..., D_{1n}$, all of which have no constraints... then integrate over $D_{23}$ which is just a definite integral from $|D_{12} - D_{23}|$ to $D_{12}+D_{23}$ of $\exp[-\lambda D_{13}]$ and then, in the general case, integrating over $D_ij$ becomes the definite integral from $\max_{k \neq i,j} |D_{ik}-D_{jk}|$ to $\min_{k\neq i,j} D_{ik}+D_{jk}$, but this is the point at which I get stuck, because these things becomes nasty quite quickly (even for just $n=4$).

At the end of the day, I've love to be able to integrate more complex functions, like a chi-square type function rather than an exponential type function, but the exponential is the most trivial case that is interesting...

To be precise, I'm looking for a closed form evaluation of the integral above, preferably with some derivation that will help me work out more complex examples.

Answer 1

The space of variables $D_{ij}$ satisfying the constraints of a metric form a polytope (or really a cone, since any scalar multiple satisfies it as well). In general, integrating functions over such objects can be (computationally) hard. Here's an article that talks about this in more detail (for the specific case of integrating polynomials over a simplex).

Caveats:

• you're integrating over a cone, not a polytope: maybe that makes things easier (although I doubt it)
• you're integrating a very specific kind of function and maybe some specific tricks work for that case.
• if you're willing to get an approximate answer, I'd suspect that something might be possible

Answer 2

A keyword that comes to mind is "first-passage percolation on the complete graph of n vertices," though I don't know that anybody's studied this. FPP is the assignment of random lengths (or "passage times") to a graph. Typically, this is over the lattice $\mathbb Z^d$, rather than arbitrary graphs. A major tool is the subadditive ergodic theorem, which relies on the fact that you can translate along the lattice; in the case of the complete graph, you would have no such tool.