On a functional contraction method

DOI10.1214/14-AOP919MaRDI QIDQ2354151zbMATH OpenOpenAlexFDO

Authors Ralph Neininger, Henning Sulzbach

Publication date 10 July 2015

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

Full work available at URL https://arxiv.org/abs/1202.1370, https://projecteuclid.org/euclid.aop/1433341320

zbMATH Keywords

functional limit theoremDonsker's invariance principlecontraction methodrecursive distributional equationZolotarev metric

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Combinatorial probability (60C05) Self-similar stochastic processes (60G18)

Abstract: Methods for proving functional limit laws are developed for sequences of stochastic processes which allow a recursive distributional decomposition either in time or space. Our approach is an extension of the so-called contraction method to the space $mathcalC[0,1]$ of continuous functions endowed with uniform topology and the space $mathcalD[0,1]$ of c`{a}dl`{a}g functions with the Skorokhod topology. The contraction method originated from the probabilistic analysis of algorithms and random trees where characteristics satisfy natural distributional recurrences. It is based on stochastic fixed-point equations, where probability metrics can be used to obtain contraction properties and allow the application of Banach's fixed-point theorem. We develop the use of the Zolotarev metrics on the spaces $mathcalC[0,1]$ and $mathcalD[0,1]$ in this context. Applications are given, in particular, a short proof of Donsker's functional limit theorem is derived and recurrences arising in the probabilistic analysis of algorithms are discussed.

Recommendations

• The contraction method for recursive algorithms
• A general limit theorem for recursive algorithms and combinatorial structures
• scientific article; zbMATH DE number 1392847
• A limit theorem for recursively defined processes in Lp
• A functional limit theorem for the profile of search trees

Cites work

• scientific article; zbMATH DE number 3163006 (Why is no real title available?)
• scientific article; zbMATH DE number 3848298 (Why is no real title available?)
• scientific article; zbMATH DE number 3673252 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 3488357 (Why is no real title available?)
• scientific article; zbMATH DE number 3572929 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 3353830 (Why is no real title available?)
• scientific article; zbMATH DE number 3065414 (Why is no real title available?)
• A fixed point theorem for distributions
• A functional combinatorial central limit theorem
• A functional limit theorem for the profile of search trees
• A general limit theorem for recursive algorithms and combinatorial structures
• A limit process for partial match queries in random quadtrees and 2-d trees
• A limit theorem for recursively defined processes in Lp
• A limit theorem for “quicksort”
• Analytic variations on quadtrees
• Higher moments of Banach space valued random variables
• IDEAL METRICS IN THE PROBLEMS OF PROBABILITY THEORY AND MATHEMATICAL STATISTICS
• Ideal Metrics in the Problem of Approximating Distributions of Sums of Independent Random Variables
• Measurability of linear operators in the Skorokhod topology
• On a multivariate contraction method for random recursive structures with applications to quicksort
• On the analysis of stochastic divide and conquer algorithms
• On the contraction method with degenerate limit equation.
• Partial Match Queries in Random Quadtrees
• Partial match queries in two-dimensional quadtrees: a probabilistic approach
• Probability metrics and recursive algorithms
• Recursive self-similarity for random trees, random triangulations and Brownian excursion
• Stein's method for diffusion approximations
• The contraction method for recursive algorithms
• The size of random fragmentation trees

Cited in

(20)

• An optimal Berry-Esseen type theorem for integrals of smooth functions
• Partial match queries in random quadtrees
• Self-similar real trees defined as fixed points and their geometric properties
• scientific article; zbMATH DE number 1076112 (Why is no real title available?)
• A limit theorem for recursively defined processes in Lp
• scientific article; zbMATH DE number 7491483 (Why is no real title available?)
• The weighted branching process
• A limit process for partial match queries in random quadtrees and 2-d trees
• A robust variant of the method of contracting compacta
• Higher moments of Banach space valued random variables
• On densities for solutions to stochastic fixed point equations
• Stochastic fixed-point equations
• A limit field for orthogonal range searches in two-dimensional random point search trees
• On the contraction method with degenerate limit equation.
• The quicksort process
• Process convergence for the complexity of radix selection on Markov sources
• The dual tree of a recursive triangulation of the disk
• All solutions of the stochastic fixed point equation of the Quicksort process
• Parameterised branching processes: a functional version of Kesten \& Stigum theorem
• Combinatorial analysis of growth models for series-parallel networks

This page was built for publication: On a functional contraction method

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