Trickle-down processes and their boundaries

DOI10.1214/EJP.V17-1698zbMATH Open1246.60100arXiv1010.0453OpenAlexW2121113001MaRDI QIDQ428599FDOQ428599

Anton Wakolbinger, Rudolf Grübel, Steven Neil Evans

Publication date: 22 June 2012

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: 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 Schuetzenberger'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 work available at URL: https://arxiv.org/abs/1010.0453

Recommendations

• Doob-Martin boundary of Rémy's tree growth chain
• Random recursive trees: a boundary theory approach
• scientific article; zbMATH DE number 20661
• Markov chains indexed by trees
• Doob-Martin compactification of a Markov chain for growing random words sequentially

zbMATH Keywords

Catalan numberMallows modelquincunxChinese restaurant processharmonic functionPoisson boundary\(q\)-binomial theoremcompositioninternal diffusion limited aggregationrandom recursive tree\(h\)-transformEwens sampling formulabinary search treedigital search treeDirichlet random measureGriffiths-Engen-McCloskey distributionrandom partitiontail \(\sigma \)-field

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms (68W40) Random measures (60G57) Boundary theory for Markov processes (60J50)

Cited In (10)

• Refined asymptotics for the composition of cyclic urns
• Combinatiorial Markov chains
• Limits of Mallows trees
• Pruned Discrete Random Samples
• The height of record‐biased trees
• The height of Mallows trees
• Mallows product measure
• Refined quicksort asymptotics
• Search trees: metric aspects and strong limit theorems
• Sampling and learning Mallows and generalized Mallows models under the Cayley distance

This page was built for publication: Trickle-down processes and their boundaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428599)