Premium
Limit Theorems for Combinatorial Structures via Discrete Process Approximations
Author(s) -
Arratia Richard,
Tavaré Simon
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030310
Subject(s) - mathematics , random permutation , permutation (music) , limit (mathematics) , central limit theorem , generalization , combinatorics , discrete mathematics , mathematical analysis , symmetric group , statistics , physics , acoustics
Discrete functional limit theorems, which give independent process approximations for the joint distribution of the component structure of combinatorial objects such as permutations and mappings, have recently become available. In this article, we demonstrate the power of these theorems to provide elementary proofs of a variety of new and old limit theorems, including results previously proved by complicated analytical methods. Among the examples we treat are Brownian motion limit theorems for the cycle counts of a random permutation or the component counts of a random mapping, a Poisson limit law for the core of a random mapping, a generalization of the Erdös–Turán Law for the log‐order of a random permutation and the smallest component size of a random permutation, approximations to the joint laws of the smallest cycle sizes of a random mapping, and a limit distribution for the difference between the total number of cycles and the number of distinct cycle sizes in a random permutation.