Invasion percolation on Galton-Watson trees. (English) Zbl 1466.60211

Summary: We consider invasion percolation on Galton-Watson trees. On almost every Galton-Watson tree, the invasion cluster almost surely contains only one infinite path. This means that for almost every Galton-Watson tree, invasion percolation induces a probability measure on infinite paths from the root. We show that under certain conditions of the progeny distribution, this measure is absolutely continuous with respect to the limit uniform measure. This confirms that invasion percolation, an efficient self-tuning algorithm, may be used to sample approximately from the limit uniform distribution. Additionally, we analyze the forward maximal weights along the backbone of the invasion cluster and prove a limit law for the process.


60K35 Interacting random processes; statistical mechanics type models; percolation theory
Full Text: DOI arXiv Euclid


[1] [ABF13] L. Addario-Berry and K. Ford. Poisson-Dirichlet branching random walks. Ann. Appl. Prob., 23:283-307, 2013. · Zbl 1278.60129
[2] [AGdHS08] O. Angel, J. Goodman, F. den Hollander, and G. Slade. Invasion percolation on regular trees. Ann. Probab., 36:420-466, 2008. · Zbl 1145.60050
[3] [AGM13] O. Angel, J. Goodman, and M. Merle. Scaling limit of the invasion percolation cluster on a regular tree. Ann. Probab., 41:229-261, 2013. · Zbl 1281.60076
[4] [AN72] K. Athreya and P. Ney. Branching Processes. Springer-Verlag, New York, 1972. · Zbl 0259.60002
[5] [Azu67] Kazuoki Azuma. Weighted sums of certain dependent random variables. Tôhoku Math. J. (2), 19:357-367, 1967. · Zbl 0178.21103 · doi:10.2748/tmj/1178243286
[6] [BD74] N. Bingham and R. Doney. Asymptotic properties of supercritical branching processes I: the Galton-Watson process. Adv. Appl. Prob., 6:711-731, 1974. · Zbl 0297.60044
[7] [Bil99] Patrick Billingsley. Convergence of probability measures. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons, Inc., New York, second edition, 1999. A Wiley-Interscience Publication. · Zbl 0944.60003
[8] [DSV09] M. Damron, A. Sapozhnikov, and B. Vágvölgyi. Relations between invasion percolation and critical percolation in two dimensions. Ann. Probab., 37:2297-2331, 2009. · Zbl 1247.60134
[9] [Dub71] Serge Dubuc. Problèmes relatifs à l’itération de fonctions suggérés par les processus en cascade. Ann. Inst. Fourier (Grenoble), 21(1):171-251, 1971. · Zbl 0196.12801
[10] [Dur10] R. Durrett. Probability: Theory and Examples. Duxbury Press, New York, NY, fourth edition, 2010. · Zbl 1202.60001
[11] [FN71] D. H. Fuk and S. V. Nagaev. Probabilistic inequalities for sums of independent random variables. Teor. Verojatnost. i Primenen., 16:660-675, 1971. · Zbl 0259.60024
[12] [Har63] T. Harris. The theory of branching processes. Springer, Berlin, 1963. · Zbl 0117.13002
[13] [HPS99] O. Häggström, Y. Peres, and R. Schonmann. Percolation on transitive graphs as a coalescent process: relentless merging followed by simultaneous uniqueness. In Perplexing problems in probability, volume 44, pages 69-90. Birkhäuser, Boston, 1999. · Zbl 0948.60098
[14] [JS89] M. Jerrum and A. Sinclair. Approximate counting, uniform generation and rapidly mixing markov chains. Inform. and Comput., 82:93-133, 1989. · Zbl 0668.05060
[15] [Kes86] H. Kesten. The incipient infinite cluster in two-dimensional percolation. Prob Theory Rel. Fields, 73:369-394, 1986. · Zbl 0584.60098 · doi:10.1007/BF00776239
[16] [LP17] R. Lyons and Y. Peres. Probability on trees and networks. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2017.
[17] [LPP96] R. Lyons, R. Pemantle, and Y. Peres. Biased random walks on galton-watson trees. Prob. Th. Rel. Fields, 106:249-264, 1996. · Zbl 0859.60076
[18] [Lyo90] R. Lyons. Random walks and percolation on trees. Ann. Probab., 18:931-958, 1990. · Zbl 0714.60089 · doi:10.1214/aop/1176990730
[19] [MPR18] M. Michelen, R. Pemantle, and J. Rosenberg. Quenched Survival of Bernoulli Percolation on Galton-Watson Trees. 2018. arXiv:1805.03693 · Zbl 1458.60097
[20] [RS00] D. Randall and A. Sinclair. Self-testing algorithms for self-avoiding walks. Journal of Mathematical Physics, 41:1570-1584, 2000. · Zbl 0977.82020 · doi:10.1063/1.533197
[21] [WW83] D. Wilkinson and J. Willemsen. Invasion percolation: a new form of percolation theory. J. Phys., ser. A: Math. Gen., 16:3365-3376, 1983.
[22] [Zha95] Y. Zhang. The fractal volume of the two-dimensional invasion percolation cluster. Comm. Math.Phys., 167:237-254, 1995. · Zbl 0811.60095 · doi:10.1007/BF02100587
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.