A general limit theorem for recursive algorithms and combinatorial structures

DOI10.1214/aoap/1075828056zbMath1041.60024OpenAlexW2042464140MaRDI QIDQ1431560

Ralph Neininger, Ludger Rüschendorf

Publication date: 10 June 2004

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

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

zbMATH Keywords

contraction methodrecursive structuredivide-and-conquer algorithmmultivariate limit lawZolotarev metric

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Searching and sorting (68P10) (L^p)-limit theorems (60F25)

Related Items (66)

Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs ⋮ Implicit Renewal Theory and Power Tails on Trees ⋮ On the contraction method with degenerate limit equation. ⋮ The fixed points of the multivariate smoothing transform ⋮ The Weighted Branching Process ⋮ Distances in random digital search trees ⋮ Information-theoretic thresholds from the cavity method ⋮ The left-right-imbalance of binary search trees ⋮ Directional differentiability for supremum-type functionals: statistical applications ⋮ Higher moments of Banach space valued random variables ⋮ A limit process for partial match queries in random quadtrees and 2-d trees ⋮ On the size of paged recursive trees ⋮ Node profiles of symmetric digital search trees: Concentration properties ⋮ A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries ⋮ Smoothing equations for large Pólya urns ⋮ Asymptotic normality for the size of graph tries built from M-ary tree labelings ⋮ DEGREE PROFILE OF HIERARCHICAL LATTICE NETWORKS ⋮ Central limit theorem in uniform metrics for generalized Kac equations ⋮ Tail behavior of solutions of linear recursions on trees ⋮ Multi-dimensional smoothing transformations: existence, regularity and stability of fixed points ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ Implicit renewal theorem for trees with general weights ⋮ Process convergence for the complexity of radix selection on Markov sources ⋮ Heavy tailed solutions of multivariate smoothing transforms ⋮ On densities for solutions to stochastic fixed point equations ⋮ Refined asymptotics for the composition of cyclic urns ⋮ Maximums on trees ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ On the Variety of Shapes on the Fringe of a Random Recursive Tree ⋮ The size of random fragmentation trees ⋮ Random environment on coloured trees ⋮ Asymptotic Properties of a Leader Election Algorithm ⋮ A functional limit theorem for the profile of search trees ⋮ Perpetuities in Fair Leader Election Algorithms ⋮ The total path length of split trees ⋮ Asymptotic Analysis of Hoppe Trees ⋮ Limiting theorems for the nodes in binary search trees ⋮ Distributional analysis of swaps in quick select ⋮ Dependence and phase changes in random m‐ary search trees ⋮ Linear stochastic equations in the critical case ⋮ On the Subtree Size Profile of Binary Search trees ⋮ On stochastic recursive equations of sum and max type ⋮ A limit field for orthogonal range searches in two-dimensional random point search trees ⋮ From coin tossing to rock-paper-scissors and beyond: a log-exp gap theorem for selecting a leader ⋮ Limit theorems for random spatial drainage networks ⋮ Asymptotic joint normality of counts of uncorrelated motifs in recursive trees ⋮ Departure from normality of increasing-dimension martingales ⋮ Combinatorial Analysis of Growth Models for Series-Parallel Networks ⋮ Limit laws for the Randić index of random binary tree models ⋮ Asymptotic theory for the multidimensional random on-line nearest-neighbour graph ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ On the total length of the random minimal directed spanning tree ⋮ Refined quicksort asymptotics ⋮ Stochastic fixed-point equations ⋮ Partial match queries in random quadtrees ⋮ Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees ⋮ Limit distribution of distances in biased random tries ⋮ Random additions in urns of integers ⋮ The Wiener Index of Random Digital Trees ⋮ The dual tree of a recursive triangulation of the disk ⋮ The Smoothing Transform: A Review of Contraction Results ⋮ Precise Tail Index of Fixed Points of the Two-Sided Smoothing Transform ⋮ Precise tail asymptotics of fixed points of the smoothing transform with general weights ⋮ On a functional contraction method ⋮ Selection by rank inK-dimensional binary search trees ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• Some average measures in m-ary search trees
• On the balance property of Patricia tries: External path length viewpoint
• Asymptotic expansions of the mergesort recurrences
• On the distribution of leaves in rooted subtrees of recursive trees
• A fixed point theorem for distributions
• On The variance of the extremal path length in a symmetric digital trie
• Mellin transforms and asymptotics. The mergesort recurrence
• Normal convergence problem? Two moments and a recurrence may be the clues
• The contraction method for recursive algorithms
• On the analysis of stochastic divide and conquer algorithms
• Phase changes in randomm-ary search trees and generalized quicksort
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• Quickselect and the Dickman Function
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Limit laws for local counters in random binary search trees
• Uniform Estimates of the Rate of Convergence in the Multi-Dimensional Central Limit Theorem
• Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees
• Approximation of Distributions of Sums of Independent Random Variables with Values in Infinite-Dimensional Spaces
• Ideal Metrics in the Problem of Approximating Distributions of Sums of Independent Random Variables
• Analysis of the space of search trees under the random insertion algorithm
• The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules
• On the internal path length ofd-dimensional quad trees
• Digital Search Trees Again Revisited: The Internal Path Length Perspective
• The Joint Distribution of Elastic Buckets in Multiway Search Trees
• Stochastic analysis of the Merge-Sort algorithm
• On the structure of random plane‐oriented recursive trees and their branches
• Total Path Length for Random Recursive Trees
• Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
• Rates of convergence for Quicksort
• A multivariate view of random bucket digital search trees
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• An L₂ convergence theorem for random affine mappings
• Probability metrics and recursive algorithms
• Analysis of quickselect : an algorithm for order statistics
• Asymptotic distribution theory for Hoare's selection algorithm
• A limit theorem for “quicksort”
• Limit theorems for the number of maxima in random samples from planar regions

This page was built for publication: A general limit theorem for recursive algorithms and combinatorial structures