×

zbMATH — the first resource for mathematics

Rayleigh processes, real trees, and root growth with re-grafting. (English) Zbl 1086.60050
A complete metric space \((X,d)\) is said to be a real tree if for all \(x, y\in X\) there exists a unique isometric embedding \(\varphi_{x,y}: [0,d(x,y)]\to X\) such that \(\varphi_{x,y}(0)=x, \varphi_{x,y}(d(x,y))=y\) and for every injective continuous map \(\psi: [0,1]\to X\) one has \(\psi([0,1])=\varphi_{\psi(0),\psi(1)}([0,d(\psi(0),\psi(1))]).\) The real trees form a class of metric spaces that extends the class of trees with edge lengths by allowing behavior such as infinite total edge length and vertices with infinite branching degrees. Aldous’ Brownian continuum random tree may be treated as a random compact real tree. The Aldous-Broder algorithm is a Markov chain on the space of rooted combinatorial trees with \(N\) vertices that has the uniform tree as a stationary distribution. The authors construct and study a Markov process on the space of all rooted compact real trees that has the continuum random tree as its stationary distribution and appears as a scaling limit as \(N\to\infty\) of the Aldous-Broder chain. An essential novelty of this paper is the use of a pointed Gromov-Hausdorff distance to metrize the space of rooted compact real trees.

