Trickle-down processes and their boundaries

Steven Neil Evans (University of California at Berkeley)
Rudolf Grübel (Leibniz Universität Hannover)
Anton Wakolbinger (Goethe-Universität Frankfurt am Main)


It is possible to represent each of a number of Markov chains as an evolving sequence of connected subsets of a directed acyclic graph that grow in the following way: initially, all vertices of the graph are unoccupied, particles are fed in one-by-one at a distinguished source vertex, successive particles proceed along directed edges according to an appropriate stochastic mechanism, and each particle comes to rest once it encounters an unoccupied vertex. Examples include the binary and digital search tree processes, the random recursive tree process and generalizations of it arising from nested instances of Pitman's two-parameter Chinese restaurant process, tree-growth models associated with Mallows' $\phi$ model of random permutations and with Schützenberger's non-commutative $q$-binomial theorem, and a construction due to Luczak and Winkler that grows uniform random binary trees in a Markovian manner. We introduce a framework that encompasses such Markov chains, and we characterize their asymptotic behavior by analyzing in detail their Doob-Martin compactifications, Poisson boundaries and tail $\sigma$-fields.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-58

Publication Date: January 1, 2012

DOI: 10.1214/EJP.v17-1698


  • Andrews, George E.; Askey, Richard; Roy, Ranjan. Special functions. Encyclopedia of Mathematics and its Applications, 71. Cambridge University Press, Cambridge, 1999. xvi+664 pp. ISBN: 0-521-62321-9; 0-521-78988-5 MR1688958
  • Aldous, David; Steele, J. Michael. The objective method: probabilistic combinatorial optimization and local weak convergence. Probability on discrete structures, 1--72, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. MR2023650
  • Blei, David M.; Griffiths, Thomas L.; Jordan, Michael I. The nested Chinese restaurant process and Bayesian nonparametric inference of topic hierarchies. J. ACM 57 (2010), no. 2, Art. 7, 30 pp. MR2606082
  • Blackwell, David; Kendall, David. The martin boundary of Pólya's urn scheme, and an application to stochastic population growth. J. Appl. Probability 1 1964 284--296. MR0176518
  • Blackwell, David; MacQueen, James B. Ferguson distributions via Pólya urn schemes. Ann. Statist. 1 (1973), 353--355. MR0362614
  • Chauvin, Brigitte; Drmota, Michael; Jabbour-Hattab, Jean. The profile of binary search trees. Ann. Appl. Probab. 11 (2001), no. 4, 1042--1062. MR1878289
  • Critchlow, Douglas E.; Fligner, Michael A.; Verducci, Joseph S. Probability models on rankings. J. Math. Psych. 35 (1991), no. 3, 294--318. MR1128236
  • Critchlow, Douglas E. Metric methods for analyzing partially ranked data. Lecture Notes in Statistics, 34. Springer-Verlag, Berlin, 1985. x+216 pp. ISBN: 3-540-96288-3 MR0818986
  • Crippa, Davide; Simon, Klaus. $q$-distributions and Markov processes. Discrete Math. 170 (1997), no. 1-3, 81--98. MR1452938
  • Devroye, Luc. Universal limit laws for depths in random trees. SIAM J. Comput. 28 (1999), no. 2, 409--432. MR1634354
  • Diaconis, P.; Fulton, W. A growth model, a game, an algebra, Lagrange inversion, and characteristic classes. Commutative algebra and algebraic geometry, II (Italian) (Turin, 1990). Rend. Sem. Mat. Univ. Politec. Torino 49 (1991), no. 1, 95--119 (1993). MR1218674
  • Dennert, Florian; Grübel, Rudolf. On the subtree size profile of binary search trees. Combin. Probab. Comput. 19 (2010), no. 4, 561--578. MR2647493
  • Dong, Rui; Goldschmidt, Christina; Martin, James B. Coagulation-fragmentation duality, Poisson-Dirichlet distributions and random recursive trees. Ann. Appl. Probab. 16 (2006), no. 4, 1733--1750. MR2288702
  • Diaconis, Persi. Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11. Institute of Mathematical Statistics, Hayward, CA, 1988. vi+198 pp. ISBN: 0-940600-14-5 MR0964069
  • Drmota, Michael; Janson, Svante; Neininger, Ralph. A functional limit theorem for the profile of search trees. Ann. Appl. Probab. 18 (2008), no. 1, 288--333. MR2380900
  • Doob, J. L. Discrete potential theory and boundaries. J. Math. Mech. 8 1959 433--458; erratum 993. MR0107098
  • Fuchs, Michael. Subtree sizes in recursive trees and binary search trees: Berry-Esseen bounds and Poisson approximations. Combin. Probab. Comput. 17 (2008), no. 5, 661--680. MR2454562
  • Fligner, M. A.; Verducci, J. S. Distance based ranking models. J. Roy. Statist. Soc. Ser. B 48 (1986), no. 3, 359--369. MR0876847
  • Goodman, Frederick M.; Kerov, Sergei V. The Martin boundary of the Young-Fibonacci lattice. J. Algebraic Combin. 11 (2000), no. 1, 17--48. MR1747061
  • Gnedin, Alexander; Olshanski, Grigori. The boundary of the Eulerian number triangle. Mosc. Math. J. 6 (2006), no. 3, 461--475, 587. MR2274860
  • Gnedin, Alexander; Olshanski, Grigori. Coherent permutations with descent statistic and the boundary problem for the graph of zigzag diagrams. Int. Math. Res. Not. 2006, Art. ID 51968, 39 pp. MR2211157
  • Gnedin, Alexander; Olshanski, Grigori. A $q$-analogue of de Finetti's theorem. Electron. J. Combin. 16 (2009), no. 1, Research Paper 78, 16 pp. MR2529787
  • Gnedin, Alexander; Olshanski, Grigori. $q$-exchangeability via quasi-invariance. Ann. Probab. 38 (2010), no. 6, 2103--2135. MR2683626
  • Gnedin, A.; Pitman, J. Exchangeable Gibbs partitions and Stirling triangles. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 325 (2005), Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 12, 83--102, 244--245; translation in J. Math. Sci. (N. Y.) 138 (2006), no. 3, 5674--5685 MR2160320
  • Grimmett, G. R. Random labelled trees and their branching networks. J. Austral. Math. Soc. Ser. A 30 (1980/81), no. 2, 229--237. MR0607933
  • Grübel, Rudolf. On the median-of-$k$ version of Hoare's selection algorithm. Theor. Inform. Appl. 33 (1999), no. 2, 177--192. MR1707969
  • Grübel, Rudolf. On the silhouette of binary search trees. Ann. Appl. Probab. 19 (2009), no. 5, 1781--1802. MR2569807
  • Hitczenko, Paweł; Louchard, Guy. Distinctness of compositions of an integer: a probabilistic analysis. Analysis of algorithms (Krynica Morska, 2000). Random Structures Algorithms 19 (2001), no. 3-4, 407--437. MR1871561
  • Janson, Svante. Ideals in a forest, one-way infinite binary trees and the contraction method. Mathematics and computer science, II (Versailles, 2002), 393--414, Trends Math., Birkhäuser, Basel, 2002. MR1940149
  • Janson, Svante. Conditioned Galton-Watson trees do not grow, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Discrete Math. Theor. Comput. Sci. Proc., AG, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2006, pp. 331--334. MR2509643
  • Johnson, Norman L.; Kotz, Samuel. Urn models and their application. An approach to modern discrete probability theory. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, New York-London-Sydney, 1977. xiii+402 pp. MR0488211
  • Knuth, Donald E. The art of computer programming. Vol. 1: Fundamental algorithms. Second printing Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont 1969 xxi+634 pp. MR0286317
  • Knuth, Donald E. The art of computer programming. Volume 3. Sorting and searching. Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. xi+722 pp. (1 foldout). MR0445948
  • Kerov, Sergei; Okounkov, Andrei; Olshanski, Grigori. The boundary of the Young graph with Jack edge multiplicities. Internat. Math. Res. Notices 1998, no. 4, 173--199. MR1609628
  • Kemeny, John G.; Snell, J. Laurie; Knapp, Anthony W. Denumerable Markov chains. Second edition. With a chapter on Markov random fields, by David Griffeath. Graduate Texts in Mathematics, No. 40. Springer-Verlag, New York-Heidelberg-Berlin, 1976. xii+484 pp. MR0407981
  • Lawler, Gregory F.; Bramson, Maury; Griffeath, David. Internal diffusion limited aggregation. Ann. Probab. 20 (1992), no. 4, 2117--2140. MR1188055
  • Luczak, Malwina; Winkler, Peter. Building uniformly random subtrees. Random Structures Algorithms 24 (2004), no. 4, 420--443. MR2060629
  • Mahmoud, Hosam M. Evolution of random search trees. Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1992. xii+324 pp. ISBN: 0-471-53228-2 MR1140708
  • Mallows, C. L. Non-null ranking models. I. Biometrika 44 (1957), 114--130. MR0087267
  • Marden, John I. Analyzing and modeling rank data. Monographs on Statistics and Applied Probability, 64. Chapman & Hall, London, 1995. xiv+329 pp. ISBN: 0-412-99521-2 MR1346107
  • Pitman, J. Combinatorial stochastic processes. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002. With a foreword by Jean Picard. Lecture Notes in Mathematics, 1875. Springer-Verlag, Berlin, 2006. x+256 pp. ISBN: 978-3-540-30990-1; 3-540-30990-X MR2245368
  • Pólya, G. On the number of certain lattice polygons. J. Combinatorial Theory 6 1969 102--105. MR0236031
  • Picardello, Massimo A.; Woess, Wolfgang. The full Martin boundary of the bi-tree. Ann. Probab. 22 (1994), no. 4, 2203--2222. MR1331221
  • Pitman, Jim; Winkel, Matthias. Regenerative tree growth: binary self-similar continuum random trees and Poisson-Dirichlet compositions. Ann. Probab. 37 (2009), no. 5, 1999--2041. MR2561439
  • Revuz, D. Markov chains. North-Holland Mathematical Library, Vol. 11. North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1975. x+336 pp. MR0415773
  • Rogers, L. C. G.; Williams, David. Diffusions, Markov processes, and martingales. Vol. 1. Foundations. Reprint of the second (1994) edition. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 2000. xx+386 pp. ISBN: 0-521-77594-9 MR1796539
  • Sawyer, Stanley A. Martin boundaries and random walks. Harmonic functions on trees and buildings (New York, 1995), 17--44, Contemp. Math., 206, Amer. Math. Soc., Providence, RI, 1997. MR1463727
  • Schützenberger, Marcel Paul. Une interprétation de certaines solutions de l'équation fonctionnelle: $F(x+y)=F(x)F(y)$. (French) C. R. Acad. Sci. Paris 236, (1953). 352--353. MR0053402
  • Sedgewick, R., Flajolet, Ph. An introduction to the analysis of algorithms, Addison-Wesley, Reading, 1996.
  • Smythe, Robert T.; Mahmoud, Hosam M. A survey of recursive trees. (Ukrainian) ; translated from Teor. Ĭmovīr. Mat. Stat. No. 51 (1994), 1--29 Theory Probab. Math. Statist. No. 51 (1995), 1--27 (1996) MR1445048
  • Stanley, Richard P. Enumerative combinatorics. Vol 1. Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997, With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original. MR1442260
  • Teh, Yee Whye; Jordan, Michael I.; Beal, Matthew J.; Blei, David M. Hierarchical Dirichlet processes. J. Amer. Statist. Assoc. 101 (2006), no. 476, 1566--1581. MR2279480
  • von Weizsäcker, Heinrich. Exchanging the order of taking suprema and countable intersections of $\sigma $-algebras. Ann. Inst. H. Poincaré Sect. B (N.S.) 19 (1983), no. 1, 91--100. MR0699981
  • Watanabe, Takesi. A probabilistic method in Hausdorff moment problem and Laplace-Stieltjes transform. J. Math. Soc. Japan 12 1960 192--206. MR0120683
  • Woess, Wolfgang. Random walks on infinite graphs and groups. Cambridge Tracts in Mathematics, 138. Cambridge University Press, Cambridge, 2000. xii+334 pp. ISBN: 0-521-55292-3 MR1743100

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.