## 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)$$.

### MSC:

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

### References:

  Aldous, D. and Pitman, J. (1994). Brownian bridge asymptotics for random mappings. Random Structures Algorithms 5 487–512. · Zbl 0811.60057  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  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  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  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  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  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  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  Doksum, K. (1974). Tailfree and neutral random probabilities and their posterior distributions. Ann. Probab. 2 183–201. · Zbl 0279.60097  Donnelly, P. and Joyce, P. (1991). Consistent ordered sampling distributions: Characterization and convergence. Adv. in Appl. Probab. 23 229–258. · Zbl 0724.60040  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.  Feller, W. (1971). An Introduction to Probability Theory and its Applications II , 2nd ed. Wiley, New York. · Zbl 0219.60003  Gnedin, A. V. (1997). The representation of composition structures. Ann. Probab. 25 1437–1450. · Zbl 0895.60037  Gnedin, A. V. (1998). On the Poisson–Dirichlet limit. J. Multivariate Anal. 67 90–98. · Zbl 0949.62017  Gnedin, A. V. (2004). The Bernoulli sieve. Bernoulli 10 79–96. · Zbl 1044.60005  Gnedin, A. V. (2004). Three sampling formulas. Combin. Probab. Comput. 13 185–193. · Zbl 1060.62039  Gnedin, A. V. and Pitman, J. (2003). Regenerative composition structures, Version 2. Available at arxiv.org/abs/math.PR/0307307v2. · Zbl 1070.60034  Gnedin, A. V. and Pitman, J. (2004). Regenerative partition structures. Available at arxiv.org/abs/math.PR0408071. · Zbl 1075.60005  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  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  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  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  James, L. F. (2003). Poisson calculus for spatial neutral to the right processes. Available at arxiv.org/abs/math.PR/0305053. · Zbl 1091.62012  Karlin, S. (1967). Central limit theorems for certain infinite urn schemes. J. Math. Mech. 17 373–401. · Zbl 0154.43701  Kerov, S. (1995). Coherent random allocations and the Ewens–Pitman formula. PDMI Preprint, Steklov Math. Institute, St. Petersburg. · Zbl 1077.60007  Kingman, J. F. C. (1978). The representation of partition structures. J. London Math. Soc. 18 374–380. · Zbl 0415.92009  Kingman, J. F. C. (1980). The Mathematics of Genetic Diversity . SIAM, Philadelphia, PA. · Zbl 0458.92009  Maisonneuve, B. (1983). Ensembles régénératifs de la droite. Z. Wahrsch. Verw. Gebiete 63 501–510. · Zbl 0496.60033  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  Pitman, J. (1995). Exchangeable and partially exchangeable random partitions. Probab. Theory Related Fields 102 145–158. · Zbl 0821.60047  Pitman, J. (1997). Partition structures derived from Brownian motion and stable subordinators. Bernoulli 3 79–96. · Zbl 0882.60081  Pitman, J. (1999). Coalescents with multiple collisions. Ann. Probab. 27 1870–1902. · Zbl 0963.60079  Pitman, J. (2002). Combinatorial stochastic processes. Technical Report 621, Dept. Statistics, Univ. California, Berkeley. Available at http://www.stat.berkeley.edu/tech-reports/.  Pitman, J. (2003). Poisson–Kingman partitions. Science and Statistics : A Festschrift for Terry Speed 30 (D. R. Goldstein, ed.) 1–34. IMS, Hayward, CA.  Pitman, J. and Speed, T. P. (1973). A note on random times. Stochastic Process. Appl. 1 369–374. · Zbl 0275.60060  Pitman, J. and Yor, M. (1996). Random discrete distributions derived from self-similar random sets. Electron. J. Probab. 1 1–28. · Zbl 0891.60042  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  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  Sawyer, S. and Hartl, D. (1985). A sampling theory for local selection. J. Genet. 64 21–29.  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.