## Abstract

Methods for proving functional limit laws are developed for se-

quences 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 C[0, 1] of continu-

ous functions endowed with uniform topology and the space D[0, 1]

of c`adl`ag functions with the Skorokhod topology. The contraction

method originated from the probabilistic analysis of algorithms and

random trees where characteristics satisfy natural distributional re-

currences. It is based on stochastic fixed-point equations, where prob-

ability 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 C[0, 1] and D[0, 1] in this con-

text. 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.

quences 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 C[0, 1] of continu-

ous functions endowed with uniform topology and the space D[0, 1]

of c`adl`ag functions with the Skorokhod topology. The contraction

method originated from the probabilistic analysis of algorithms and

random trees where characteristics satisfy natural distributional re-

currences. It is based on stochastic fixed-point equations, where prob-

ability 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 C[0, 1] and D[0, 1] in this con-

text. 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.

Original language | English |
---|---|

Pages (from-to) | 1777-1822 |

Number of pages | 48 |

Journal | Annals of Probability |

Volume | 43 |

Issue number | 4 |

DOIs | |

Publication status | Published - 3 Jun 2015 |

## Keywords

- functional limit theorem
- contraction method
- recursive distributional equation
- Zolotarev metric
- Donsker’s invariance principle