Recursive partition structures (Q874733): Difference between revisions

This paper is a step in a line of research flourishing in recent years. Let \(P= (P_1,P_2,\dots)\) be a random discrete distribution. So the \(P_j\) are nonnegative random variables with sum unity. It is also called a paintbox: conditionally, given \(P\), the balls in an infinite set \(B\) are painted i.i.d. with color \(i\) with probability \(P_i\). This defines a random partition of \(B\), the blocks be the sets of balls painted the same color. Let \(K_{nr}\), \(r\geq 1\), being the number of colors represented \(r\) times on the first \(n\) balls and \(K_n= \sum_r K_{nr}\) the number of colors on these balls. One may construct \(P\) by a stick-breaking model: Let \(W_1,W_2,\dots\) be i.i.d. random variables with values in \([0,1)\). Take \(P_1= 1-W_1\), \(P_2= (1- W_2) W_1\), \(P_3= (1-W_3) W_1W_2\), etc., i.e., we divide \([0,1]\) into intervals \(1-W\), and \(W_1\), then \(W_1\) into \((1-W_2)W_1\) and \(W_2W_1\), etc. This model is generalized here to division into more than two parts. Let \(X= (X_1,X_2,\dots)\) and \(Y= (Y_1,Y_2,\dots)\) be two sequences of random variables with \(\sum_i X_i+ \sum_j Y_j= 1\). The first step divides \([0,1]\) into intervals \(\xi_1,\xi_2,\dots\) called crumbs and \(\eta_1,\eta_2,\dots\) called solids. Their joint law is the same as of \((X,Y)\). The solids are not divided any further and are taken as elements of \(P\). Each crumb is divided into new crumbs and solids by the same (relative) law as \((X,Y)\), independent of other crumbs and of history. This procedure is repeated. It is assumed that \(E\sum_i X_i< 1\) so that the total size of solids over all generations is unity and that \(E\# \{i: X_i> 0\}> 1\) so that the branching process of crumbs is supercritical. Put \(\psi(\alpha)= E\sum_i X^\alpha_i\), \(\varphi(\alpha)= E\sum_j Y^\alpha_j\). It is assumed that the equation \(\psi(\alpha)= 1\) has a solution \(\alpha_*\), unique in \(\{\alpha: \text{Re\,}\alpha> \alpha_*-\varepsilon\}\) and that \(\varphi(\alpha_*-\varepsilon)< \infty\) (Malthusian hypothesis). Then the intrinsic martingale \(M_k= \sum \xi^{\alpha_*}\), with sum over all crumbs \(\xi\) in the first \(k\) generations, has an a.s. limit \(M\) as \(k\to\infty\). It is shown that \(K_n\sim bn^{\alpha_*}M\) and \(K_{nr}\sim c_r n^{\alpha_*}M\), a.s. as \(n\to\infty\). It is also shown that limit and expectation may be interchanged here. A recurrence for the moments of \(M\) is derived. More specific results are obtained for certain tripartite splittings of \([0,1]\) and for a splitting into one solid and \(d+1\) crumbs, \(d\geq 1\), where \(X_1,\dots, X_{d+1}\), \(Y_1\) have a Dirichlet distribution.