Binary sequential representations of random partitions. (English) Zbl 1093.60008

Young, James E.

Bernoulli 11, No. 5, 847-861 (2005).

From the author’s text: “A partition of \(n\) is simply a collection of positive integers whose sum is \(n\). Let \(\omega_n\) denote the collection of partitions of \(n\) and encode a partition \(\pi\in\omega_n\) via the component counts \((a_1,\dots ,a_n)\), where \(a_i\) is the number of components of size \(i\), for \(i=1,\dots,n\). A partition structure is a sequence of probability measures \(P_1,P_2,\dots\) defined on \(\omega_1,\omega_2,\dots\), respectively, which satisfies the consistency relation \[ \begin{aligned} P_n(a_1,\dots,a_n) = &P_{n+1}(a_1+1,\dots,a_{n+1})\frac{a_1+1}{n+1}\\ &+\sum_{r=2}^{n+1} P_{n+1}(a_1,\dots ,a_{r-1}-1,a_r+1,\dots,a_{n+1}) \frac{r(a_r+1)}{n+1} \end{aligned} \] for all \(n\geq 1\). Partition structures are naturally constructed by sampling individuals of various types from hypothetical infinite populations. If we allow these populations to be random and have ‘novel’ types of individuals, then all partition structures may be constructed in this fashion.”
Let \(\xi=(\xi_1,\xi_2,\dots)\) be a sequence of independent Bernoulli random variables with success probability \(p_n=P(\xi_n=1)\). Define for each \(n\geq 1\) a partition of \([n]=\{1,\dots,n\}\) by \(\Pi_n(\xi)=(a_1,\dots,a_n)\in\omega_n\), where \(a_i\) is the number of \(i\)-spacings between successive \(1\)s in the finite sequence \((\xi_1,\dots,\xi_n)\). It turns out that the sequence \((P_n)\) of distributions of the partitions \(\Pi_n\) forms a random partition if and only if \(p_n=\theta/(\theta+n-1)\) for \(n\geq 1\) with \(\theta=p_2/(1-p_2)\). This is the Ewens’ one-parameter family of partitions. The author obtains a two-parameter generalization of Ewens’ partition by considering random partitions constructed from discrete renewal processes and introducing a convolution-type product on \(0-1\) sequences.

Reviewer: Ljuben Mutafchiev (Sofia)

MSC:

60C05	Combinatorial probability
05A18	Partitions of sets

References:

