Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
CALIBRATING THE CLOCK: USING STOCHASTIC PROCESSES TO MEASURE THE RATE OF EVOLUTION 139 (5.27) so that indeed Cb and Zb can be coupled closely if (and, it turns out, only if) b = o(n). Combinatorial Assemblies The spirit of the approximations in the preceding subsectionâreplacing a dependent process with an independent oneâcarries over to other combinatorial structures. The first of these is the class of assemblies. Assemblies are labeled structures built as follows. The set {1,2,. . .,n} is partitioned into ak subsets of size k, for k = 1,2,. . .,n, and each subset of size k is marked as one of mk indecomposable components of size k. For example, in the case of permutations, mk = (k â 1)!, and the components of size k are the cycles on k elements. The number of structures N(a) of weight n having ai components of size i, i = 1,2,. . .,n, is therefore given by (5.28) and the total numberp(n) of structures of weight n is given by (5.29) A random structure of weight n is obtained by choosing one of the p(n) possibilities with equal probability. If Cj â Cj(n) denotes the number of components of size j, then (5.30)
CALIBRATING THE CLOCK: USING STOCHASTIC PROCESSES TO MEASURE THE RATE OF EVOLUTION 140 In the case of permutations, this reduces to (5.22), because then mj / j! = 1 / j. Note that for any x > 0, the probability above is proportional to so that by comparison with (5.22) we see that (C1, C2,. . ., Cn) = (Zl,Z2,. . .,Zn| T = n), where the Zi are independent Poisson random variables with means In particular this implies that where Rb = â1â¤iâ¤b iZi. This observation reduces the calculation of a total variation distance between two processes to the calculation of a total variation distance between two random variables. We focus our attention on the class of assemblies that satisfies the logarithmic condition (5.31) for some κ,y > 0. Among these are random permutations (for which (5.31) holds identically in i with κ = y = 1), and random mappings of [n] to itself, for which . The study of random mappings has a long and venerable history in the combinatorics literature and is reviewed in Mutafciev (1984), Kolchin (1986), and Flajolet and Odlyzko (1990), for example.
CALIBRATING THE CLOCK: USING STOCHASTIC PROCESSES TO MEASURE THE RATE OF EVOLUTION 141 For the logarithmic class we may choose x = yâ1, and then it is known (under an additional mild rate of convergence assumption in (5.31)) that (5.32) just as for the ESF. But more detailed information is available. For example, Arratia et al. (1994b) show that for fixed b, (5.33) The term |κ â 1| reflects the similarity of the structure to an ESF with parameter κ, whereas the term E[|Rb â E [Rb]|] reflects the local behavior of the structure. The θ-biased structures, those with probability proportional to q to the number of components, can also be studied in this way. In particular (5.30) holds, the Poisson-distributed Z, now having mean The accuracy of the approximation of Cb by Zb for the logarithmic class is still measured by (5.32) and (5.33), with κ replaced by θκ. A rather weak consequence of the bounds typified by (5.32) and (5.33) is the fact that for each fixed b, (C1 (n),C2(n),. . .,Cb(n)) (Z1 ,Z2,. . .,Zb), meaning that the component counting process C converges in distribution (in Râ ) to the independent process Z. For each n, we are comparing the combinatorial process to a single limiting process. This recovers the classical result of Goncharov (1944) showing that the cycle counts of a random permutation are asymptotically independent Poisson random variables with means 1/i. The analog for random mappings is due to Kolchin (1976).
