Regenerative composition structures. (English) Zbl 1070.60034

A composition of \(n\) with parts \(n_1,\dots, n_k\) is an ordered sequence \((n_1,\dots, n_k)\) of positive integers with sum \(n\). A random composition is a random variable \(C_n\) with values in the set of compositions of \(n\). A composition structure \((C_n)\) is a Markovian sequence \(C_n\), \(n= 1,2,\dots\), of random compositions having sampling consistency: \(n\) identical balls are distributed into an ordered series of boxes according to \(C_n\) and \(C_{n-1}\) is obtained by discarding one ball at random and deleting any empty box created. The composition structure \((C_n)\) is regenerative if, given that the first part \(F_n\) of \(C_n\) is \(m\), the remaining composition of \(n-m\) is distributed as \(C_{n-m}\), \(1\leq m< n\). Then \(P(C_n= (n_1,\dots, n_k))\) is a product of decrement matrix elements \(q(h; m)= P(F_h =m)\). This is also sufficient for \((C_n)\) to be regenerative. The \(q(n; m)\) then satisfy a recurrence.
In the above boxes label the balls at random from 1 to \(n\). This gives a random ordered set-partition \(C_n^*\) of \(\{1,\dots,n\}\). The construction of the \(C^*_n\) is consistent by the sampling consistency of \((C_n)\) and so defines a random ordered partition \(C^*\) of \(N\). The regenerative composition structures are characterized (Theorem 5.2) as follows: Let \(R\) be the closed range of a subordinator \(S_t\), \(t\geq 0\). Let \(\varepsilon_1, \varepsilon_2,\dots\) be i.i.d. standard exponentials independent of the \(S_t\) and \(\varepsilon_{1n},\dots, \varepsilon_{nn}\) the increasing order statistics of \(\varepsilon_1,\dots,\varepsilon_n\). The \(j\in \{1,\dots, n\}\) with \(\varepsilon_{jn}\) in a same component of \(R^c\) then define a block of an ordered set-partition of \(\{1,\dots, n\}\), each \(i\) with \(\varepsilon_{in}\in R\) being a singleton of this partition. The sizes of the blocks form a regenerative composition of \(n\).
Further subjects studied are: Examples, e.g. \(X_{hk}\) i.i.d. 0-1 variables. The \(i\)th block is the set of \(h\) with epoch \(i\) of first 0. Or points of an i.i.d. sequence falling into random intervals of \([0,1]\). A two-parameter family of composition structures starting from \(C^*_n\). The effect of the transformation \(z\to 1-\exp(-z)\) giving the random set \(\widetilde R= 1-\exp(-R)\). The \(q(n;n)\) determine the distribution of regenerative \((C_n)\). The frequency of singletons in \(C^*\). Symmetry between \((n_1,\dots, n_k)\) and \((n_k,\dots, n_1)\) or, equivalently, \(\widetilde R\) and \(1-\widetilde R\). A closer study of the intervals of \(R^c\) and sample points \(\varepsilon_{jn}\) inducing a partition of \([0,\infty)\).


60G09 Exchangeability for stochastic processes
60C05 Combinatorial probability
Full Text: DOI arXiv


