Trickle-down processes and their boundaries

  • 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' ϕ 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 σ-fields.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Steven Neil Evans, Rudolf Grübel, Anton WakolbingerGND
ArXiv Id:
Parent Title (English):Electronic journal of probability
Publisher:EMIS ELibEMS
Place of publication:[Madralin]
Document Type:Article
Year of Completion:2014
Date of first Publication:2012/01/01
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2014/01/27
Tag:Catalan number; Chinese restaurant process; Dirichlet random measure; Ewens sampling formula; Griffiths–Engen–McCloskey distribution; Mallows model; Poisson boundary; binary search tree; composition; digital search tree; h-transform; harmonic function; internal diffusion limited aggregation; q-binomial theorem; quincunx; random partition; random recursive tree; σ-field
Page Number:58
First Page:1
Last Page:58
Institutes:Informatik und Mathematik / Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
MSC-Classification:60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Jxx Markov processes / 60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60-XX PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX) / 60Jxx Markov processes / 60J50 Boundary theory
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68Wxx Algorithms (For numerical algorithms, see 65-XX; for combinatorics and graph theory, see 05C85, 68Rxx) / 68W40 Analysis of algorithms [See also 68Q25]
Licence (German):License LogoCreative Commons - Namensnennung 3.0