Logarithmic combinatorial structures: A probabilistic approach
This research monograph is concerned with precise approximations to the process of component counts in random decomposable combinatorial structures by simpler discrete, independent processes. The authors develop powerful methods for pushing most of the results (as well as the conditions required) to their limit. The arguments used are completely probabilistic (unlike some of the authors' previous papers), and indeed the book may be roughly summarized as a deep study of component counts in decomposable combinatorial structures without generating function, without Fourier analysis, and with purely probabilistic reasoning. A prototype of the so-called ``logarithmic combinatorial structures is cycles in permutations. Permutations can be viewed as a set of cycles, whose exponential generating function is of the form \(\log(1/(1-z))\) (since there are \((n-1)!\) different ways of arranging \(n\) distinct numbers in a cycle), thus the term ``logarithmic. The authors' view of the cycle structures is through the fine, informative counting process \((C_1(n), C_2(n), \dots)\), where \(C_i(n)\) denotes the number of cycles of size \(i\) in a random permutation of \(n\) elements. The basic idea is that if we have good knowledge on such processes, then many other properties like the distribution of the total number of cycles and functional limit theorems can be derived. Two typical types of limit theorems are as follows. (i) \((C_1(n), C_2(n), \dots)\) converges in distribution to \((\text{Po}(1), \text{Po}(\frac 12), \dots)\) in \(\mathbb{Z}_+^\infty\), where \(\text{Po}(\frac1i)\) denotes a Poisson random variable with mean \(1/i\), and, (ii) for the size of the \(k\)th largest cycle \(L_k(n)\), \(n^{-1} (L_1(n), L_2(n), \dots)\) converges in distribution to \((L_1, L_2, \dots)\) in \([0,1]^\infty\), where the random vector \((L_1, L_2,\dots)\) has a Poisson-Dirichlet distribution with parameter \(1\). These results roughly say that counts of small cycles are asymptotically independent, while those of large cycles are strongly dependent. In this book such results are (i) extended to cover a wider class of combinatorial structures, and (ii) refined by stronger types of approximation theorems with different degrees of precision on error rate. For a general treatment of the component counts, the following two conditions are crucial: (i) the conditioning relation \[ \mathcal{L}(C_1^{(n)}, \dots,C_n^{(n)}) = \mathcal{L}(Z_1,\dots,Z_n \mid Z_1+2Z_2+\cdots + nZ_n =n), \] and (ii) the logarithmic condition \[ \mathbb{P}(Z_n=1) \sim \mathbb{E}(Z_n) \sim \theta/n \qquad (\theta>0). \] Here \(C_j^{(n)}\) denotes the number of components of size \(j\) and the \(Z_j\)'s are some discrete random variables, which are usually Poisson, binomial or negative binomial. From a combinatorial point of view, the conditioning relation corresponds roughly to decomposability of the underlying structure and the logarithmic condition reflects analytic properties needed on the generating functions. For the types of approximation theorems, the authors study mostly the total variation distances \(d_{\text{TV}}(\mathcal{L}(C_1^{(n)}, \dots,C_b^{(n)}), \mathcal{L}(Z_1,\dots,Z_b))\) and \( d_{\text{TV}}(\mathcal{L}(C_{b+1}^{(n)}, \dots,C_n^{(n)}), \mathcal{L}(C_{b+1}^{*(n)},\dots,C_n^{*(n)}))\), where \(d_{\text{TV}}\) denotes the total variation distance and \(C_j^{*(n)}\) denotes the numbers of cycles of lengths \(j\), in a \(\theta\)-biased random permutation of \(n\) objects (whose joint distribution follows the Ewens sampling formula). Once good bounds are available for these distances, properties for the approximators can be transferred to those of the component counts. Thus two chapters (4 and 5) are devoted to derive all types of properties needed for the Ewens sampling formula, which include local and functional limit theorems and large deviations for the number of cycles, distributions of the lengths of small cycles, ordered cycle lengths, and largest cycles, and the Erdős-Turán law for log order of a random element. The diversity of the types of results implied by the authors' strong approximation theorems shows the advantages of the authors' consideration of the more general total variation distances. A large amount of fine estimates are derived in order to achieve the generality of the condition and the precision for the total variation distances. The first half of the book (first six chapters) describes the background, the main types of results discussed in the book, properties needed for the Ewens sampling formula (which is used later on as a basic approximator), as well as the methods of proof used. Chapter 7 describes the main theorems of the book under general conditions whose consequences are discussed in Chapter 8; the proofs are then given in Chapters 9 to 14 (pp.\ 225 -- 338). The contents of each chapter are sketched as follows. Chapter 1 starts from a discussion of properties of cycles in permutations: joint distribution and moments of cycle counts (Cauchy's formula), marginal distribution, total variation distance between the cycle counts and Poisson process, the Feller coupling, local and functional limit theorems for total number of cycles, distributions of the small and large cycles, age-ordered list of cycle lengths, and the Erdős-Turán law. Then the asymptotic analogy between cycles in permutations and prime factors in random integers are highlighted (theory in one side is generally inspiring for that in the other). Chapter 2 describes decomposable combinatorial structures, aiming mainly at assemblies (set construction for labelled structures), multisets and selections (set construction for unlabelled structures), and their variations by refining, coloring and tilting, the viewpoint being consistently probabilistic. Examples include integer partitions, set partitions, polynomials over finite fields, binary search trees, additive arithmetic semigroups, coagulation fragmentation processes, etc. Chapter 3 gives an overview of the main results in the book, beginning with the conditioning relation and logarithmic condition. A section on total variation and Wasserstein distances and another on Stein's method are included. Chapters 4 and 5 give a detailed discussion of the Ewens sampling formula. The notion of size-biasing is first introduced. Chapter 4 then focusses on distributional properties of the random variables \(n^{-1} \sum_{b<j\leq n} jZ_j\), where \(\mathcal{L}(Z_j) =\mathcal{L}(\text{Po}(1/j))\), \(0\leq b<n\). The main reason of studying such partial sums is that the total variation distance between two random vectors are reduced to some weighted sum of two random variables (one-dimensional) of such a type. Chapter 5 then deals with the more general process approximations. Chapter 6 turns to general logarithmic combinatorial structures and follows the same pattern of treatment for Ewens sampling formula by considering first distributions of \(n^{-1}\sum_{b<j\leq n}jC_j^{(n)}\) and then the associated process approximations. It derives, in particular, asymptotics of the total variation distance between the process of component counts in assembly, multiset and selection constructions and the associated limiting process. From Chapter 7 on, the treatment is for more general (not only for assembly, multiset and selection) logarithmic structures but under stronger analytic assumptions in order to prove more effective bounds on the total variation distances. ``Chapter 8 gives a number of consequences of the approximation theorems of the preceding chapter, illustrating the power inherent in discrete functional limit theorems and approximations. Each is based on earlier limiting results, improving upon them in two ways. First, the context is broadened from an often quite restrictive setting to that of a very general logarithmic combinatorial structure. Secondly, the limit theorems are supplied with error bounds. This book, whose title was already cited in the paper by \textit{R. Arratia} and \textit{S. Tavaré} [Adv. Math. 104, 90--154 (1994; Zbl 0802.60008)], represents the culmination of a decade-long research by the authors. It is very well-written and informative. Highly recommended.
- The number of components in a logarithmic combinatorial structure.
- The cycle structure of random permutations
- Limits of logarithmic combinatorial structures.
- Explicit Limits of Total Variation Distance in Approximations of Random Logarithmic Assemblies by Related Poisson Processes
- Limit Theorems for Combinatorial Structures via Discrete Process Approximations
- An analytic method in probabilistic combinatorics
- Veneziano amplitudes, spin chains and abelian reduction of QCD
- Asymptotic value distribution of additive functions defined on the symmetric group
- A functional limit theorem on powers of random permutations
- A logical approach to asymptotic combinatorics I. First order properties
- The cycle structure of random permutations
- Independent process approximations for random combinatorial structures
- On rational structures and their asymptotics
- The collision spectrum of \(\Lambda\)-coalescents
- Ordered and size-biased frequencies in GEM and Gibbs' models for species sampling
- Genealogical properties of subsamples in highly fecund populations
- Local probabilities and total variation distance for random permutations
- When do combinatorial structures obey the Poisson-Dirichlet law?
- Sampling and learning Mallows and generalized Mallows models under the Cayley distance
- Singularity analysis for heavy-tailed random variables
- Monotonous subsequences and the descent process of invariant random permutations
- On the number of eigenvalues of modified permutation matrices in mesoscopic intervals
- Limit theorems for the logarithm of the order of a random \(A\)-mapping
- On the strange domain of attraction to generalized Dickman distributions for sums of independent random variables
- Size bias for one and all
- Random combinatorial structures: the convergent case
- The ubiquitous Ewens sampling formula
- Limits of logarithmic combinatorial structures.
- The Poisson-Dirichlet law is the unique invariant distribution for uniform split-merge transfor\-mations.
- The number of components in a logarithmic combinatorial structure.
- Conditional large and moderate deviations for sums of discrete random variables. Combinatoric applications
- Random permutation matrices under the generalized Ewens measure
- Marginals of multivariate Gibbs distributions with applications in Bayesian species sampling
- Weighted dependency graphs
- Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm
- Size distribution of the largest component of a random \(a\)-mapping
- Precise asymptotics of longest cycles in random permutations without macroscopic cycles
- Central limit theorem for the least common multiple of a uniformly sampled \(m\)-tuple of integers
- On the dependence of the component counting process of a uniform random variable
- Distance between natural numbers based on their prime signature
- Asymptotic behavior of the number of distinct values in a sample from the geometric stick-breaking process
- The characteristic polynomial of a random matrix
- The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees
- Broadcasting on random recursive trees
- One-dimensional cellular automata with random rules: longest temporal period of a periodic solution
- Moment characteristics of a random mapping with restrictions on component sizes
- The method of cumulants for the normal approximation
- The component counts of random functions
- The Feller coupling for random derangements
- Statistical enumeration of groups by double cosets
- Large genus asymptotic geometry of random square-tiled surfaces and of random multicurves
- A penalised model reproducing the mod-Poisson fluctuations in the Sathé-Selberg theorem
- Fifty years of theoretical population biology
- Developments in coalescent theory from single loci to chromosomes
- Limits of random tree-like discrete structures
- Split-and-merge in stationary random stirring on lattice torus
- How long is the convex minorant of a one-dimensional random walk?
- Convergence to scale-invariant Poisson processes and applications in Dickman approximation
- A product of invariant random permutations has the same small cycle structure as uniform
- Efficient generation of random derangements with the expected distribution of cycle lengths
- Limiting distributions of generalised Poisson-Dirichlet distributions based on negative binomial processes
- The component counts of random injections
- Hierarchical species sampling models
- Random permutations with logarithmic cycle weights
- Size biased sampling from the Dickman subordinator
- A sharp inequality for the variance with respect to the Ewens sampling formula
- The minimal observable clade size of exchangeable coalescents
- Rényi 100, quantitative and qualitative (in)dependence
- Stein's method for the Poisson-Dirichlet distribution and the Ewens sampling formula, with applications to Wright-Fisher models
- Asymptotic statistics of cycles in surrogate-spatial permutations
- The Dickman subordinator, renewal theorems, and disordered systems
- Malliavin and Dirichlet structures for independent random variables
- On the least common multiple of several random integers
- Dickman approximation in simulation, summations and perpetuities
- Looking-backward probabilities for Gibbs-type exchangeable random partitions
- On fluctuations of eigenvalues of random permutation matrices
- On the number of components of fixed size in a random \(A\)-mapping
- Central limit theorem for random partitions under the Plancherel measure
- Extreme sizes in Gibbs-type exchangeable random partitions
- Probabilistic divide-and-conquer: deterministic second half
- Distributions of linear functionals of two parameter Poisson-Dirichlet random measures
- Lattice permutations and Poisson-Dirichlet distribution of cycle lengths
- The characteristic polynomial of a random permutation matrix at different points
- A conjugate class of random probability measures based on tilting and with its posterior analysis
- Permanental partition models and Markovian Gibbs structures
- Beta-coalescents and continuous stable random trees
- The Poisson distribution for linear statistics of random permutations
- The law of iterated logarithm for logarithmic combinatorial assemblies
- The Strassen law of iterated logarithm for combinatorial assemblies
- Ewens' sampling formula and related formulae: combinatorial proofs, extensions to variable population size and applications to ages of alleles
- The hyperbolic geometry of random transpositions
- Asymptotic laws for compositions derived from transformed subordinators
- Asymptotic laws for regenerative compositions: gamma subordinators and the like
- Regenerative compositions in the case of slow variation
- An isoperimetric inequality for conjugation-invariant sets in the symmetric group
- Central limit theorem for multiplicative class functions on the symmetric group
- Mod-\(\phi\) convergence: approximation of discrete measures and harmonic analysis on the torus
- Random permutations without macroscopic cycles
- On smooth mesoscopic linear statistics of the eigenvalues of random permutation matrices
- Fisher's measure of variability in repeated samples
- Bin sizes in time-inhomogeneous infinite Polya processes
- Local probabilities for random permutations without long cycles
- Euler's constant: Euler's work and modern developments
- Approximate sampling formulae for general finite-alleles models of mutation
- The scaling window for a random graph with a given degree sequence
This page was built for publication: Logarithmic combinatorial structures: A probabilistic approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422444)
