On a functional contraction method

• DOI: 10.1214/14-aop919
• Publication Date: 2015-06-03T15:36:41Z
• Authors: Ralph Neininger; Henning Sulzbach
• Keywords: FOS: Computer and information sciences; Donsker’s invariance principle; Probability (math.PR); 68Q25; contraction method; recursive distributional equation; 01 natural sciences; Zolotarev metric; Functional limit theorem; 60F17; 60G18; Computer Science - Data Structures and Algorithms; FOS: Mathematics; 60C05; Data Structures and Algorithms (cs.DS); 0101 mathematics; Mathematics - Probability

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.<br/>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)<br/>