Regenerative partition structures (Q1773151)

A partition structure is a sequence of stochastic partitions \(\pi_n= (\pi_{n1}, \pi_{n2},\dots)\) of \(n\), \(n=1,2,\dots\), where the parts \(\pi_{ni}\) are random variables with \(\pi_{n1}\geq\pi_{n2}\geq\cdots\geq 1\) and with sum \(n\). The parts may be seen as the block sizes of a set partition \(\Pi_n\) of \([n]=\{1,\dots, n\}\), all \(\Pi_n\) for \(\pi_n\) being equally likely. Let \(\Pi_m\), \(1\leq m\leq n\), be the restriction of \(\Pi_n\) to \([m]\) and \(\rho_m\) the ranked sequence of block sizes of \(\Pi_m\). Then \(\rho_m\) is said to be derived from \(\pi_n\) by random sampling. It is required that the sequence \(\pi_n\) is sampling consistent, i.e. \(\pi_m\) is distributed as \(\rho_m\), \(m\leq n\). A stochastic part \(X_n\) is deleted from \(\pi_n\), so that \(P(\pi_n=\lambda,X_n=x)= p(\lambda)d (\lambda, x)\), where \(p(\lambda)=P(\pi_n=\lambda)\), \(\lambda\) partition of \(n\), the index \(n\) being omitted, and the deletion kernel \(d(\lambda,x)\) satisfying \(\sum d(\lambda,x)= 1\) with \(\sum\) over all parts \(x\) of \(\lambda\). The structure is regenerative w.r.t. \(d(\lambda,x)\) when \(P(\pi_n=\lambda,X_n=x)=P(X_n=x)P(\pi_{n-x}=\lambda-\{x\})\), i.e. \[ p(\lambda)d(\lambda,x)= q(n,x)p(\lambda-\{x\}) \tag{*} \] where \(\lambda -\{x\}\) is the partition \(\lambda\) with part \(x\) deleted and \(q(n,x)= P(X_n=x)\). The \(q(n,x)\) may be chosen as any distribution on \([n]\) and then \(p\) is unique from (*) but not always \(d\) since we may have \(p (\lambda)=0\). When \(\pi_n\) is regenerative, so the partitions derived by random sampling are. A unique way given the \(q(n,x)\) of defining a sequence \(X_{n1},X_{n2},\dots\) by successive deletion of parts of \(\pi_n\) is constructed. This sequence is a stochastic composition (i.e., ordered partition) of \(n\). It is regenerative when \(\pi_n\) is. So the theory of regenerative partitions is reduced to the theory of regenerative compositions, which was presented rather completely by the authors [Ann. Probab. 33, No. 2, 445--479 (2005; Zbl 1070.60034)]; see also \textit{A. V. Gnedin} [ibid. 25, No. 3, 1437--1450 (1997; Zbl 0895.60037)]. Example: \(d(\lambda,x)=a(\lambda,x)/n\) where \(a (\lambda,x)\) is the number of parts \(x\) in \(\lambda\). The partition structures regenerative w.r.t. this \(d\) are characterized. A fragmented permutation of \([n]\) is a pair \((\sigma, \lambda)\) with \(\sigma\) a permutation of \([n]\) and \(\lambda\) a composition of \(n\) to be interpreted as an ordered sequence of boxes dividing the permutation. A Markov chain on the set of fragmented permutations is defined as follows. Let \(X_n\) be a random variable with values in \([n]\). Given \(X_n=x\) pick a sequence of \(x\) different elements of the permutation, remove these from the above boxes and put them into a new box to the left of the remaining boxes. This chain has a unique invariant distribution uniform on the permutation part and as \(X_{n1}, X_{n2},\dots\) in the above construction for the composition part, these parts being independent. The construction of random compositions by random points in the complement of a closed random set, and with singletons in that set, as in the above references, is discussed.