Limit Laws for the Optimal Directed Tree with Random Costs

Research output: Contribution to journalArticle

Abstract

Suppose that script C = {cij : i, j = 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,. . . ,n. Then the 'cost' of T is denned to be c(T) = S (i,j)?T cij, where (i, j) denotes the directed edge from i to j in the tree T. Let Tn denote the 'optimal' tree, i.e. c(Tn)=min{c(T) : 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 c11, c12,. . . , cin which guarantee the existence of sequences {an}, {bn}, and {dn} such that b-1n(c(Tn)-an) ? N(0, 1) in distribution, d-1n c(Tn) ? 1 in probability, and d-1nE(c(Tn)) ? 1 as n ? 8, 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, . . . , n} into itself. Our results complement and extend those obtained by McDiarmid [9] for optimal branchings in a complete directed graph.

Original languageEnglish
Pages (from-to)315-335
Number of pages21
JournalCombinatorics, Probability and Computing
Volume6
Issue number3
Publication statusPublished - 1997

Fingerprint

Limit Laws
Costs
Random Mapping
Denote
Continuous random variable
Rooted Trees
Order Statistics
Complete Graph
Directed Graph
Branching
Complement
Asymptotic Behavior
Non-negative
Moment

Cite this

@article{63bca10a5c654bf18f80b8f9da1b5e6f,
title = "Limit Laws for the Optimal Directed Tree with Random Costs",
abstract = "Suppose that script C = {cij : i, j = 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,. . . ,n. Then the 'cost' of T is denned to be c(T) = S (i,j)?T cij, where (i, j) denotes the directed edge from i to j in the tree T. Let Tn denote the 'optimal' tree, i.e. c(Tn)=min{c(T) : 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 c11, c12,. . . , cin which guarantee the existence of sequences {an}, {bn}, and {dn} such that b-1n(c(Tn)-an) ? N(0, 1) in distribution, d-1n c(Tn) ? 1 in probability, and d-1nE(c(Tn)) ? 1 as n ? 8, 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, . . . , n} into itself. Our results complement and extend those obtained by McDiarmid [9] for optimal branchings in a complete directed graph.",
author = "Hansen, {Jennie C.}",
year = "1997",
language = "English",
volume = "6",
pages = "315--335",
journal = "Combinatorics, Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",
number = "3",

}

Limit Laws for the Optimal Directed Tree with Random Costs. / Hansen, Jennie C.

In: Combinatorics, Probability and Computing, Vol. 6, No. 3, 1997, p. 315-335.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Limit Laws for the Optimal Directed Tree with Random Costs

AU - Hansen, Jennie C.

PY - 1997

Y1 - 1997

N2 - Suppose that script C = {cij : i, j = 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,. . . ,n. Then the 'cost' of T is denned to be c(T) = S (i,j)?T cij, where (i, j) denotes the directed edge from i to j in the tree T. Let Tn denote the 'optimal' tree, i.e. c(Tn)=min{c(T) : 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 c11, c12,. . . , cin which guarantee the existence of sequences {an}, {bn}, and {dn} such that b-1n(c(Tn)-an) ? N(0, 1) in distribution, d-1n c(Tn) ? 1 in probability, and d-1nE(c(Tn)) ? 1 as n ? 8, 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, . . . , n} into itself. Our results complement and extend those obtained by McDiarmid [9] for optimal branchings in a complete directed graph.

AB - Suppose that script C = {cij : i, j = 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,. . . ,n. Then the 'cost' of T is denned to be c(T) = S (i,j)?T cij, where (i, j) denotes the directed edge from i to j in the tree T. Let Tn denote the 'optimal' tree, i.e. c(Tn)=min{c(T) : 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 c11, c12,. . . , cin which guarantee the existence of sequences {an}, {bn}, and {dn} such that b-1n(c(Tn)-an) ? N(0, 1) in distribution, d-1n c(Tn) ? 1 in probability, and d-1nE(c(Tn)) ? 1 as n ? 8, 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, . . . , n} into itself. Our results complement and extend those obtained by McDiarmid [9] for optimal branchings in a complete directed graph.

UR - http://www.scopus.com/inward/record.url?scp=0031515486&partnerID=8YFLogxK

M3 - Article

VL - 6

SP - 315

EP - 335

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

SN - 0963-5483

IS - 3

ER -