ONE, TWO AND THREE TIMES log n/n FOR PATHS IN A COMPLETE GRAPH WITH RANDOM WEIGHTS

SVANTE JANSON

Abstract. Consider the minimal weights of paths between two points in a complete graph K_{n} with random weights on the edges, the weights being e.g. uniformly distributed. It is shown that, asymptotically, this is log n/n for two given points, that the maximum if one point is fixed and the other varies is 2 log n/n, and that the maximum over all pairs of points is 3 log n/n. Some further related results are given too, including results on asymptotic distributions and moments, and on the number of edges in the minimal weight paths.

1. Introduction

Let a random weight T_{ij} be assigned to every edge ij of the complete graph K_{n}. (Thus T_{ji} = T_{ij}. We do not define T_{ij} for i = j.) We assume that the \binom{n}{2} weights T_{ij}, 1 ≤ i < j ≤ n, are independent and identically distributed; moreover we assume that they are non-negative and that their distribution function ℙ(T_{ij} ≤ t) = t + o(t) as t ↘ 0; the main examples being the uniform U(0, 1) and the exponential Exp(1) distributions.

Let, for two vertices i and j, X_{ij} be the minimal total weight of a path between i and j. Our main theorem is a set of three different asymptotic results for X_{ij}. (log denotes the natural logarithm.)

Theorem 1. Under the assumptions above, as n → ∞:

(i) For any fixed i and j,

\frac{X_{ij}}{log n/n} →^{p} 1.

(ii) For any fixed i,

\frac{max_{j≤n} X_{ij}}{log n/n} →^{p} 2.

(iii)

\frac{max_{i,j≤n} X_{ij}}{log n/n} →^{p} 3.

Hence, with high probability, X_{ij} is about log n/n for any fixed (or random) pair of vertices, but there are pairs of vertices for which it is larger; up to 2 log n/n if i is fixed and up to 3 log n/n globally.

Date: December 10, 1997; revised October 1, 1998.

Similarly, defining Y_{i} = max_{j≤n} X_{ij}, we see from (ii) and (iii) that Y_{i} typically is about 2 log n/n, but that it is larger for a few vertices with max_{i} Y_{i} being about 3 log n/n. A companion result shows that, in contrast, Y_{i} is not significantly smaller than 2 log n/n for any vertex i.

Theorem 2. As n → ∞,

\frac{min_{i≤n} max_{j≤n} X_{ij}}{log n/n} →^{p} 2.

In other words, interpreting the weights as distances, most pairs of vertices are at a distance of about log n/n, the radius of the graph is about 2 log n/n and the diameter is about 3 log n/n.

Remark 1. Theorem 1(i),(ii) may alternatively be stated in terms of firstpassage percolation on the complete graph (the time to reach a given vertex is about log n/n and the time to reach all is 2 log n/n).

For completeness and comparison, we also state the corresponding simple (and well-known) results for the minimal distance from a vertex. In this case there is less concentration and we obtain convergence (in distribution) to a non-degenerate random variable instead of to a constant.

Theorem 3. Let Z_{i} = min_{j≠i} X_{ij} = min_{j≠i} T_{ij}. As n → ∞:

(i) For any fixed i,

nZ_{i} →^{d} Exp(1).

(ii)

n^{2} min_{i≤n} Z_{i} = n^{2} min_{i,j≤n} T_{ij} →^{d} Exp(2).

(iii)

\frac{max_{i≤n} Z_{i}}{log n/n} →^{p} 1.

The proofs of (i) and (ii) are simple exercises, while (iii) is, in disguise, the well-known threshold for existence of isolated vertices in a random graph [1, Exercise III.2]; consider the graph with edges {ij : T_{ij} < t}. We leave the details to the reader. (Note that if T_{ij} ∈ Exp(1), then (n − 1)Y_{i} ∈ Exp(1) and n(n − 1) min_{i} Y_{i} ∈ Exp(2) exactly.)

ONE, TWO AND THREE TIMES log n/n 3

Using Theorem 3(iii), we can give a simple informal explanation of the discrepancy between the three parts of Theorem 1 as follows, interpreting the weights as travel times: Most vertices are connected by efficient highways, which take you to almost any other vertex within about log n/n (but rarely much quicker). Some vertices, however, are remote villages (like Oberwolfach), from which it takes up to log n/n to get to any other vertex at all. Hence, starting at a typical vertex, most travel times are about log n/n, but it takes an extra log n/n (just for the final step in the path) to reach a few remote vertices. Similarly, if we start at one of the very remote vertices, it takes about log n/n to get to any other vertex at all, 2 log n/n to get to most other vertices and 3 log n/n to get to the other very remote vertices.

Some further results on asymptotic distributions and moments are given in Section 3. The lengths of the minimum weight paths are studied in Section 4.

Acknowledgements. Most of this work was done during the meeting Random Graphs and Combinatorial Structures at Oberwolfach, September–October 1997; I thank several participants, in particular Jim Fill and Johan Håstad, for their helpful comments and questions. The proof of the main theorem was completed a few weeks later, while I tried to get my daughter Sofie back to sleep one night; I thank her for giving me this opportunity.

