×

zbMATH — the first resource for mathematics

On a functional contraction method. (English) Zbl 1372.60045
Summary: 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.

MSC:
60F17 Functional limit theorems; invariance principles
60G18 Self-similar stochastic processes
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Aldous, D. (1994). Recursive self-similarity for random trees, random triangulations and Brownian excursion. Ann. Probab. 22 527-545. · Zbl 0808.60017
[2] Barbour, A. D. (1990). Stein’s method for diffusion approximations. Probab. Theory Related Fields 84 297-322. · Zbl 0665.60008
[3] Barbour, A. D. and Janson, S. (2009). A functional combinatorial central limit theorem. Electron. J. Probab. 14 2352-2370. · Zbl 1193.60010
[4] Bentkus, V. Yu. and Rachkauskas, A. (1984). Estimates for the distance between sums of independent random elements in Banach spaces. Teor. Veroyatn. Primen. 29 49-64. · Zbl 0534.60008
[5] Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. Wiley, New York. · Zbl 0944.60003
[6] Broutin, N., Neininger, R. and Sulzbach, H. (2013). A limit process for partial match queries in random quadtrees and \(2\)-d trees. Ann. Appl. Probab. 23 2560-2603. · Zbl 1358.68080
[7] Cartan, H. (1971). Differential Calculus . Hermann, Paris. · Zbl 0223.35004
[8] Chern, H.-H. and Hwang, H.-K. (2003). Partial match queries in random quadtrees. SIAM J. Comput. 32 904-915 (electronic). · Zbl 1053.68128
[9] Curien, N. and Joseph, A. (2011). Partial match queries in two-dimensional quadtrees: A probabilistic approach. Adv. in Appl. Probab. 43 178-194. · Zbl 1215.68083
[10] Dieudonné, J. (1960). Foundations of Modern Analysis. Pure and Applied Mathematics 10 . Academic Press, New York. · Zbl 0100.04201
[11] Donsker, M. D. (1951). An invariance principle for certain probability limit theorems. Mem. Amer. Math. Soc. 6 12. · Zbl 0042.37602
[12] Drmota, M., Janson, S. and Neininger, R. (2008). A functional limit theorem for the profile of search trees. Ann. Appl. Probab. 18 288-333. · Zbl 1143.68019
[13] Eickmeyer, K. and Rüschendorf, L. (2007). A limit theorem for recursively defined processes in \(L^{p}\). Statist. Decisions 25 217-235. · Zbl 1144.60017
[14] Flajolet, P., Gonnet, G., Puech, C. and Robson, J. M. (1993). Analytic variations on quadtrees. Algorithmica 10 473-500. · Zbl 0783.68056
[15] Giné, E. and León, J. R. (1980). On the central limit theorem in Hilbert space. Stochastica 4 43-71. · Zbl 0432.60011
[16] Janson, S. and Kaijser, S. (2014). Higher moments of Banach space valued random variables. Mem. Amer. Math. Soc. · Zbl 1336.60007
[17] Janson, S. and Neininger, R. (2008). The size of random fragmentation trees. Probab. Theory Related Fields 142 399-442. · Zbl 1158.60044
[18] Ledoux, M. and Talagrand, M. (1991). Probability in Banach Spaces : Isoperimetry and Processes. Ergebnisse der Mathematik und Ihrer Grenzgebiete (3) [ Results in Mathematics and Related Areas (3)] 23 . Springer, Berlin. · Zbl 0748.60004
[19] Lukacs, E. (1975). Stochastic Convergence , 2nd ed. Probability and Mathematical Statistics 30 . Academic Press, New York. · Zbl 0312.60011
[20] Neininger, R. (2001). On a multivariate contraction method for random recursive structures with applications to Quicksort. Random Structures Algorithms 19 498-524. Analysis of algorithms (Krynica Morska, 2000). · Zbl 0990.68054
[21] Neininger, R. (2004). Stochastische Analyse von Algorithmen , Fixpunktgleichungen und Ideale Metriken . Univ. Frankfurt, Habilitation. .
[22] Neininger, R. and Rüschendorf, L. (2004). A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab. 14 378-418. · Zbl 1041.60024
[23] Neininger, R. and Rüschendorf, L. (2004). On the contraction method with degenerate limit equation. Ann. Probab. 32 2838-2856. · Zbl 1060.60005
[24] Pestman, W. R. (1995). Measurability of linear operators in the Skorokhod topology. Bull. Belg. Math. Soc. Simon Stevin 2 381-388. · Zbl 0844.47016
[25] Rachev, S. T. and Rüschendorf, L. (1995). Probability metrics and recursive algorithms. Adv. in Appl. Probab. 27 770-799. · Zbl 0829.60094
[26] Rösler, U. (1991). A limit theorem for “Quicksort”. RAIRO Inform. Théor. Appl. 25 85-100. · Zbl 0718.68026
[27] Rösler, U. (1992). A fixed point theorem for distributions. Stochastic Process. Appl. 42 195-214. · Zbl 0761.60015
[28] Rösler, U. (2001). On the analysis of stochastic divide and conquer algorithms. Algorithmica 29 238-261. Average-case analysis of algorithms (Princeton, NJ, 1998). · Zbl 0967.68168
[29] Rösler, U. and Rüschendorf, L. (2001). The contraction method for recursive algorithms. Algorithmica 29 3-33. · Zbl 0967.68166
[30] Strassen, V. and Dudley, R. M. (1969). The central limit theorem and \(\varepsilon\)-entropy. In Probability and Information Theory ( Proc. Internat. Sympos. , McMaster Univ. , Hamilton , Ont. , 1968) 224-231. Springer, Berlin.
[31] Sulzbach, H. (2012). On a functional contraction method. Dissertation, Univ. Frankfurt. Available at .
[32] Zolotarev, V. M. (1976). Approximation of the distributions of sums of independent random variables with values in infinite-dimensional spaces. Teor. Veroyatn. Primen. 21 741-758.
[33] Zolotarev, V. M. (1976). Metric distances in spaces of random variables and of their distributions. Mat. Sb. 101(143) 416-454, 456. · Zbl 0367.60003
[34] Zolotarev, V. M. (1977). Ideal metrics in the problem of approximating the distributions of sums of independent random variables. Teor. Veroyatn. Primen. 22 449-465. · Zbl 0385.60025
[35] Zolotarev, V. M. (1979). Ideal metrics in the problems of probability theory and mathematical statistics. Austral. J. Statist. 21 193-208. · Zbl 0428.62012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.