On a functional contraction method

DOI10.1214/14-AOP919zbMATH Open1372.60045arXiv1202.1370OpenAlexW2144905577MaRDI QIDQ2354151FDOQ2354151

Authors: Ralph Neininger, Henning Sulzbach 

Publication date: 10 July 2015

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

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.

Full work available at URL: https://arxiv.org/abs/1202.1370

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

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)

Cites Work

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

Cited In (20)

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

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)