2. Proofs

We first observe that the distribution of T_{ij} does not affect the results, as long as it satisfies the condition above. This is seen by the following standard coupling argument, which we include for completeness.

Let F^{−1} : [0, 1) → [0, ∞) be the inverse function of the distribution function F (t) = ℙ(T_{ij} ≤ t) of T_{ij}. If U_{ij} ∈ U(0, 1) are independent uniform random variables, then F^{−1}(U_{ij}) has the same distribution as T_{ij}, so we may without loss of generality assume that T_{ij} = F^{−1}(U_{ij}). By assumption, F (t)/t → 1 as t ↘ 0, and thus also F^{−1}(t)/t → 1. Let ε > 0. If X_{ij} < 10 log n/n, say, for some i and j, then T_{kl} = F^{−1}(U_{kl}) < 10 log n/n for each edge kl in the minimum weight path from i to j, and thus, provided n is large enough, 1 − ε < T_{kl}/U_{kl} < 1 + ε. Consequently, the sum of the U_{kl} for the same path is at most (1 − ε)^{−1}X_{ij}, and thus, using X′_{ij} to denote the minimal path weight defined by {U_{ij}}, X′_{ij} ≤ (1 − ε)^{−1}X_{ij}. Conversely, by the same argument, if X′_{ij} < 10 log n/n then X_{ij} < (1+ε)X′_{ij}. If follows that if either X_{ij} < 9 log n/n or X′_{ij} < 9 log n/n, and n is large enough, then both X_{ij} < 10 log n/n and X′_{ij} < 10 log n/n hold, and moreover (1 − ε)X′_{ij} < X_{ij} < (1 + ε)X′_{ij}. It now follows immediately that if any part of Theorem 1 or 2 holds either for T_{ij} or for the uniform U_{ij}, then it holds for both. In particular, a proof of these results for any distribution with F (t)/t → 1 as t ↘ 0 implies the same results for U(0, 1), and then for any other such distribution.

We may thus choose a convenient distribution of T_{ij}; we use the exponential distribution because of its excellent Markov properties. Hence, in the sequel we assume that T_{ij} ∈ Exp(1).

Proof of Theorem 1. For parts (i) and (ii), we may assume that i = 1. We adopt the first-passage percolation viewpoint (see Remark 1), so we regard vertex 1 as initially infected, and assume that the infection spreads along each edge with an Exp(1)-distributed waiting time. We first study when the other vertices get infected, considering them in order of infection and ignoring their labels.

