Details
| Original language | English |
|---|---|
| Pages (from-to) | 1-58 |
| Number of pages | 58 |
| Journal | Electronic journal of probability |
| Volume | 17 |
| Publication status | Published - 2012 |
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' φ model of random permutations and with Schützenberger's non-commutative g-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 com-pactifications, Poisson boundaries and tail cr-fields.
Keywords
- Binary search tree, Catalan number, Chinese restaurant process, Composition, Digital search tree, Dirichlet random measure, E wens sampling formula, Griffiths-engen-mccloskey distribution, h-transform, Harmonic function, Internal diffusion limited aggregation, Mallows model, Poisson boundary, q-binomial theorem, Quincunx, Random partition, Random recursive tree, Tail σ-field
ASJC Scopus subject areas
- Mathematics(all)
- Statistics and Probability
- Decision Sciences(all)
- Statistics, Probability and Uncertainty
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Electronic journal of probability, Vol. 17, 2012, p. 1-58.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Trickle-down processes and their boundaries
AU - Evans, Steven N.
AU - Grübel, Rudolf
AU - Wakolbinger, Anton
PY - 2012
Y1 - 2012
N2 - 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 g-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 com-pactifications, Poisson boundaries and tail cr-fields.
AB - 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 g-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 com-pactifications, Poisson boundaries and tail cr-fields.
KW - Binary search tree
KW - Catalan number
KW - Chinese restaurant process
KW - Composition
KW - Digital search tree
KW - Dirichlet random measure
KW - E wens sampling formula
KW - Griffiths-engen-mccloskey distribution
KW - h-transform
KW - Harmonic function
KW - Internal diffusion limited aggregation
KW - Mallows model
KW - Poisson boundary
KW - q-binomial theorem
KW - Quincunx
KW - Random partition
KW - Random recursive tree
KW - Tail σ-field
UR - http://www.scopus.com/inward/record.url?scp=84856240991&partnerID=8YFLogxK
U2 - 10.1214/EJP.v17-1698
DO - 10.1214/EJP.v17-1698
M3 - Article
AN - SCOPUS:84856240991
VL - 17
SP - 1
EP - 58
JO - Electronic journal of probability
JF - Electronic journal of probability
SN - 1083-6489
ER -