Calculating the Secrets of Life: Contributions of the Mathematical Sciences to Molecular Biology (1995)
Chapter: Other Combinatorial Structures
Page 142
There are many uses to which such total variation estimates can be put. In essence, functionals of the dependent process that depend mainly on the small component counts (that is, on components of size o(n)) are well approximated by the corresponding functionals of the independent process, which are often much easier to analyze. A typical example shows that the total number of components in such a structure asymptotically has a normal distribution, with mean and variance qk log n . A corresponding functional central limit theorem follows by precisely the same methods. In addition, these estimates lead to bounds on the distances between the laws of such functionals. Some examples that illustrate the power of this approach can be found in Arratia and Tavaré (1992) and Arratia et al. (1993).
Other Combinatorial Structures
The strategy employed for assemblies also works for other combinatorial structures, including multisets and selections. We focus just on the multiset case. To build such structures, which are now unlabeled, imagine a supply of mj types of irreducible component of weight j, and build an object of total weight n by choosing components with replacement. The number N(a) of structures of weight n having aj components of size j = 1,2,. . .,n is
(5.34)
and the total number of structures of weight n is p(n) = SaN(a). A random multiset of size n has aj components of size j with probability
(5.35)
The ingredient common to assemblies and multisets is the fact that
Page 143
but the approximating independent random variables {Zi} are no longer Poisson, but rather negative binomial with parameters mi and xi:
(5.36)
valid for 0 < x < 1. In the q-biased case, the Zi are negative binomial with parameters mi and qxi, for any q < x-1.
The most studied example in this setting concerns the factorization of a random monic polynomial over the finite field GF(q) with q elements. The components of size i are precisely the irreducible factors of degree i, there being
of them. The function m(·) is the Möbius function: m(k) = -l or 1 according to whether k is the product of an odd or even number of distinct prime factors, and m(k) = 0 if k is divisible by the square of a prime. The logarithmic condition
(5.37)
is satisfied by random polynomials with k = 1 and y = q. For this logarithmic class the total variation estimates (5.32) and (5.33) apply once more (with appropriate modification for the q-biased case), and the techniques described at the end of the previous section can then be used to study the behavior of many interesting functionals. In particular, examples describing the functional central limit theorem, with error estimates, for the random polynomial case, can be found in Arratia et al. (1993).