MSC:
60J27 Continuous-time Markov processes on discrete state spaces
60B05 Probability measures on topological spaces
60B99 Probability theory on algebraic and topological structures
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aldous, D.J.: The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discrete Math. 3(4), 450–465 (1990), MR 1069105 · Zbl 0717.05028 · doi:10.1137/0403039
[2] Aldous, D.: The continuum random tree I. Ann. Probab. 19, 1–28 (1991), MR 1085326 · Zbl 0722.60013 · doi:10.1214/aop/1176990534
[3] Aldous, D.: The continuum random tree. II. An overview. Stochastic analysis (Durham, 1990), London Math. Soc. Lecture Note Ser. Vol. 167, MR 1166406 · Zbl 0747.05077
[4] Aldous, D.: The continuum random tree III. Ann. Probab. 21, 248–289 (1993), MR 1207226 · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[5] Aldous, D.: Recursive self-similarity for random trees, random triangulations and Brownian excursion. Ann. Probab. 22 (2), 527–545 (1994), MR 1288122 · Zbl 0808.60017 · doi:10.1214/aop/1176988720
[6] Aldous, D.: Triangulating the circle, at random. Am. Math. Monthly 101 (3), 223–233 (1994), MR 1264002 · Zbl 0804.52011 · doi:10.2307/2975599
[7] Aldous, D.: Mixing time for a Markov chain on cladograms. Combinatorics, Probability, and Computing 9, 191–204 (2000), MR 1774749 · Zbl 0961.60077 · doi:10.1017/S096354830000417X
[8] Aldous, D.J., Tsoucas, P.: A proof of the Markov chain theorem. Stat. Probab. Letters 8, 189–192 (1989), MR 1017890 · Zbl 0679.60069 · doi:10.1016/0167-7152(89)90016-3
[9] Burago, D., Burago, Y., Ivanov, S.: A course in metric geometry. Graduate studies in mathematics, vol. 33, AMS, Boston, MA, 2001, MR 1835418 · Zbl 0981.51016
[10] Bestvina, M.: \(\mathbb{R}\)-trees in topology, geometry, and group theory. Handbook of geometric topology, North-Holland, Amsterdam, 2002, MR 1886668 · Zbl 0998.57003
[11] Bridson, M.R., Haefliger, A.: Metric spaces of non-positive curvature. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, MR 1744486
[12] Billera, L.J., Holmes, S.P., Vogtman, K.: Geometry of the space of phylogenetic trees. Adv. Appl. Math. 27, 733–767 (2001), MR 1867931 · Zbl 0995.92035 · doi:10.1006/aama.2001.0759
[13] Broder, A.: Generating random spanning trees. 30th IEEE Symp. Found. Comp. Sci. 1989, pp. 442–447
[14] Borodin, A.N., Salminen, P.: Handbook of Brownian motion—facts and formulae. second ed., Probability and its Applications, MR 1912205 · Zbl 0859.60001
[15] Cai, H.: Piecewise deterministic Markov processes. Stochastic Anal. MR 1220886
[16] Colombo, G., Dai Pra, P.: A class of piecewise deterministic Markov processes. Markov Process. Related Fields 7 (2), 2001, MR 1856497 · Zbl 0986.60067
[17] Chiswell, I.: Introduction to \(\Lambda\)-trees. World Scientific, MR 1851337 · Zbl 0872.20027
[18] Costa, O.L.V.: Stationary distributions for piecewise-deterministic Markov processes. J. Appl. Probab. 27 (1), 60–73 (1990), MR 1039184 · Zbl 0703.60068 · doi:10.2307/3214595
[19] Davis, M.H.A.: Piecewise-deterministic Markov processes: a general class of nondiffusion stochastic models. J. Roy. Statist. Soc. Ser. B, MR 790622
[20] Davis, M.H.A.: Markov models and optimization. Monographs on Statistics and MR 1283589
[21] Dufour, F., Costa, O.L.V.: Stability of piecewise-deterministic Markov processes. SIAM J. Control Optim. MR 1710229 · Zbl 1159.60339
[22] Dumas, V., Guillemin, F., Robert, P.: A Markovian analysis of additive-increase multiplicative-decrease algorithms. Adv. in MR 1895332 · Zbl 1002.60091
[23] Diaconis, P., Holmes, S.: Matching and phylogenetic trees. Proc. Nat. Acad. Sci. U.S.A. 53, 321–402 (1998), MR 1665632 · Zbl 0908.92023
[24] Duquesne, T., Le Gall, J.-F.: Random trees, Lévy processes and spatial branching processes. Astérisque (281), 2002, MR 1954248
[25] Duquesne, T., Le Gall, J.-F.: Probabilistic and fractal aspects of Lévy trees. Preprint, 2004
[26] Dress, A., Moulton, V., Terhalle, W.: T-theory: an overview. European J. Combin. 17 (2–3), 161–175 (1996), MR 1379369 · Zbl 0853.54027
[27] Dress, A.W.M.: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorical properties of metric spaces. Adv. Math. 53, 321–402 (1984), MR 753872 · Zbl 0562.54041 · doi:10.1016/0001-8708(84)90029-X
[28] Dress, A.W.M., Terhalle, W.F.: The real tree. Adv. Math. 120, 283–301 (1996), MR 1397084 · Zbl 0855.05040 · doi:10.1006/aima.1996.0040
[29] Ethier, S.N., Kurtz, T.G.: Markov processes. John Wiley & Sons Inc., New York, 1986, Characterization and convergence. MR 838085 · Zbl 0592.60049
[30] Evans, S.N., Pitman, J.: Stationary Markov processes related to stable Ornstein-Uhlenbeck processes and the additive coalescent. MR 1649003 · Zbl 0934.60046
[31] Evans, S.N.: Snakes and spiders: Brownian motion on \(\mathbb{R}\)-trees. Probab. Theory Relat. Fields 117 (3), 2000, MR 1774068 · Zbl 0959.60070
[32] Felsenstein, J.: Inferring phylogenies. Sinauer Associates, 2003
[33] Gromov, M.: Metric structures for Riemannian and non-Riemannian spaces. Progress in Mathematics, vol. 152, Birkhäuser Boston Inc., Boston, MA, 1999, Based on the 1981 French original [MR 85e:53051], With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean, MR 1699320 · Zbl 0953.53002
[34] Hasofer, A.M.: On the derivative and the upcrossings of the Rayleigh process. Austral. J. Statist. 12, 150–151 (1970), MR 298755 · Zbl 0222.60028 · doi:10.1111/j.1467-842X.1970.tb00235.x
[35] Jacod, J., Skorokhod, A.V.: Jumping Markov processes. Ann. Inst. Henri Poincaré 32, 11–67 (1996), MR 1373726 · Zbl 0841.60066
[36] Le Gall, J.-F.: Spatial branching processes, random snakes and partial differential equations. Lectures in Mathematics ETH Zürich, MR 1714707
[37] Miller, K.S., Bernstein, R.I., Blumenson, L.E.: Rayleigh processes. MR 94862
[38] Morgan, J.W.: \(\Lambda\)-trees and their applications. Bull. Am. MR 1100579 · Zbl 0767.05054
[39] Paulin, F.: Topologie de Gromov équivariante, structures hyperboliques et arbres réels. Invent. Math. 94 (1), 1988, MR 958589 · Zbl 0673.57034
[40] Paulin, F.: The Gromov topology on R-trees. Topology Appl. MR 1007101
[41] Pitman, J.: Combinatorial stochastic processes. Tech. Report 621, Dept. Statistics, U.C. Berkeley, 2002, Lecture notes for St. Flour course, July 2002. Available via http://www.stat.berkeley.edu/tech-reports/
[42] Pittel, B.: Note on exact and asymptotic distributions of the parameters of the loop-erased random walk on the complete graph. Mathematics and computer science, II (Versailles, 2002), Trends Math., Birkhäuser, MR 1940151 · Zbl 1030.05109
[43] Peres, Y., Revelle, D.: Scaling limits of the uniform spanning tree and loop-erased random walk on finite graphs. Preprint. arXiv:math.PR/0410430, 2004
[44] Prüfer, H.: Neuer Beweis eines Satzes über Permutationen. Arch. Math. Phys. 27, 742–744 (1918) · JFM 46.0106.04
[45] Propp, J.G., Wilson, D.B.: How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph. J. Algorithms 27 (2), 170–217 (1998), 7th Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996). MR 1622393 · Zbl 0919.68092 · doi:10.1006/jagm.1997.0917
[46] Shalen, P.B.: Dendrology of groups: an introduction. Essays in group theory. Math. Sci. Res. Inst. Publ. Vol. 8, Springer, New York, 1987, MR 919830 · Zbl 0649.20033
[47] Shalen, P.B.: Dendrology and its applications. Group theory from a geometrical viewpoint (Trieste, 1990), World Sci. Publishing, River Edge, NJ, MR 1170376
[48] Semple, C., Steel, M.: Phylogenetics. Oxford Lecture Series in Mathematics and its Applications. Vol. 24, Oxford Univ. Press, Oxford, 2003, MR 2060009 · Zbl 1043.92026
[49] Terhalle, W.F.: R-trees and symmetric differences of sets. Europ. J. Combinatorics 18, 825–833 (1997), MR 1478827 · Zbl 0882.05042 · doi:10.1006/eujc.1996.0134
[50] Wilson, D.B.: Generating random spanning trees more quickly than the cover time. Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996) (New York), ACM, 1996, MR 1427525 · Zbl 0946.60070
[51] Wilson, D.B., Propp, J.G.: How to get an exact sample from a generic Markov chain and sample a random spanning tree from a directed graph, both within the cover time. Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996) (New York), MR 1381954 · Zbl 0847.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.