Random set partitions: Asymptotics of subset counts

[摘要] We study the asymptotics of subset counts for the uniformly random partition of the set [n]. It is known that typically most of the subsets of the random partition are of size r, with re(r) = n. Confirming a conjecture formulated by Arratia and Tavare, we prove that the counts of other subsets are close, in terms of the total variation distance, to the corresponding segments of a sequence {Z(J)} of independent, Poisson (r(i)/j!) distributed random variables. DeLaurentis and Pittel had proved that the finite-dimensional distributions of a continuous time process that counts the typical size subsets converge to those of the Brownian Bridge process. Combining the two results allows to prove a functional limit theorem which covers a broad class of the integral functionals. Among illustrations, we prove that the total number of refinements of a random partition is asymptotically lognormal. (C) 1997 Academic Press.

[发布日期] 1997-08-01