Exchangeable Gibbs partitions and Stirling triangles

A. V. Gnedin   ; J. Pitman

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XII, Tome 325 (2005), pp. 83-102

Résumé

For two collections of nonnegative and suitably normalised weights $W=(W_j)$ and $V=(V_{n,k})$, a probability distribution on the set of partitions of the set $\{1,\ldots,n\}$ is defined by assigning to a generic partition $\{A_j, j\leq k\}$ the probability $V_{n,k}\,W_{|A_1|}\cdots W_{|A_k|}$, where $|A_j|$ is the number of elements of $A_j$. We impose constraints on the weights by assuming that the resulting random partitions $\Pi_n$ of $[n]$ are consistent as $n$ varies, meaning that they define an exchangeable partition of the set of all natural numbers. This implies that the weights $W$ must be of a very special form depending on a single parameter $\alpha\in[-\infty,1]$. The case $\alpha=1$ is trivial, and for each value of $\alpha\ne 1$ the set of possible $V$-weights is an infinite-dimensional simplex. We identify the extreme points of the simplex by solving the boundary problem for a generalised Stirling triangle. In particular, we show that the boundary is discrete for $-\infty\le\alpha<0$ and continuous for $0\le\alpha<1$. For $\alpha\le 0$ the extremes correspond to the members of the Ewens–Pitman family of random partitions indexed by $(\alpha,\theta)$, while for $0<\alpha<1$ the extremes are obtained by conditioning an $(\alpha,\theta)$-partition on the asymptotics of the number of blocks of $\Pi_n$ as $n$ tends to infinity.

Bibliographie

[1] D. J. Aldous, “Exchangeability and related topics”, École d'été de probabilités de Saint-Flour, XIII—1983, Lecture Notes Math., 1117, Springer, Berlin, 1985, 1–198 | MR

[2] D. J. Aldous, “Tail behavior of birth-and-death and stochastically monotone processes”, Probab. Theory Related Fields, 62:3 (1983), 375–394 | MR | Zbl

[3] 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

[4] A. Borodin, G. Olshanski, “Harmonic functions of multiplicative graphs and interpolation polynomials”, Electron. J. Combin., 7 (2000) | MR

[5] P. Diaconis, D. Freedman, “Partial exchangeability and sufficiency”, Statistics Applications and New Directions, Proceedings of the Indian Statistical Institute Golden Jubilee International Conference, eds. J. K. Ghosh, J. Roy, Indian Statistical Institute, Sankhya, 1984, 205–236 | MR

[6] E. B. Dynkin, “Sufficient statistics and extreme points”, Ann. Probab., 6 (1978), 705–730 | DOI | MR | Zbl

[7] C. Banderier, P. Flajolet, G. Schaeffer, M. Soria, “Random maps, coalescing saddles, singularity analysis and Airy phenomena”, Random Structures Algorithms, 19 (2001), 194–246 | DOI | MR | Zbl

[8] P. Flajolet, J. Gabarró, H. Pekari, “Analytic urns.”, Ann. Probab., 33:3 (2005), 1200–1233 | DOI | MR | Zbl

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

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

[11] J. G. Kemeny, J. L. Snell, A. W. Knopp, Denumerable Markov Chains, Springer, New York, 1976 | MR

[12] S. V. Kerov, “Combinatorial examples in the theory of AF-algebras”, Zap. Nauchn. Semin. LOMI, 172, 1989, 55–67 | MR

[13] S. Kerov, “Coherent random allocations and the Ewens–Pitman sampling formula”, Zap. Nauchn. Semin. POMI, 325, 2005, 127–145 | MR | Zbl

[14] S. Kerov, Asymptotic Representation Theory of the Symmetric Group and Its Applications in Analysis, Amer. Math. Soc., Providence, RI, 2003 | MR | Zbl

[15] S. Kerov, “The boundary of Young lattice and random Young tableaux”, Formal power series and algebraic combinatorics. Series formelles et combinatoire algebrique 1994, Invited lectures presented at the 6th international DIMACS workshop (May 23–27, 1994), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 24, eds. Billera, Louis J. et al., American Mathematical Society, Providence, RI, 1996, 133–158 | MR | Zbl

[16] S. Kerov, A. Okounkov, G. Olshanski, “The boundary of the Young graph with Jack edge multiplicities”, Int. Math. Res. Not., 4 (1998), 173–199 | DOI | MR | Zbl

[17] J. F. C. Kingman, The Mathematics of Genetic Diversity, CBMS-NSF Reg. Conf. Ser. Appl. Math., 34, 1980 | MR | Zbl

[18] G. Labelle, P. Leroux, E. Pergola, R. Pinzani, “Stirling numbers interpolation using permutations with forbidden sequences”, Discrete Math., 246:1–3 (2002), 177–195 | DOI | MR | Zbl

[19] G. Olshanski, $q$-Pascal triangle and $q$-Young, 2001, Unpublished

[20] J. Pitman, “Exchangeable and partially exchangeable random partitions”, Probab. Theory Related Fields, 102 (1995), 145–158 | DOI | MR | Zbl

[21] J. Pitman, “Poisson–Kingman partitions”, Science and Statistics: A Festschrift for Terry Speed, IMS Lecture Notes – Monograph Series, 40, ed. D. R. Goldstein, Institute of Mathematical Statistics, Hayward, California, 2003, 1–34 | MR

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

[23] J. Pitman, “An extension of de Finetti's theorem”, Adv. Appl. Probab., 10 (1978), 268–270 | DOI

[24] J. Pitman, Combinatorial Stochastic Processes, Technical Report No 621, Dept. Statistics, U. C. Berkeley

[25] J. Pitman, “Brownian motion, bridge, excursion and meander characterized by sampling at independent uniform times”, Electron. J. Probab., 4:11 (1999), 1–33 | MR

[26] A. Regev , Y. Roichman,, Statistics of wreath products and generalized Bernoulli–Stirling numbers, Preprint, 2004 ; arXiv: /math.CO/0404354 | MR

[27] E. G. Tsylova, “Probabilistic methods for obtaining asymptotic formulas for generalized Stirling numbers”, Statistical Estimation and Hypothesis Testing Methods, Perm. Gos. Univ., Perm., 1991, 165–178 | MR

[28] E. G. Tsylova, “The asymptotic behavior of generalized Stirling numbers”, Combinatorial-Algebraic Methods in Applied Mathematics, Gor'kov. Gos. Univ., Gorki, 1985, 143–154, 158 | MR

[29] A. M. Vershik, “Statistical mechanics of combinatorial partitions, and their limit shapes”, Funct. Anal. Appl., 30 (1996), 90–105 | DOI | MR | Zbl