Combinatorics, Probability and Computing


The Min Mean-Weight Cycle in a Random Network


a1 Brown University and Ecole Normale Supérieure, DI ENS, CNRS UMR 8548, 45 rue d'Ulm, 75005 Paris, France (e-mail:

a2 Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA (e-mail:


The mean weight of a cycle in an edge-weighted graph is the sum of the cycle's edge weights divided by the cycle's length. We study the minimum mean-weight cycle on the complete graph on n vertices, with random i.i.d. edge weights drawn from an exponential distribution with mean 1. We show that the probability of the min mean weight being at most c/n tends to a limiting function of c which is analytic for c ≤ 1/e, discontinuous at c = 1/e, and equal to 1 for c > 1/e. We further show that if the min mean weight is ≤ 1/(en), then the length of the relevant cycle is Θ p (1) (i.e., it has a limiting probability distribution which does not scale with n), but that if the min mean weight is > 1/(en), then the relevant cycle almost always has mean weight (1 + o(1))/(en) and length at least (2/π2o (1)) log2 n log log n.

(Received January 18 2012)

(Revised May 01 2013)

(Online publication July 22 2013)

2010 Mathematics subject classification:

  • Primary 05C80;
  • Secondary 68Q87


  Work partly funded by NSF AF 0964037, and partly done while visiting Microsoft Research.