Limit Laws for the Optimal Directed Tree with Random Costs

Abstract

Suppose that [Cscr ]={c_ij[ratio ]i, j[ges ]1} is a collection of i.i.d. nonnegative continuous random variables and suppose T is a rooted, directed tree on vertices labelled 1,2,[ctdot ],n. Then the ‘cost’ of T is defined to be c(T)=[sum ] _(i,j)∈Tc_ij, where (i, j) denotes the directed edge from i to j in the tree T. Let T_n denote the ‘optimal’ tree, i.e. c(T_n) =min{c(T)[ratio ]T is a directed, rooted tree in with n vertices}. We establish general conditions on the asymptotic behaviour of the moments of the order statistics of the variables c₁₁, c₁₂, [ctdot ], c_in which guarantee the existence of sequences {a_n}, {b_n}, and {d_n} such that b⁻¹_n (c(T_n)−a_n) →N(0, 1) in distribution, d⁻¹_nc(T_n)→1 in probability, and d⁻¹_nE(c(T_n))→1 as n→∞, and we explicitly determine these sequences. The proofs of the main results rely upon the properties of general random mappings of the set {1, 2, [ctdot ], n} into itself. Our results complement and extend those obtained by McDiarmid [9] for optimal branchings in a complete directed graph.