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