60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Refine
Document Type
- Article (2) (remove)
Language
- English (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- Catalan number (1)
- Chinese restaurant process (1)
- Dirichlet random measure (1)
- Ewens sampling formula (1)
- Griffiths–Engen–McCloskey distribution (1)
- Mallows model (1)
- Poisson boundary (1)
- binary search tree (1)
- coalescent (1)
- composition (1)
Institute
- Mathematik (2)
In this paper we prove asymptotic normality of the total length of external branches in Kingman's coalescent. The proof uses an embedded Markov chain, which can be described as follows: Take an urn with n black balls. Empty it in n steps according to the rule: In each step remove a randomly chosen pair of balls and replace it by one red ball. Finally remove the last remaining ball. Then the numbers Uk, 0 < k < n, of red balls after k steps exhibit an unexpected property: (U0, ... ,Un) and (Un, ... ;U0) are equal in distribution.
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.