Self-similar and Markov composition structures

A. V. Gnedin   ; J. Pitman

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XIII, Tome 326 (2005), pp. 59-84

Résumé

The bijection between composition structures and random closed subsets of the unit interval implies that the composition structures associated with $S\cap[0,1]$ for a self-similar random set $S\subset{\mathbb R}_+$ are those which are consistent with respect to a simple truncation operation. Using the standard coding of compositions by finite strings of binary digits starting with a 1, the random composition of $n$ is defined by the first $n$ terms of a random binary sequence of infinite length. The locations of 1s in the sequence are the places visited by an increasing time-homogeneous Markov chain on the positive integers if and only if $S=\exp(-W)$ for some stationary regenerative random subset $W$ of the real line. Complementing our study in previous papers, we identify self-similar Markovian composition structures associated with the two-parameter family of partition structures.

Bibliographie

[1] R. Arratia, “On the central role of scale invariant Poisson processes on $(0,\infty)$”, Microsurveys in discrete probability (Princeton, NJ, 1997), Amer. Math. Soc., Providence, RI, 21–41 | MR | Zbl

[2] R. Arratia, A. D. Barbour, S. Tavaré, Logarithmic combinatorial structures: a probabilistic approach, EMS Monographs in Mathematics, European Mathematical Society, Zürich, 2003 | MR | Zbl

[3] A. D. Barbour, A. V. Gnedin, Regenerative compositions in the case of slow variation, arXiv: /math.PR/0505171 | MR

[4] J. Bunge, C. Goldie, “Record sequences and their applications”, Handbook of Statistics, Elsevier. Handb. Stat., 19, eds. D. N. Shanbhag, C. R. Rao, Elsevier, Amsterdam, 2001, 277–308 | MR | Zbl

[5] P. Donnelly, P. Joyce, “Consistent ordered sampling distributions: characterization and convergence”, Adv. Appl. Prob., 23 (1991), 229–258 | DOI | MR | Zbl

[6] A. V. Gnedin, “The representation of composition structures”, Ann. Probab., 25 (1997), 1437–1450 | DOI | MR | Zbl

[7] A. V. Gnedin, “The Bernoulli sieve”, Bernoulli, 10 (2004), 79–96 | DOI | MR | Zbl

[8] A. V. Gnedin, “Three sampling formulas”, Combin. Probab. Comput., 13 (2004), 185–193 | DOI | MR | Zbl

[9] A. V. Gnedin, J. Pitman, “Regenerative composition structures”, Ann. Probab., 33 (2005), 445–479 | DOI | MR | Zbl

[10] A. V. Gnedin, J. Pitman, “Regenerative partition structures”, Elec. J. Comb., 11:2 (2004–2005), R12 | MR

[11] A. V. Gnedin, J. Pitman, M. Yor, “Asymptotic laws for composition structures derived from transformed subordinators”, Ann. Probab., to appear | MR

[12] A. V. Gnedin, J. Pitman, M. Yor, Asymptotic laws for regenerative compositions: gamma subordinators and the like, arXiv: /math.PR/0405440 | MR

[13] S. Nacu, Increments of random partitions, arXiv: /math.PR/0310091 | MR

[14] J. Pitman, “Partition structures derived from Brownian motion and stable subordinators”, Bernoulli, 3 (1997), 79–96 | DOI | MR | Zbl

[15] J. Pitman, Combinatorial stochastic processes, Ecole d'Ete de Probabilites de Saint-Flour XXXII, 2002, Lecture Notes in Mathematics, 1875, Springer, Berlin, 2006 | MR | Zbl

[16] J. Pitman, M. Yor, “The two-parameter Poisson–Dirichlet distribution derived from transformed subordinator”, Ann. Probab., 25 (1996), 855–900 | MR

[17] J. Pitman, M. Yor, “Random discrete distributions derived from self-similar random sets”, Electron. J. Probab., 1 (1996), 1–28 | MR | Zbl

[18] M. I. Taksar, “Stationary Markov sets”, L. N. Math., 1247 (1986), 302–340 | MR

[19] J. E. Young, Partition-valued stochastic processes with applications, PhD thesis, UC Berkeley, 1995 | MR