[1]	Aldous, D.J. (1985) Exchangeability and related topics. In P.-L. Hennequin (ed.), Ecole d\'É té de Probabilités de Saint-Flour XIII. Lecture Notes in Math. 1117. Berlin: Springer-Verlag.
[2]	Aldous, D.J. and Pitman, J. (1993) Brownian bridge asymptotics for random mappings. Random Structures Algorithms, 5, 487-512. · Zbl 0811.60057 · doi:10.1002/rsa.3240050402
[3]	Arratia, R.A. and Tavaré, S. (1992) Limit theorems for combinatorial structures via discrete process approximations. Random Structures Algorithms, 3, 321-345. · Zbl 0758.60009 · doi:10.1002/rsa.3240030310
[4]	Arratia, R.A., Barbour, A.D. and Tavaré, S. (1992) Poisson process approximations for the Ewens sampling formula. Ann. Appl. Probab., 2, 519-535. · Zbl 0756.60006 · doi:10.1214/aoap/1177005647
[5]	Arratia, R.A., Barbour, A.D. and Tavaré, S. (2003) Logarithmic Combinatorial Structures: A Probabilistic Approach. Zurich: European Mathematical Society. · Zbl 1040.60001
[6]	Blackwell, D. and MacQueen, J.B. (1973) Ferguson distributions via Poĺya urn schemes. Ann. Statist., 1, 353-355. · Zbl 0276.62010 · doi:10.1214/aos/1176342372
[7]	Donnelly, P. and Grimmett, G. (1993) On the asymptotic distribution of large prime factors. J. London Math. Soc. (2), 47, 395-404. · Zbl 0839.11039 · doi:10.1112/jlms/s2-47.3.395
[8]	Donnelly, P., Ewens, W.J. and Padmadisastra, S. (1991a) Functionals of random mappings: Exact and asymptotic results. Adv. Appl. Probab., 23, 437-455. JSTOR: · Zbl 0736.60008 · doi:10.2307/1427616
[9]	Donnelly, P., Kurtz, T.G. and Tavaré, S. (1991b) On the functional central limit theorem for the Ewens sampling formula. Ann. Appl. Probab., 1, 539-545. · Zbl 0747.60013 · doi:10.1214/aoap/1177005837
[10]	Ethier, S.N. and Kurtz, T.G. (1981) The infinitely-many-neutral-alleles diffusion model. Adv. Appl. Probab., 13, 429-452. JSTOR: · Zbl 0483.60076 · doi:10.2307/1426779
[11]	Ewens, W.J. (1972) The sampling theory of selectively neutral alleles. Theoret. Popul. Biol., 3, 87-112. · Zbl 0245.92009 · doi:10.1016/0040-5809(72)90035-4
[12]	Feller, W. (1945) The fundamental limit theorems in probability. Bull. Amer. Math. Soc., 51, 800-832. · Zbl 0060.28702 · doi:10.1090/S0002-9904-1945-08448-1
[13]	Feller, W. (1971) An Introduction to Probability Theory and Its Applications, Volume II (2nd edn). New York: Wiley. · Zbl 0219.60003
[14]	Foata, D. (1974) La série génératrice exponentielle dans les problèmes d\'énumération, Séminaire de Mathématiques Supérieures 54. Montreal: Presses de lÚniversité de Montréal. · Zbl 0325.05007
[15]	Goulden, I.P. and Jackson, D.M. (1983) Combinatorial Enumeration. New York: Wiley. · Zbl 0519.05001
[16]	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 · doi:10.1007/BF00276386
[17]	Joyce, P. and Tavaré, S. (1987) Cycles, permutations, and the structure of the Yule process with immigration. Stochastic Process. Appl., 25, 309-314. · Zbl 0625.92011 · doi:10.1016/0304-4149(87)90209-2
[18]	Kingman, J.F.C. (1978a) Random partitions in population genetics. Proc. Roy Soc. Lond. Ser. A, 361, 1-20. · Zbl 0393.92011 · doi:10.1098/rspa.1978.0089
[19]	Kingman, J.F.C. (1978b) The representation of partition structures. J. London Math. Soc. (2), 18, 374-380. · Zbl 0415.92009 · doi:10.1112/jlms/s2-18.2.374
[20]	Kingman, J.F.C. (1980) Mathematics of Genetic Diversity. Philadelphia: Society of Industrial and Applied Mathematics. · Zbl 0458.92009
[21]	Kingman, J.F.C. (1982) The coalescent. Stochastic Process. Appl., 13, 253-248. · Zbl 0491.60076 · doi:10.1016/0304-4149(82)90011-4
[22]	Mekjian, A.Z. (1990) Distribution of cluster sizes from evaporation to total multifragmentation. Phys. Rev. C, 41, 2103-2117. · doi:10.1103/PhysRevC.41.2103
[23]	Mekjian, A.Z. (1991) Cluster distributions in physics and genetic diversity. Phys. Rev. A, 44, 8361- 8374. · doi:10.1103/PhysRevA.44.8361
[24]	Mekjian, A.Z. and Lee, S.J. (1991) Models of fragmentation and partitioning phenomena based on the symmetric group Sn and combinatorial analysis. Phys. Rev. A, 44, 6294-6312. · doi:10.1103/PhysRevA.44.6294
[25]	Perman, M., Pitman, J. and Yor, M. (1992) Size-biased sampling of Poisson point processes and excursions. Probab. Theory Related Fields, 92, 21-39. · Zbl 0741.60037 · doi:10.1007/BF01205234
[26]	Pitman, J. (1992) The two-parameter generalization of Ewensŕandom partition structure. Technical Report 345, Department of Statistics, University of California, Berkeley.
[27]	Pitman, J. (1995) Exchangeable and partially exchangeable random partitions. Probab. Theory Related Fields, 102, 145-158. · Zbl 0821.60047 · doi:10.1007/BF01213386
[28]	Pitman, J. (1996) Random discrete distributions invariant under size-biased permutation. Adv. Appl. Probab., 28, 525-539. JSTOR: · Zbl 0853.62018 · doi:10.2307/1428070
[29]	Pitman, J. (1997) Partition structures derived from Brownian motion and stable subordinators. Bernoulli, 3, 79-96. · Zbl 0882.60081 · doi:10.2307/3318653
[30]	Pitman, J. (2002) Combinatorial Stochastic Processes. Lecture notes for St. Flour course.
[31]	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 · doi:10.1214/aop/1024404422
[32]	Revuz, D. and Yor, M. (1999) Continuous Martingales and Brownian Motion (3rd edn). Berlin: Springer-Verlag. · Zbl 0917.60006
[33]	Rogers, L.C.G. and Williams, D. (2000) Diffusions, Markov Processes, and Martingales, Vol. 2: Ito Calculus (2nd edn). Cambridge: Cambridge University Press. · Zbl 0977.60005
[34]	Vershik, A.M. (1987) The asymptotic distribution of factorizations of natural numbers into prime divisors. Soviet Math. Dokl., 34, 57-61. · Zbl 0625.10033
[35]	Watterson, G.A. (1974) The sampling theory of selectively neutral alleles. Adv. Appl. Probab., 6, 463-488. JSTOR: · Zbl 0289.62020 · doi:10.2307/1426228
[36]	Zabell, S.L. (1992) Predicting the unpredictable. Synthese, 90, 205-232. · Zbl 0757.62006 · doi:10.1007/BF00485351