Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T17:34:37.553Z Has data issue: false hasContentIssue false
  • English
  • Français

On a random directed spanning tree

Part of: Graph theory Stochastic processes Geometric probability and stochastic geometry

Published online by Cambridge University Press:  01 July 2016

Abhay G. Bhatt  and
Rahul Roy
Abhay G. Bhatt*
Affiliation:
Indian Statistical Institute, Delhi
Rahul Roy*
Affiliation:
Indian Statistical Institute, Delhi
*
∗ Postal address: Indian Statistical Institute, 7 S.J.S. Sansanwal Marg, New Delhi 110016, India.
∗ Postal address: Indian Statistical Institute, 7 S.J.S. Sansanwal Marg, New Delhi 110016, India.
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the asymptotic properties of a minimal spanning tree formed by n points uniformly distributed in the unit square, where the minimality is amongst all rooted spanning trees with a direction of growth. We show that the number of branches from the root of this tree, the total length of these branches, and the length of the longest branch each converges weakly. This model is related to the study of record values in the theory of extreme-value statistics and this relation is used to obtain our results. The results also hold when the tree is formed from a Poisson point process of intensity n in the unit square.

Keywords

Minimal spanning treerecord valuesweak convergence

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry 60G70: Extreme value theory; extremal processes
Secondary: 05C05: Trees 90C27: Combinatorial optimization
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 36 , Issue 1 , March 2004 , pp. 19 - 42
Copyright
Copyright © Applied Probability Trust 2004 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aldous, D. and Steele, J. M. (1992). Asymptotics for Euclidean minimal spanning trees on random points. Prob. Theory Relat. Fields 92, 247–258.Google Scholar
Beardwood, J., Halton, J. H. and Hammersley, J. M. (1959). The shortest path through many points. Proc. Camb. Phil. Soc. 55, 299–327.Google Scholar
Chung, K. L. (1974). A Course in Probability Theory, 2nd edn. Academic Press, New York.Google Scholar
David, H.A. (1970). Order Statistics. John Wiley, New York.Google Scholar
Feller, W. (1978). An Introduction to Probability Theory and Its Applications, Vol. 1. John Wiley, New York.Google Scholar
Gilbert, E. N. (1961). Random plane networks. J. Soc. Indust. Appl. 9, 533–543.Google Scholar
Gradshteyn, I. S. and Ryzhik, I. M. (1980). Table of Integrals, Series and Products. Academic Press, New York.Google Scholar
Gupta, P and Kumar, P. R. (1999). Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis, Control, Optimization and Applications, eds McEneaney, W. M., Yin, G. and Zhang, Q., Birkhäuser, Boston, MA, pp. 547–566.CrossRefGoogle Scholar
Kesten, H. and Lee, S. (1996). The central limit theorem for weighted minimal spanning trees on random points. Ann. Appl. Prob. 6, 495–527.Google Scholar
Rényi, A., (1976). On the extreme elements of observations. In Selected Papers of Alfred Rényi, Vol. 3, Akadémiai Kiadó, Budapest, pp. 50–65.Google Scholar
Rodriguez-Iturbe, I. and Rinaldo, A. (1997). Fractal River Basins, Chance and Self-Organization. Cambridge University Press, New York.Google Scholar
Shohat, J. A. and Tamarkin, J. D. (1950). The Problem of Moments, revised edn (Math. Surveys 1). American Mathematical Society, New York.Google Scholar
Steele, J. M. (1988). Growth rates of Euclidean minimal spanning trees with power weighted edges. Ann. Prob. 16, 1767–1787.Google Scholar