Normal convergence problem? Two moments and a recurrence may be the clues

DOI10.1214/AOAP/1029962872MaRDI QIDQ1578596zbMATH OpenOpenAlexFDO

Authors Boris Pittel

Publication date 4 September 2000

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1214/aoap/1029962872

zbMATH Keywords

independence numbernumber of linear extensionsbranching (Galton-Watson) processescoefficients of generating functionsnormal convergencenumber of vertices of degreerandom labelled rooted trees

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Graph theory (05C99)

Recommendations

• Pattern distribution in various types of random trees
• Nodes of large degree in random trees and forests
• The Distribution of Patterns in Random Trees
• The distribution of nodes of given degree in random trees

Cites work

• scientific article; zbMATH DE number 3152798 (Why is no real title available?)
• scientific article; zbMATH DE number 3569817 (Why is no real title available?)
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• scientific article; zbMATH DE number 852055 (Why is no real title available?)
• scientific article; zbMATH DE number 3415878 (Why is no real title available?)
• A Note on the Theory of Moment Generating Functions
• A Recurrence Related to Trees
• An urn model for cannibal behavior
• Analysis of the space of search trees under the random insertion algorithm
• Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees
• Limit laws for local counters in random binary search trees
• Linear extensions of a random partial order
• On a likely shape of the random Ferrers diagram
• On maximal independent sets of nodes in trees
• On some problems of the statistical theory of partitions with application to characters of the symmetric group. III
• On the Expected Performance of Path Compression Algorithms
• On the log-product of the subtree-sizes of random trees
• On tree census and the giant component in sparse random graphs
• Packing and Covering Constants for Certain Families of Trees. II
• Packing and covering constants for certain families of trees. I
• The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Genera
• The average performance of the greedy matching algorithm
• The expected linearity of a simple equivalence algorithm
• The standard additive coalescent

Cited in

(20)

• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs
• Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates
• Asymptotic distribution of two-protected nodes in random binary search trees
• Sorting 1-away permutations with underlying Fibonacci convolutions
• Conditioned Galton-Watson trees: the shape functional, and more on the sum of powers of subtree sizes and its mean
• Critical beta-splitting, via contraction
• The critical beta-splitting random tree. I: Heights and related results
• Analysis of three graph parameters for random trees
• Independent sets of random trees and sparse random graphs
• On the asymptotic normality in the problem on the tuples repetitions in a marked complete tree
• A general limit theorem for recursive algorithms and combinatorial structures
• On the independent set sequence of a tree
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• A class of polynomial recurrences resulting in (\(n/\log n, n/\log^2n\))-asymptotic normality
• On the distribution of the number of Young tableaux for a uniformly random diagram
• Convergence rate for the number of crossings in a random labelled tree
• Phase changes in random m-ary search trees and generalized quicksort
• Singularity analysis, Hadamard products, and tree recurrences
• The sum of powers of subtree sizes for conditioned Galton-Watson trees
• Limit laws for the Randić index of random binary tree models

This page was built for publication: Normal convergence problem? Two moments and a recurrence may be the clues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1578596)