On densities for solutions to stochastic fixed point equations

We consider systems of stochastic fixed point equations that arise in the asymptotic analysis of random recursive structures and algorithms such as Quicksort, large Pólya urn processes, and path lengths of random recursive trees and split trees. The main result states sufficient conditions on the fixed point equations that imply the existence of bounded, smooth, rapidly decreasing Lebesgue densities.

• Publication year

  2016

• Venue

  Random Struct. Algorithms

• Publication date

  2016-04-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/rsa.20799arXiv 1604.05787
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the tails of the limiting Quicksort distribution

  2015cited by this paper
• The CLT Analogue for Cyclic Urns

  2015cited by this paper
• B-urns

  2014cited by this paper
• Describing the asymptotic behaviour of multicolour P\'olya urns via smoothing systems analysis

  2014cited by this paper
• Smoothing Equations for Large Pólya Urns

  2013cited by this paper
• Asymptotic Analysis of Hoppe Trees

  2012influential reference
• Support and density of the limit $m$-ary search trees distribution

  2012influential reference
• Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model

  2012cited by this paper
• On a functional contraction method

  2012cited by this paper
• Limit distributions for multitype branching processes of $m$-ary search trees

  2011cited by this paper
• On the Asymptotic Internal Path Length and the Asymptotic Wiener Index of Random Split Trees

  2011influential reference
• The total path length of split trees

  2011influential reference
• Limit distributions for large P\'{o}lya urns

  2009influential reference
• 78035 Versailles cedex

  2009influential reference
• Polya Urn Models

  2008cited by this paper
• The size of random fragmentation trees

  2006cited by this paper
• Analytic urns

  2004cited by this paper
• A general limit theorem for recursive algorithms and combinatorial structures

  2004cited by this paper
• Functional limit theorems for multitype branching processes and generalized Pólya urns

  2004influential reference
• On the contraction method with degenerate limit equation

  2004cited by this paper
• Transfer theorems and asymptotic distributional results for m‐ary search trees

  2003cited by this paper
• Density approximation and exact simulation of random variables that are solutions of fixed-point equations

  2002cited by this paper
• Asymptotic properties and absolute continuity of laws stable by random weighted mean

  2001influential reference
• On the analysis of stochastic divide and conquer algorithms

  2001cited by this paper
• On a multivariate contraction method for random recursive structures with applications to Quicksort

  2001cited by this paper
• Smoothness and decay properties of the limiting Quicksort density function

  2000influential reference
• Total Path Length for Random Recursive Trees

  1999influential reference
• On the internal path length of d-dimensional quad trees

  1999cited by this paper
• Asymptotic properties of supercritical age-dependent branching processes and homogeneous branching random walks

  1999cited by this paper
• Universal Limit Laws for Depths in Random Trees

  1999cited by this paper
• Quicksort Algorithm Again Revisited

  1999cited by this paper
• On the internal path length of d -dimensional quad trees

  1999cited by this paper
• Probability metrics and recursive algorithms

  1995cited by this paper
• Some properties of a limiting distribution in Quicksort

  1995cited by this paper
• A fixed point theorem for distributions

  1992influential reference
• Limiting Distributions for Path Lengths in Recursive Trees

  1991influential reference
• A limit theorem for "Quicksort"

  1991influential reference
• A Limiting Distribution for Quicksort

  1989cited by this paper
• Limit Theorems for Certain Branching Random Walks on Compact Groups and Homogeneous Spaces

  1983influential reference
• Urn Models and Their Application—An Approach to Modern Discrete Probability Theory

  1978cited by this paper
• Urn models and their application : an approach to modern discrete probability theory

  1978cited by this paper
• Urn models and their application

  1977influential reference
• A limit theorem for a class of supercritical branching processes

  1972cited by this paper
• On the Supercritical One Dimensional Age Dependent Branching Processes

  1969influential reference
• A Limit Theorem for Multidimensional Galton-Watson Processes

  1966cited by this paper
• Quicksort

  1962cited by this paper
• An Introduction to Probability Theory and Its Applications

  1959cited by this paper
• Combinatorics, Probability and Computing Pólya Urns via the Contraction Method P ´ Olya Urns via the Contraction Method

  year unknowninfluential reference

• Probabilistic analysis of optimal multi-pivot QuickSort

  2025cites this paper
• On conditioning a self-similar growth-fragmentation by its intrinsic area

  2019cites this paper
• Refined Asymptotics for the Number of Leaves of Random Point Quadtrees

  2018cites this paper
• Balanced multicolour Pólya urns via smoothing systems analysis

  2018cites this paper
• Absolute continuity of the martingale limit in branching processes in random environment

  2018cites this paper
• Absolute Continuity of Complex Martingales and of Solutions to Complex Smoothing Equations

  2018influential citation
• 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018, Uppsala, Sweden, June 25-29, 2018

  2018cites this paper
• Probabilistic Analysis of the Dual-Pivot Quicksort "Count"

  2017influential citation