On a functional contraction method

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 $\mathcal{C}[0,1]$ of continuous functions endowed with uniform topology and the space $\mathcal{D}[0,1]$ of càdlà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 $\mathcal{C}[0,1]$ and $\mathcal{D}[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.

Published at http://dx.doi.org/10.1214/14-AOP919 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• A functional limit theorem for the profile of search trees
• On a functional contraction method
• A limit process for partial match queries in random quadtrees and $2$-d trees

Cited by in corpus (8)

• Polya urns via the contraction method
• On a functional contraction method
• A limit process for partial match queries in random quadtrees and $2$-d trees
• The dual tree of a recursive triangulation of the disk
• A Limit Theorem for Radix Sort and Tries with Markovian Input
• Combinatorial analysis of growth models for series-parallel networks
• The Brownian continuum random tree as the unique solution to a fixed point equation
• The Quicksort Process