Coding multitype forests: Application to the law of the total population of branching forests

Chaumont, Loïc; Liu, Rongli

doi:10.1090/tran/6421

Coding multitype forests: Application to the law of the total population of branching forests
HTML articles powered by AMS MathViewer

by Loïc Chaumont and Rongli Liu PDF

Trans. Amer. Math. Soc. 368 (2016), 2723-2747 Request permission

Abstract:

By extending the breadth first search algorithm to any $d$-type critical or subcritical irreducible branching forest, we show that such forests can be encoded through $d$ independent, integer valued, $d$-dimensional random walks. An application of this coding, together with a multivariate extension of the Ballot Theorem which is obtained here, allows us to give an explicit form of the law of the total population, jointly with the number of subtrees of each type, in terms of the offspring distribution of the branching process.

References

Krishna B. Athreya and Peter E. Ney, Branching processes, Die Grundlehren der mathematischen Wissenschaften, Band 196, Springer-Verlag, New York-Heidelberg, 1972. MR 0373040
Olivier Bernardi and Alejandro H. Morales, Counting trees using symmetries, J. Combin. Theory Ser. A 123 (2014), 104–122. MR 3157803, DOI 10.1016/j.jcta.2013.12.001
Jean Bertoin, The structure of the allelic partition of the total population for Galton-Watson processes with neutral mutations, Ann. Probab. 37 (2009), no. 4, 1502–1523. MR 2546753, DOI 10.1214/08-AOP441
Jean-François Le Gall, Random trees and applications, Probab. Surv. 2 (2005), 245–311. MR 2203728, DOI 10.1214/154957805100000140
Meyer Dwass, The total progeny in a branching process and a related random walk, J. Appl. Probability 6 (1969), 682–686. MR 253433, DOI 10.2307/3212112
I. J. Good, Generalizations to several variables of Lagrange’s expansion, with applications to stochastic processes, Proc. Cambridge Philos. Soc. 56 (1960), 367–380. MR 123021, DOI 10.1017/s0305004100034666
Theodore E. Harris, The theory of branching processes, Dover Phoenix Editions, Dover Publications, Inc., Mineola, NY, 2002. Corrected reprint of the 1963 original [Springer, Berlin; MR0163361 (29 #664)]. MR 1991122
T. E. Harris, First passage and recurrence distributions, Trans. Amer. Math. Soc. 73 (1952), 471–486. MR 52057, DOI 10.1090/S0002-9947-1952-0052057-2
Igor Kortchemski, Invariance principles for Galton-Watson trees conditioned on the number of leaves, Stochastic Process. Appl. 122 (2012), no. 9, 3126–3172. MR 2946438, DOI 10.1016/j.spa.2012.05.013
Grégory Miermont, Invariance principles for spatial multitype Galton-Watson trees, Ann. Inst. Henri Poincaré Probab. Stat. 44 (2008), no. 6, 1128–1161 (English, with English and French summaries). MR 2469338, DOI 10.1214/07-AIHP157
Nariyuki Minami, On the number of vertices with a given degree in a Galton-Watson tree, Adv. in Appl. Probab. 37 (2005), no. 1, 229–264. MR 2135161, DOI 10.1239/aap/1113402407
Charles J. Mode, Multitype branching processes. Theory and applications, Modern Analytic and Computational Methods in Science and Mathematics, No. 34, American Elsevier Publishing Co., Inc., New York, 1971. MR 0279901
J. W. Moon, Some determinant expansions and the matrix-tree theorem, Discrete Math. 124 (1994), no. 1-3, 163–171. Graphs and combinatorics (Qawra, 1990). MR 1258851, DOI 10.1016/0012-365X(92)00059-Z
Richard Otter, The multiplicative process, Ann. Math. Statistics 20 (1949), 206–224. MR 30716, DOI 10.1214/aoms/1177730031
J. Pitman, Combinatorial stochastic processes, Lecture Notes in Mathematics, vol. 1875, Springer-Verlag, Berlin, 2006. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002; With a foreword by Jean Picard. MR 2245368
Lajos Takács, A generalization of the ballot problem and its application in the theory of queues, J. Amer. Statist. Assoc. 57 (1962), 327–337. MR 138139
W. T. Tutte, The dissection of equilateral triangles into equilateral triangles, Proc. Cambridge Philos. Soc. 44 (1948), 463–482. MR 27521, DOI 10.1017/s030500410002449x