Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-22T15:09:46.852Z Has data issue: false hasContentIssue false
  • English
  • Français

Functionals of random mappings: exact and asymptotic results

Published online by Cambridge University Press:  01 July 2016

P. J. Donnelly ,
W. J. Ewens  and
S. Padmadisastra
P. J. Donnelly*
Affiliation:
Queen Mary and Westfield College, London
W. J. Ewens*
Affiliation:
Monash University
S. Padmadisastra*
Affiliation:
Monash University
*
∗Postal address: School of Mathematical Sciences, Queen Mary and Westfield College, Mile End Road, London El 4NS, UK.
∗∗Postal address: Department of Mathematics, Monash University, Clayton, VIC 3168, Australia.
∗∗Postal address: Department of Mathematics, Monash University, Clayton, VIC 3168, Australia.
Get access Rights & Permissions [Opens in a new window]

Abstract

A random mapping partitions the set {1, 2, ···, m} into components, where i and j are in the same component if some functional iterate of i equals some functional iterate of j. We consider various functionals of these partitions and of samples from it, including the number of components of ‘small' size and of size O(m) as m → ∞the size of the largest component, the number of components, and various symmetric functionals of the normalized component sizes. In many cases exact results, while available, are uniformative, and we consider various approximations. Numerical and simulation results are also presented. A central tool for many calculations is the ‘frequency spectrum', both exact and asymptotic.

Keywords

FREQUENCY SPECTRUMSIZE-BIASED DISTRIBUTIONGEM DISTRIBUTION
Type
Research Article
Information
Advances in Applied Probability , Volume 23 , Issue 3 , September 1991 , pp. 437 - 455
Copyright
Copyright © Applied Probability Trust 1991 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aldous, D. J. (1985) Exchangeability and related topics, in Lecture Notes in Mathematics 1117, ed. Dold, A. and Eckmann, B., pp. 1–198. Springer-Verlag, Berlin.Google Scholar
Donnelly, P. J. and Joyce, P. (1989) Continuity and weak convergence of ranked and size-biased permutations on the infinite simplex. Stoch. Proc. Appl. 31, 89–103.Google Scholar
Donnelly, P. J. and Tavaré, S. (1986) The ages of alleles and a coalescent. Adv. Appl. Prob. 18, 1–19.CrossRefGoogle Scholar
Donnelly, P. J. and Tavaré, S. (1991) The biology of random permutations: the Poisson–Dirichlet and the GEM distributions in applied probability. (In preparation.) Google Scholar
Ewens, W. J. (1972) The sampling theory of selectively neutral alleles. Theoret. Pop. Biol. 3, 87–112.CrossRefGoogle ScholarPubMed
Feller, W. (1966) An Introduction to Probability Theory and its Applications , Vol. II. Wiley, New York.Google Scholar
Frank, H. and Frisch, I. T. (1971) Communication, Transmission and Transportation Networks . Addison-Wesley, Reading, Mass.Google Scholar
Gertsbakh, I. B. (1977) Epidemic processes on a random graph: some preliminary results. J. Appl. Prob. 14, 427–438.Google Scholar
Hansen, J. (1990) Functional limit theorems for random labelled combinatorial structures. (Submitted).Google Scholar
Harris, B. (1960) Probability distributions related to random mappings. Ann. Math. Statist. 31, 1045–1062.Google Scholar
Katz, L. (1955) Probability of indecomposability of a random mapping function. Ann. Math. Statist. 26, 512–517.CrossRefGoogle Scholar
Kelly, F. (1977) Exact results for the Moran neutral allele model. J. Appl. Prob. 9, 197–201.Google Scholar
Kingman, J. F. C. (1975) Random discrete distributions. J. R. Statist. Soc. 37, 1–22.Google Scholar
Kingman, J. F. C. (1977) The population structure associated with the Ewens sampling formula. Theoret. Popn Biol. 11, 274–284.CrossRefGoogle ScholarPubMed
Kingman, J. F. C. (1978) Random partitions in population genetics. Proc. R. Soc. A 361, 1–20.Google Scholar
Knuth, D. E. (1981) The Art of Computer Programming , Vol. 2. Addison-Wesley, Reading, Mass. Google Scholar
Kolchin, V. F. (1976) A problem of the allocation of particles into cells and random mappings. Theory Prob. Appl. 21, 48–63.CrossRefGoogle Scholar
Kupka, J. G. (1990) The distribution and moments of the number of components of a random mapping function. J. Appl. Prob. 27, 202–207.Google Scholar
Ore, O. (1977) Graphs and their Uses. Math. Assoc. Amer., Yale University Press, New Haven.Google Scholar
Ross, S. M. (1981) A random graph. J. Appl. Prob. 18, 309–315.Google Scholar
Watterson, G. A. (1976) The stationary distributions of the infinitely-many neutral alleles diffusion model. J. Appl. Prob. 13, 639–651.CrossRefGoogle Scholar
Watterson, G. A. and Guess, H. A. (1977) Is the most frequent allele the oldest? Theoret. Popn Biol. 11, 141–160.Google Scholar