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

DOI10.1214/AOAP/1029962872zbMATH Open0960.60014OpenAlexW2063369100MaRDI QIDQ1578596FDOQ1578596

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

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

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)

Cites Work

• 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: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation.
• Title not available (Why is that?)
• Limit laws for local counters in random binary search trees
• Title not available (Why is that?)
• A Recurrence Related to Trees
• A Note on the Theory of Moment Generating Functions
• The standard additive coalescent
• Title not available (Why is that?)
• On a likely shape of the random Ferrers diagram
• Linear extensions of a random partial order
• The average performance of the greedy matching algorithm
• On maximal independent sets of nodes in trees
• The expected linearity of a simple equivalence algorithm
• Title not available (Why is that?)
• An urn model for cannibal behavior
• Analysis of the space of search trees under the random insertion algorithm
• 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. I
• Packing and Covering Constants for Certain Families of Trees. II
• On some problems of the statistical theory of partitions with application to characters of the symmetric group. III
• Title not available (Why is that?)
• On the Expected Performance of Path Compression Algorithms
• Gibbs' Measures on Combinatorial Objects and the Central Limit Theorem for an Exponential Family of Random Trees

Cited In (14)

• 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
• Conditioned Galton-Watson trees: the shape functional, and more on the sum of powers of subtree sizes and its mean
• Analysis of three graph parameters for random trees
• 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
• 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)