Since there are n − 1 neighbours of the initially infected vertex, the time V_{1} until the second vertex is infected is exponentially distributed with expectation 1/(n − 1). More generally, when k < n vertices have been infected, there are k(n − k) edges connecting the infected and non-infected vertices, and thus the time V_{k} until the next vertex is infected is Exp(1/(k(n − k)); moreover, this time is independent of V_{1}, …, V_{k−1}. In other words, the time S_{m} until m vertices have become infected can be written

S_{m} = ∑_{1}^{m−1} V_{k}

where V_{1}, …, V_{n−1} are independent with V_{k} ∈ Exp(1/(k(n − k)).

The times {S_{m}}_{m=2}^{n} are just the minimal path weights {X_{1j}}_{j=2}^{n}, arranged in increasing order. In particular,

Y_{1} = max_{j≥2} X_{1j} = S_{n} = ∑_{1}^{n−1} V_{k}.  (1)

Hence

\begin{aligned}𝔼 Y_{1} & = ∑_{1}^{n−1} 𝔼 V_{k} = ∑_{1}^{n−1} \frac{1}{k(n − k)} = \frac{1}{n} ∑_{1}^{n−1}(\frac{1}{k} + \frac{1}{n − k} ) = \frac{2}{n} ∑_{1}^{n−1} \frac{1}{k} \\ & = 2\frac{log n}{n} + O(\frac{1}{n}) \end{aligned} (2)

and similarly

\begin{aligned}Var Y_{1} & = ∑_{1}^{n−1} Var V_{k} = ∑_{1}^{n−1}(\frac{1}{k(n − k)})^{2} ≤ 2 ∑_{1}^{n/2} \frac{1}{k^{2}(n − k)^{2}} \\ & ≤ \frac{8}{n^{2}} ∑_{1}^{n/2} \frac{1}{k^{2}} = O(n^{−2}). \end{aligned}  (3)

(ii) now follows by Chebyshev’s inequality.

For (i), fix further j = 2. Observe that if N is the number of vertices infected before vertex 2, then

X_{12} = S_{N+1} = ∑_{1}^{N} V_{k},  (4)

where, by symmetry, N is uniformly distributed over 1, …, n − 1 and independent of V_{1}, …, V_{n−1}. We rewrite this equation as X_{12} = ∑_{1}^{n−1} 1[N ≥ k]V_{k}, using indicator functions to eliminate the random summation limit. Hence,

\begin{aligned}𝔼 X_{12} & = ∑_{1}^{n−1} 𝔼(1[N ≥ k]V_{k}) = ∑_{1}^{n−1} ℙ(N ≥ k) 𝔼 V_{k} \\ & = ∑_{1}^{n−1} \frac{n − k}{n − 1} \frac{1}{k(n − k)} = ∑_{1}^{n−1} \frac{1}{k(n − 1)} \\ & = \frac{log n}{n} + O(\frac{1}{n}). \end{aligned}  (5)

In order to estimate the variance, we further rewrite the sum as

X_{12} = ∑_{1}^{N}(V_{k} − 𝔼 V_{k}) + ∑_{1}^{N} \frac{1}{n}(\frac{1}{k} + \frac{1}{n − k} )

= ∑_{1}^{N}(V_{k} − 𝔼 V_{k}) + \frac{1}{n}(log N + log n − log(n − N)) + O(\frac{1}{n}). (6)

We consider the three terms on the right hand side separately. Since N, V_{1}, …, V_{n−1} are independent,

Var(∑_{1}^{N}(V_{k} − 𝔼 V_{k})) = 𝔼(∑_{1}^{N}(V_{k} − 𝔼 V_{k}))^{2} = 𝔼(∑_{1}^{N} Var V_{k})

≤ ∑_{1}^{n−1} Var V_{k} = ∑_{1}^{n−1} \frac{1}{k^{2}(n − k)^{2}}

≤ ∑_{1}^{n/2} \frac{4}{k^{2}n^{2}} + ∑_{n/2}^{n−1} \frac{4}{n^{2}(n − k)^{2}} = O(\frac{1}{n^{2}} ).

For the second term, we observe that

𝔼(log N − log(n − 1))^{2} = 𝔼(log \frac{N}{n − 1})^{2} → ∫_{0}^{1}(log x)^{2} dx < ∞

as n → ∞. Hence Var(log N) = Var(log(n − N)) = O(1), and it follows that the variance of the second term in (6) also is O(n^{−2}). The same is trivially true for the third term.

Consequently, Var X_{12} = O(n^{−2}), which together with (5) yields (i).

The proof of (iii) is divided into two parts, considering upper and lower bounds separately. First, by (1), for −∞ ≤ t < 1 − 1/n,

𝔼 e^{tnY_{1}} = ∏_{1}^{n−1} 𝔼 e^{ntV_{k}} = ∏_{1}^{n−1}(1 − \frac{nt}{k(n − k)})^{−1}.  (7)

Hence, for every a > 0, choosing t = 1 − 1/ log n (n ≥ 3),

ℙ(Y_{1} > a log n/n) ≤ 𝔼 e^{tnY_{1}−ta log n} = e^{−ta log n} ∏_{1}^{n−1}(1 − \frac{nt}{k(n − k)})^{−1}

= (1 − \frac{nt}{n − 1})^{−2} exp(−ta log n + ∑_{2}^{n−2} − log(1 − \frac{nt}{k(n − k)}))

≤ (1 − \frac{nt}{n − 1})^{−2} exp(−ta log n + ∑_{2}^{n−2}(\frac{nt}{k(n − k)} + (\frac{nt}{k(n − k)})^{2}))

= (1 − t + O(n^{−1}))^{−2} exp(−ta log n + 2t log n + O(1)) = O(n^{2−a} log^{2} n).

This evidently implies

ℙ(max_{i} Y_{i} > a log n/n) ≤ n ℙ(Y_{1} > a log n/n) = O(n^{3−a} log^{2} n),

which tends to 0 as n → ∞ for every fixed a > 3.

For the lower bound, let ε > 0 be small. Partition the vertex set {1, …, n} of K_{n} into the sets A = {1, …, n_{A}} and B = {n_{A}+1, …, n}, where n_{A} = ⌈n^{1−ε}⌉. Let n_{B} = |B| = n − n_{A}.

For i ∈ A, let U_{i} = min_{j∈B} T_{ij}. Then the random variables U_{i}, i ∈ A, are independent with U_{i} ∈ Exp(1/n_{B}). In particular,

ℙ(U_{i} > (1 − 2ε) log n/n) = exp(−(1 − 2ε)\frac{n_{B}}{n} log n)
≥ exp(−(1 − 2ε) log n) = n^{2ε−1}

and thus

ℙ(U_{i} ≤ (1 − 2ε) log n/n for every i ∈ A) ≤ (1 − n^{2ε−1})^{n^{1−ε}} < e^{−n^{ε}}. (9)

Let, for k ∈ A, E_{k} be the event that U_{k} > (1 − 2ε) log n/n but U_{i} ≤ (1 − 2ε) log n/n for i ≤ k. Then the events E_{k} are disjoint and, by (9),

∑_{k∈A} ℙ(E_{k}) = ℙ( ⋃_{k∈A} E_{k}) > 1 − e^{−n^{ε}}.  (10)

The idea of the proof is to show that conditioned on E_{k}, Y_{k} is with high probability close to 3 log n/n; in fact, as is shown in detail below, conditioning on U_{k} > (1 − 2ε) log n/n typically increases Y_{k} (which usually is about 2 log n/n) by (1−2ε) log n/n, while conditioning on U_{i} ≤ (1−2ε) log n/n for i ≤ k hardly affects the result.

We will use the following lemma.

Lemma 1. Suppose that μ, b > 0 and X ∈ Exp(μ), and define

f(x) = −μ log(e^{−b/μ} + (1 − e^{b/μ})e^{−x/μ}).

(i) The distribution of f(X) equals the conditional distribution of X given X ≤ b.

(ii) If further 0 ≤ α < 1 and b/μ ≥ α(1 − log α)/(1 − α), then f(x) ≥ αx when 0 ≤ x ≤ α^{−1}b − μ. Consequently,

ℙ(f(X) < αX) ≤ ℙ(X > α^{−1}b − μ) = e^{1−α^{−1}b/μ}.

Proof. We may for simplicity, by homogeneity, assume that μ = 1. Then e^{−X} is uniformly distributed on [0, 1], and thus for 0 ≤ t ≤ b,

\begin{aligned}ℙ(f(X) ≤ t) & = ℙ(e^{−b} + (1 − e^{−b})e^{−X} ≥ e^{−t}) = ℙ(e^{−X} ≥ \frac{e^{−t} − e^{−b}}{1 − e^{−b}} ) \\ & = \frac{1 − e^{−t}}{1 − e^{−b}} = ℙ(X ≤ t | X ≤ b), \end{aligned}

which proves (i).

For (ii) we observe that (when μ = 1) f(x) ≥ αx if and only if

e^{−b} + (1 − e^{−b})e^{−x} ≤ e^{−αx}.  (11)

Letting y = e^{−x}, the left hand side of (11) is a linear function of y, while the right hand side y^{α} is concave; hence, in order to verify (11) for the interval 0 ≤ x ≤ α^{−1}b − 1, it suffices to verify it for the endpoints.

For x = 0, (11) is a trivial identity, while for x = α^{−1}b − 1, it is

e^{−b} + (1 − e^{−b})e^{−α^{−1}b+1} ≤ e^{−b+α}.  (12)

Now, by assumption, α^{−1}b = b + b(1 − α)α^{−1} ≥ b + 1 − log α, and thus

e^{−b} + e^{−α^{−1}b+1} ≤ e^{−b} + e^{−b+log α} = (1 + α)e^{−b} ≤ e^{α}e^{−b};

this implies (12), which completes the proof of the lemma.

Continuing with the proof of Theorem 1(iii), let k ∈ A be fixed, let f be as in Lemma 1 with μ = 1/n_{B} and b = (1 − 2ε) log n/n, and define

U′_{i} = \begin{cases}f(U_{i}), & i < k, \\ U_{i} + b, & i = k, \\ U_{i}, & i > k. \end{cases}

Then, by Lemma 1(i) for i < k and the standard lack-of-memory property of exponential distributions for i = k, the distribution of U′_{i} equals the conditional distribution of U_{i} given E_{k} for every i ∈ A; moreover, by our independence assumptions, this extends to the joint distribution. Furthermore, by the same lack-of-memory property, the family of random variables {T_{ij} − U_{i}}_{j∈B} is independent of U_{i}, for each i ∈ A separately and thus for all i ∈ A jointly too; hence the joint distribution of {T_{ij} − U_{i}}_{i∈A, j∈B} is not affected by conditioning on E_{k}. It follows that if we define T′_{ij} for 1 ≤ i < j ≤ n by

T′_{ij} = \begin{cases}T_{ij} − U_{i} + U′_{i}, & i ∈ A and j ∈ B, \\ T_{ij}, & otherwise, \end{cases}  (13)

and let T′_{ji} = T′_{ij} for j > i, then the family {T′_{ij}} has the same distribution as the conditional distribution of {T_{ij}} given E_{k}. Note in particular that T′_{kj} = T_{kj} + b when j ∈ B.

Suppose that {T_{ij}} are such that

U′_{i} ≥ (1 − 2ε)U_{i} for every i ∈ A,  (14)
T_{ik} ≥ 3\frac{log n}{n} for every i ∈ A  (15)

and

Y_{k} ≥ (2 − ε)\frac{log n}{n}.  (16)

We observe first that, by (13) and (14), then

T′_{ij} ≥ (1 − 2ε)T_{ij} for every i and j ≠ i.  (17)

Now consider the minimal path weights X′_{ij} defined by the edge weights T′_{ij} and the corresponding Y′_{i} = max_{j} X′_{ij}. By (16), there exists a vertex l such that every path i_{0} = k, i_{1}, …, i_{m} = l from k to l has weight W = ∑_{1}^{m} T_{i_{s−1}i_{s}} ≥ (2 − ε) log n/n. Consider such a path and the corresponding weight W′ = ∑_{1}^{m} T′_{i_{s−1}i_{s}}. Either i_{1} ∈ A, and then, by (13) and (15), W′ ≥ T′_{ki_{1}} = T_{ki_{1}} ≥ 3 log n/n, or i_{1} ∈ B, and then T′_{ki_{1}} = T_{ki_{1}} + b, which together with (17) yields

W′ ≥ b + (1 − 2ε)W ≥ (1 − 2ε)\frac{log n}{n} + (1 − 2ε)(2 − ε)\frac{log n}{n} ≥ (3 − 7ε)\frac{log n}{n}.

Hence W′ ≥ (3 − 7ε) log n/n for every path from k to l, and thus X′_{kl} ≥ (3 − 7ε) log n/n and finally Y′_{k} ≥ X′_{kl} ≥ (3 − 7ε) log n/n.

We have shown that if (14)–(16) hold, then Y′_{k} ≥ (3 − 7ε) log n/n. Consequently,

ℙ(Y_{k} ≥ (3 − 7ε) log n/n | E_{k}) = ℙ(Y′_{k} ≥ (3 − 7ε) log n/n)
≥ ℙ((14)–(16) hold).

Let q denote the probability that (14)–(16) hold. We have so far kept k fixed, but q is independent of k, and summing over k we obtain

ℙ(max_{i} Y_{i} ≥ (3 − 7ε) log n/n) ≥ ∑_{k∈A} ℙ(Y_{k} ≥ (3 − 7ε) log n/n | E_{k}) ℙ(E_{k})

≥ q ∑_{k∈A} ℙ(E_{k}).

(18)

Now, by Lemma 1(ii) with α = 1 − 2ε, if n is large enough,

ℙ((14) fails) ≤ ∑_{i∈A} ℙ(U′_{i} < (1 − 2ε)U_{i}) ≤ n_{A}e^{1−n_{B} log n/n}
= O(n^{1−ε}n^{−1}) = o(1).

Similarly,

ℙ((15) fails) ≤ ∑_{i∈A} ℙ(T_{ik} < 3\frac{log n}{n}) ≤ 3n_{A} \frac{log n}{n} = o(1),

while ℙ((16) fails) = o(1) by the already proven part (ii) of the theorem.

Consequently, q = 1 − o(1), which by (18) and (10) yields ℙ(max_{i} Y_{i} ≥ (3 − 7ε) log n/n) → 1 as n → ∞. This completes the proof of (iii).

Proof of Theorem 2. We use (7), replacing t by −t, and obtain for every a and t > 0

ℙ(Y_{1} < a log n/n) ≤ 𝔼 e^{ta log n−tnY_{1}} ≤ e^{ta log n} ∏_{1}^{n−1}(1 + \frac{nt}{k(n − k)})^{−1}

= exp(ta log n + ∑_{1}^{n−1} − log(1 + \frac{nt}{k(n − k)}))

≤ exp(ta log n + ∑_{1}^{n−1}(−\frac{nt}{k(n − k)} + \frac{1}{2}(\frac{nt}{k(n − k)})^{2}))

= exp(at log n − 2t log n + O(t) + O(t^{2})).

If 0 < a < 2, we thus obtain for any constant t

ℙ(min_{i} Y_{i} < a log n/n) ≤ n ℙ(Y_{1} < a log n/n) = O(n^{1+(a−2)t}),

which is o(1) provided t > 1/(2−a). On the other hand, Theorem 1(ii) implies

ℙ(min_{i} Y_{i} > (2 + ε) log n/n) ≤ ℙ(Y_{1} > (2 + ε) log n/n) → 0

for every ε > 0, and the proof is complete.

3. Asymptotic distributions and moments

The method above also yields the asymptotic distributions of X_{ij} and Y_{i}; these are not normal. More precisely, we have the following result. (We have to impose a slightly stronger condition on the distribution of the T_{ij}; the condition is satisfied for the exponential and uniform distributions.)

Theorem 4. Suppose that the distribution function ℙ(T_{ij} ≤ t) = t+o(t/| log t|) as t ↘ 0. Then, as n → ∞,

nX_{ij} − log n − γ →^{d} ∑_{1}^{∞} \frac{1}{k}(ξ_{k} − 1) + ζ  (19)

and

nY_{i} − 2 log n − 2γ →^{d} ∑_{1}^{∞} \frac{1}{k}(ξ_{k} − 1) + ∑_{1}^{∞} \frac{1}{k}(ξ′_{k} − 1),  (20)

where γ is Euler’s constant, and the random variables ξ_{k}, ξ′_{k}, k ≥ 1, and ζ are independent with ξ_{k}, ξ′_{k} ∈ Exp(1) while ζ has the logistic distribution ℙ(ζ ≤ x) = e^{x}/(1 + e^{x}).

Proof. By a slight modification of the coupling argument in the proof of Theorem 1, it suffices to consider the case T_{ij} ∈ Exp(1); we omit the details.

We write A_{n} ≈ B_{n} to mean that 𝔼(A_{n} − B_{n})^{2} = o(1) as n → ∞. In the exponential case, (4) and (1) imply that

nX_{12} =^{d} ∑_{1}^{N} \frac{n}{k(n − k)}ξ_{k} = ∑_{1}^{N} \frac{n}{k(n − k)}(ξ_{k} − 1) + ∑_{1}^{N}(\frac{1}{k} + \frac{1}{n − k} )

≈ ∑_{1}^{N} \frac{1}{k}(ξ_{k} − 1) + log N + γ + log n − log(n − N)

≈ ∑_{1}^{∞} \frac{1}{k}(ξ_{k} − 1) + log \frac{N/n}{1 − N/n} + log n + γ,

and

nY_{1} =^{d} ∑_{1}^{n−1} \frac{n}{k(n − k)}ξ_{k} = ∑_{1}^{n−1} \frac{n}{k(n − k)}(ξ_{k} − 1) + 2 ∑_{1}^{n−1} \frac{1}{k}

≈ ∑_{1}^{⌊n/2⌋} \frac{1}{k}(ξ_{k} − 1) + ∑_{⌊n/2⌋+1}^{n−1} \frac{1}{n − k} (ξ_{k} − 1) + 2 log n + 2γ

=^{d} ∑_{1}^{⌊n/2⌋} \frac{1}{k}(ξ_{k} − 1) + ∑_{1}^{⌈n/2⌉−1} \frac{1}{k}(ξ′_{k} − 1) + 2 log n + 2γ.

The result follows, since N/n →^{d} η, where η ∈ U(0, 1), and ζ = log(η/(1 − η)) has the logistic distribution.

Since the moment generating function 𝔼 e^{tξ_{k}} of ξ_{k} equals (1 − t)^{−1}, Re t < 1, it follows that the moment generating function of ∑ \frac{1}{k}(ξ_{k} − 1) is

∏_{k=1}^{∞}(1 − t/k)^{−1}e^{−t/k} = lim_{n→∞} ∏_{k=1}^{n} \frac{k}{k − t}e^{−t ∑_{k=1}^{n} \frac{1}{k}}

= lim_{n→∞} \frac{Γ(n + 1)Γ(1 − t)}{Γ(n + 1 − t)}e^{−t log n−tγ+o(1)}

= Γ(1 − t)e^{−tγ}, Re t < 1;

hence the moment generating function of W = ∑ \frac{1}{k}(ξ_{k} −1)+γ equals Γ(1−t), Re t < 1. Now, if T ∈ Exp(1), then − log T has the moment generating function 𝔼 e^{−t log T} = 𝔼 T^{−t} = ∫_{0}^{∞} x^{−t}e^{−x} dx = Γ(1 − t) too. Thus W =^{d} − log T. (Recall that the restriction of the moment generating function to the imaginary axis yields the characteristic function, which determines the distribution.) Hence,

ℙ(W ≤ x) = ℙ(log T ≥ −x) = ℙ(T ≥ e^{−x}) = e^{−e^{−x}},  −∞ < x < ∞, (21)

which is one of the standard extreme value distributions [2].

Consequently, the right hand side of (20) can be written W +W′−2γ, where W and W′ are independent random variables with the distribution (21).

Moreover, the logistic distribution has the moment generating function, for | Re t| < 1, with η ∈ U(0, 1) as above,

𝔼 e^{t log(η/(1−η))} = ∫_{0}^{1} x^{t}(1 − x)^{−t} dx = B(1 + t, 1 − t) = Γ(1 + t)Γ(1 − t),

which equals the moment generating function of the symmetrization W − W′.

Thus ζ =^{d} W − W′.

We can now restate Theorem 4 as follows.

Theorem 5. Suppose that the distribution function ℙ(T_{ij} ≤ t) = t+o(t/| log t|) as t ↘ 0. Then, as n → ∞,

nX_{ij} − log n →^{d} W_{1} + W_{2} − W_{3}  (22)

and

nY_{i} − 2 log n →^{d} W_{1} + W_{2},  (23)

where W_{1}, W_{2}, W_{3} are independent random variables with the same extreme value distribution ℙ(W_{i} ≤ x) = e^{−e^{−x}}.

The variables on the right hand sides of (22) and (23) have the moment generating functions Γ(1 − t)^{2}Γ(1 + t), | Re t| < 1, and Γ(1 − t)^{2}, Re t < 1, respectively, and thus the characteristic functions Γ(1−it)^{2}Γ(1+it) and Γ(1− it)^{2}. The limit W_{1} + W_{2} in (23) has a density function that can be expressed using modified Bessel functions as 2e^{−x}K_{0}(2e^{−x/2}), cf. e.g. [3, (5.10.23)]. We do not know any simple expression for the density function of W_{1} + W_{2} − W_{3}.

Using the fact that the variance of the logistic distribution is π^{2}/3 (which follows from its moment generating function Γ(1 + t)Γ(1 − t) = πt/ sin πt, | Re t| < 1, or from the representation W −W′ above), it is easily seen that the limiting variables in (19) and (20) have expectations 0 and variances ∑_{1}^{∞} k^{−2}+ π^{2}/3 = π^{2}/2 and 2 ∑_{1}^{∞} k^{−2} = π^{2}/3, respectively. Since all approximations and limits in the proof hold in L^{2} sense, we obtain that these are the limits of the expectations and variances of the left hand sides in (19) and (20) too, provided T_{ij} ∈ Exp(1). This carries over to other distributions as well, in particular to the uniform distribution; we have the following theorem.

Theorem 6. Suppose that the distribution function ℙ(T_{ij} ≤ t) = t+o(t/| log t|) as t ↘ 0, and that 𝔼 T_{ij}^{p} < ∞ for some p > 0. Then all moments converge in (19), (20), (22) and (23); in particular,

𝔼 X_{ij} = \frac{log n}{n} + \frac{γ}{n} + o(\frac{1}{n}),
𝔼 Y_{i} = 2\frac{log n}{n} + \frac{2γ}{n} + o(\frac{1}{n}),
Var X_{ij} ∼ \frac{π^{2}}{2n^{2}} ,
Var Y_{i} ∼ \frac{π^{2}}{3n^{2}} .

Proof. It suffices to prove that 𝔼(nX_{ij}−log n)^{m} = O(1) and 𝔼(nY_{i}−2 log n)^{m} = O(1) for every even integer m and n large enough, since this implies convergence of all moments of order < m by a standard result on uniform integrability.

When T_{ij} is exponentially distributed, this can be done as for the case m = 2 in the proof of Theorem 1; we omit the details.

In general, we let a and b be two constants, to be chosen later, and split the expectation into three parts. (We treat only X_{ij}; the same argument applies to Y_{i}.)

First, 𝔼((nX_{ij} − log n)^{m}1[X_{ij} ≤ a log n/n]) = O(1) by comparison with the exponential case, using the coupling argument as in earlier proofs.

Secondly, 𝔼((nX_{ij})^{m}1[a log n/n < X_{ij} ≤ b]) ≤ b^{m}n^{m} ℙ(X_{ij} > a log n/n) = O(n^{m+2−a} log^{2} n) by (8); choosing a = m + 3 this becomes bounded.

Finally, considering only the n − 2 paths of length 2 between i and j, we see that

ℙ(X_{ij} > x) ≤ ℙ(T_{ik} > x/2 or T_{jk} > x/2 for every k ≠ i, j)
≤ (2 ℙ(T_{ij} > x/2))^{n−2}.

Now, if 𝔼 T_{ij}^{p} < ∞, then x^{p} ℙ(T_{ij} > x) → 0 as x → ∞; it follows that if b is large enough, then 2 ℙ(T_{ij} > x/2) < x^{−p} when x ≥ b, and thus

ℙ(X_{ij} > x) ≤ x^{−(n−2)p}, x ≥ b.

Consequently,

\begin{aligned}𝔼((nX_{ij})^{m}1[X_{ij} > b]) & = n^{m}b^{m} ℙ(X_{ij} > m) + n^{m} ∫_{b}^{∞} mx^{m−1} ℙ(X_{ij} > x) dx \\ & = O(n^{m}b^{−np}) = O(1), \end{aligned}

provided n > 2 + m/p.

Combining these estimates we find 𝔼(nX_{ij} −log n)^{m} = O(1) as required.

Remark 2. The asymptotic variances can also be obtained by refining the estimates used in the proof of Theorem 1.

Remark 3. The condition that 𝔼 T_{ij}^{p} < ∞ for some p > 0 is necessary too; if it fails then X_{ij} has no finite moment for any n. In fact, suppose that e.g. 𝔼 X_{ij} < ∞ for some n; then ℙ(X_{ij} > t) < 1/t for large t. Since ℙ(X_{ij} > t) ≥ ℙ(T_{ik} > t for every k ≠ i) = ℙ(T_{ij} > t)^{n−1}, this yields ℙ(T_{ij} > t) < t^{−1/(n−1)} (t large), and thus for example 𝔼 T_{ij}^{1/n} < ∞.

We do not know any similar results for max_{i,j} X_{ij}.

Problem 1. What is the asymptotic distribution of max_{i,j} X_{ij}? (Presuming that some exists.)

Problem 2. What is the order of Var(max_{i,j} X_{ij})? Is it ∼ c/n^{2}? If so, what is the constant c?

4. Lengths of minimal paths

We have so far studied the weights of the minimal paths, but one might also ask how long they are, disregarding their weights, i.e., how many edges they contain. Let L_{ij} be the length of the path between i and j that has minimal weight.

For the case of exponentially distributed T_{ij}, these lengths can be studied by observing that the proof of Theorem 1 shows that the collection of minimal weight paths from a given vertex, 1 say, form a tree (rooted at 1) which can be constructed as follows: Begin with a single root and add n − 1 vertices one by one, each time joining the new vertex to a (uniformly) randomly chosen old vertex. This type of random tree is known as a random recursive tree, and it is known that if D_{k} is the depth of the kth vertex, then D_{n}/ log n →^{p} 1 [4] and max_{k≤n} D_{k}/ log n →^{p} e [5] as n → ∞; see also the survey [6].

This leads to the following result; our condition on the distribution of T_{ij} is presumably much stronger than really required.

Theorem 7. Suppose that T_{ij} has a density function f(t) = 1+O(t) for t > 0. Then, as n → ∞:

(i) For any fixed i and j,

\frac{L_{ij}}{log n} →^{p} 1.

(ii) For any fixed i,

\frac{max_{j≤n} L_{ij}}{log n} →^{p} e.

Proof. The case when T_{ij} ∈ Exp(1) follows from the discussion before the theorem; we have L_{ij} = D_{N}, where N is uniformly distributed over 2, …, n, and max_{j≤n} L_{ij} = max_{k≤n} D_{k}.

In general, we first observe that we may, for a given n, modify the distribution of T_{ij} on the interval t ≥ 5 log n/n without affecting the result, since, by Theorem 1, edges with such large weights hardly ever are used. Hence we may assume that its density function is 1 + O(log n/n) times the density function e^{−t} of the exponential distribution, uniformly for all t > 0. It is now easy to see that the minimum weight paths from i = 1 form a random tree, obtained by adding vertices one by one as above, with the modification that the probability that the kth vertex (in order of insertion) is joined to the lth, for l < k, may depend on the previous history of the tree but always is (1 + O(log n/n))/(k − 1). We may couple this random tree growing process with the one with equal probabilities 1/(k − 1) in such a way that the probability that a vertex k is joined to different preceding vertices in the two trees is O(log n/n), even if we condition on the previous history. It follows that if we fix the end vertex j, the path from i = 1 to j is the same in both trees with probability 1−O(log^{2} n/n), which, by the result for the exponential case, implies (i) for a general distribution.

For (ii) we observe that if D_{k} is the depth of the kth vertex (in order of insertion) in the tree, and D̄_{k} is the depth in the random recursive tree with uniformly chosen ancestors, then, by the above, D_{k} = D̄_{k} for every k ≤ n_{1} = n/ log^{2} n with probability 1 − O(n_{1} log n/n) = 1 − O(1/ log n). Since max_{k≤n_{1}} D̄_{k}/ log n_{1} →^{p} e by the result quoted above [5], it follows that for every ε > 0, with probability 1 − o(1),

max_{k≤n} D_{k} ≥ max_{k≤n_{1}} D_{k} = max_{k≤n_{1}} D̄_{k} ≥ (e − ε) log n_{1} = (e − ε − o(1)) log n,

which by max_{j≤n} L_{ij} = max_{k≤n} D_{k} proves one half of the result.

For the opposite half, define the generating functions

F_{m}(t) = 𝔼 ∑_{k=1}^{m} t^{D_{k}}

and

F̄_{m}(t) = 𝔼 ∑_{k=1}^{m} tD̄_{k}

The recursive definition of the tree yields 𝔼 tD̄_{m+1} = \frac{t}{m} F̄_{m}(t) and thus

F̄_{m+1}(t) = (1 + \frac{t}{m})F̄_{m}(t),

which together with D̄_{1} = 0 yields

F̄_{m}(t) = \frac{Γ(m + t)}{Γ(m)Γ(1 + t)}.

Choosing t = e we obtain, for every a > e,

ℙ(max_{k≤n} D̄_{k} ≥ a log n) ≤ ℙ(∑_{k=1}^{n} eD̄_{k} ≥ n^{a}) ≤ n^{−a}F̄_{n}(e) ∼ n^{−a+e}/Γ(e + 1)

which tends to 0 as n → ∞.

For D_{k} we similarly obtain the inequalities, for some C < ∞ and all t > 0,

𝔼 t^{D_{m+1}} ≤ \frac{t}{m}(1 + C \frac{log n}{n})F_{m}(t),
F_{m+1}(t) ≤ (1 + \frac{t}{m}(1 + C \frac{log n}{n}))F_{m}(t),

and thus

F_{m}(t) ≤ F̄_{m}(t(1 + C \frac{log n}{n})).

which yields, similarly as above,

ℙ(max_{k≤n} D_{k} ≥ a log n) ≤ n^{−a}F_{n}(e) ≤ n^{−a}F̄_{n}(e + Ce log n/n) ∼ n^{−a+e}/Γ(e + 1)

which tends to 0 as n → ∞ for a > e.

Problem 3. How large is max_{i,j} L_{ij}?

We can show that, if α ≈ 3.591 is defined by α log α − α = 1, then for every ε > 0, ℙ(e − ε < max_{i,j} L_{ij}/ log n < α + ε) → 1. Hence it is natural to conjecture that max_{i,j} L_{ij}/ log n converges in probability to a constant in [e, α]. Which?

References

[1] B. Bollobás, Random Graphs. Academic Press, London 1985.

[2] M.R. Leadbetter, G. Lindgren and H. Rootzén, Extremes and Related Properties of Random Sequences and Processes. Springer-Verlag, New York 1983.

[3] N.N. Lebedev, Special Functions and their Applications. Dover, New York, 1972. (Translated from Russian.)

[4] J. Moon, The distance between nodes in recursive trees. In Combinatorics (British Combinatorial Conference, Aberystwyth, 1973), London Math. Soc. Lecture Note 13, Cambridge Univ. Press, London 1974, pp. 125–132.

[5] B. Pittel, Note on the heights of random recursive trees and random m-ary search trees. Random Struct. Alg. 5 (1994), 337–347.

[6] R.T. Smythe and H. Mahmoud, A survey of recursive trees. Theory Probab. Math. Statist. 51 (1995), 1–27.

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

  E-mail address: svante.janson@math.uu.se