[1] Aldous, D. and Pitman, J. (1994). Brownian bridge asymptotics for random mappings. Random Structures Algorithms 5 487–512. · Zbl 0811.60057
[2] Aldous, D. and Pitman, J. (2002). Two recursive decompositions of Brownian bridge related to the asymptotics of random mappings. Technical Report 595, Dept. Statistics, Univ. California, Berkeley. Available at http://www.stat.berkeley.edu/tech-reports/. · Zbl 1124.60012
[3] Aldous, D. J. (1985). Exchangeability and related topics. École d ’ Été de Probabilités de Saint-Flour XIII—1983 . Lecture Notes in Math. 1117 1–198. Springer, Berlin. · Zbl 0562.60042
[4] Berg, C., Christensen, J. P. R. and Ressel, P. (1984). Harmonic Analysis on Semigroups. Theory of Positive Definite and Related Functions 100 . Springer, New York. · Zbl 0619.43001
[5] Bertoin, J. (1999). Subordinators: Examples and applications. École d ’ Été de Probabilités de Saint-Flour XXVII . Lecture Notes in Math. 1727 1–198. Springer, Berlin. · Zbl 0955.60046
[6] Bertoin, J. and Yor, M. (2001). On subordinators, self-similar Markov processes and some factorizations of the exponential variable. Electron. Comm. Probab. 6 95–106. · Zbl 1024.60030
[7] Bruss, F. T. and O’Cinneide, C. A. (1990). On the maximum and its uniqueness for geometric random samples. J. Appl. Probab. 27 598–610. · Zbl 0723.60011
[8] Carmona, P., Petit, F. and Yor, M. (1997). On the distribution and asymptotic results for exponential functionals of Lévy processes. In Exponential Functionals and Principal Values Related to Brownian Motion 73–130. Rev. Mat. Iberoamericana, Madrid. · Zbl 0905.60056
[9] Doksum, K. (1974). Tailfree and neutral random probabilities and their posterior distributions. Ann. Probab. 2 183–201. · Zbl 0279.60097
[10] Donnelly, P. and Joyce, P. (1991). Consistent ordered sampling distributions: Characterization and convergence. Adv. in Appl. Probab. 23 229–258. · Zbl 0724.60040
[11] Ewens, W. J. and Tavaré, S. (1995). The Ewens sampling formula. In Multivariate Discrete Distributions (N. S. Johnson, S. Kotz and N. Balakrishnan, eds.). Wiley, New York.
[12] Feller, W. (1971). An Introduction to Probability Theory and its Applications II , 2nd ed. Wiley, New York. · Zbl 0219.60003
[13] Gnedin, A. V. (1997). The representation of composition structures. Ann. Probab. 25 1437–1450. · Zbl 0895.60037
[14] Gnedin, A. V. (1998). On the Poisson–Dirichlet limit. J. Multivariate Anal. 67 90–98. · Zbl 0949.62017
[15] Gnedin, A. V. (2004). The Bernoulli sieve. Bernoulli 10 79–96. · Zbl 1044.60005
[16] Gnedin, A. V. (2004). Three sampling formulas. Combin. Probab. Comput. 13 185–193. · Zbl 1060.62039
[17] Gnedin, A. V. and Pitman, J. (2003). Regenerative composition structures, Version 2. Available at arxiv.org/abs/math.PR/0307307v2. · Zbl 1070.60034
[18] Gnedin, A. V. and Pitman, J. (2004). Regenerative partition structures. Available at arxiv.org/abs/math.PR0408071. · Zbl 1075.60005
[19] Gnedin, A. V., Pitman, J. and Yor, M. (2003). Asymptotic laws for composition derived from transformed subordinators. Available at arxiv.org/abs/math.PR/0403438. · Zbl 1142.60327
[20] Gnedin, A. V., Pitman, J. and Yor, M. (2004). Asymptotic laws for regenarative composition: Gamma subordinators and the like. Available at arxiv.org/abs/math.PR0405440. · Zbl 1099.60023
[21] Gradinaru, M., Roynette, B., Vallois, P. and Yor, M. (1999). Abel transform and integrals of Bessel local times. Ann. Inst. H. Poincaré Probab. Statist. 35 531–572. · Zbl 0937.60080
[22] Hoppe, F. M. (1987). The sampling theory of neutral alleles and an urn model in population genetics. J. Math. Biol. 25 123–159. · Zbl 0636.92007
[23] James, L. F. (2003). Poisson calculus for spatial neutral to the right processes. Available at arxiv.org/abs/math.PR/0305053. · Zbl 1091.62012
[24] Karlin, S. (1967). Central limit theorems for certain infinite urn schemes. J. Math. Mech. 17 373–401. · Zbl 0154.43701
[25] Kerov, S. (1995). Coherent random allocations and the Ewens–Pitman formula. PDMI Preprint, Steklov Math. Institute, St. Petersburg. · Zbl 1077.60007
[26] Kingman, J. F. C. (1978). The representation of partition structures. J. London Math. Soc. 18 374–380. · Zbl 0415.92009
[27] Kingman, J. F. C. (1980). The Mathematics of Genetic Diversity . SIAM, Philadelphia, PA. · Zbl 0458.92009
[28] Maisonneuve, B. (1983). Ensembles régénératifs de la droite. Z. Wahrsch. Verw. Gebiete 63 501–510. · Zbl 0496.60033
[29] Neretin, Yu. A. (1996). The group of diffeomorphisms of a ray, and random Cantor sets. Mat. Sb. 187 73–84. [Translation in Sbornik Math. 187 857–868.] · Zbl 0871.58013
[30] Pitman, J. (1995). Exchangeable and partially exchangeable random partitions. Probab. Theory Related Fields 102 145–158. · Zbl 0821.60047
[31] Pitman, J. (1997). Partition structures derived from Brownian motion and stable subordinators. Bernoulli 3 79–96. · Zbl 0882.60081
[32] Pitman, J. (1999). Coalescents with multiple collisions. Ann. Probab. 27 1870–1902. · Zbl 0963.60079
[33] Pitman, J. (2002). Combinatorial stochastic processes. Technical Report 621, Dept. Statistics, Univ. California, Berkeley. Available at http://www.stat.berkeley.edu/tech-reports/.
[34] Pitman, J. (2003). Poisson–Kingman partitions. Science and Statistics : A Festschrift for Terry Speed 30 (D. R. Goldstein, ed.) 1–34. IMS, Hayward, CA.
[35] Pitman, J. and Speed, T. P. (1973). A note on random times. Stochastic Process. Appl. 1 369–374. · Zbl 0275.60060
[36] Pitman, J. and Yor, M. (1996). Random discrete distributions derived from self-similar random sets. Electron. J. Probab. 1 1–28. · Zbl 0891.60042
[37] Pitman, J. and Yor, M. (1997). On the lengths of excursions of some Markov processes. Séminaire de Probabilités XXXI . Lecture Notes in Math. 1655 272–286. Springer, Berlin. · Zbl 0884.60071
[38] Pitman, J. and Yor, M. (1997). The two-parameter Poisson–Dirichlet distribution derived from a stable subordinator. Ann. Probab. 25 855–900. · Zbl 0880.60076
[39] Sawyer, S. and Hartl, D. (1985). A sampling theory for local selection. J. Genet. 64 21–29.
[40] Young, J. E. (1995). Partition-valued stochastic processes with applications. Ph.D. dissertation, Univ. California, Berkeley.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.