Regenerative partition structures

Alexander Gnedin ; Jim Pitman

The electronic journal of combinatorics, The Stanley Festschrift volume, Tome 11 (2004) no. 2

Résumé

A partition structure is a sequence of probability distributions for $\pi_n$, a random partition of $n$, such that if $\pi_n$ is regarded as a random allocation of $n$ unlabeled balls into some random number of unlabeled boxes, and given $\pi_n$ some $x$ of the $n$ balls are removed by uniform random deletion without replacement, the remaining random partition of $n-x$ is distributed like $\pi_{n-x}$, for all $1 \le x \le n$. We call a partition structure regenerative if for each $n$ it is possible to delete a single box of balls from $\pi_n$ in such a way that for each $1 \le x \le n$, given the deleted box contains $x$ balls, the remaining partition of $n-x$ balls is distributed like $\pi_{n-x}$. Examples are provided by the Ewens partition structures, which Kingman characterised by regeneration with respect to deletion of the box containing a uniformly selected random ball. We associate each regenerative partition structure with a corresponding regenerative composition structure, which (as we showed in a previous paper) is associated in turn with a regenerative random subset of the positive halfline. Such a regenerative random set is the closure of the range of a subordinator (that is an increasing process with stationary independent increments). The probability distribution of a general regenerative partition structure is thus represented in terms of the Laplace exponent of an associated subordinator, for which exponent an integral representation is provided by the Lévy-Khintchine formula. The extended Ewens family of partition structures, previously studied by Pitman and Yor, with two parameters $(\alpha,\theta)$, is characterised for $0 \le \alpha < 1$ and $\theta >0$ by regeneration with respect to deletion of each distinct part of size $x$ with probability proportional to $(n-x)\tau+x(1-\tau)$, where $\tau = \alpha/(\alpha+\theta)$.

Détail

DOI : 10.37236/1869

Classification : 60C05, 60G09
Mots-clés : regenerative composition structure, deletion kernel