On the Moment-Transfer Approach for Random Variables Satisfying a One-Sided Distributional Recurrence
Michael Fuchs (National Chiao Tung University)
Abstract
The moment-transfer approach is a standard tool for deriving limit laws of sequences of random variables satisfying a distributional recurrence. However, so far the approach could not be applied to certain "one-sided" recurrences with slowly varying moments and normal limit law. In this paper, we propose a modified version of the moment-transfer approach which can be applied to such recurrences. Moreover, we demonstrate the usefulness of our approach by re-deriving several recent results in an almost automatic fashion.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 903-928
Publication Date: May 10, 2011
DOI: 10.1214/EJP.v16-885
References
- A. Bagchi and A. K. Pal. Asymptotic normality in the generalized Polya-Eggenberger urn model, with an application to computer data structures. SIAM Journal on Algebraic and Discrete Methods 6 (1985), 394--405. Math. Review 86j:60025
- Z.-D. Bai, H.-K. Hwang, W.-Q. Liang. Normal approximations of the number of records in geometrically distributed random variables. Random Structures and Algorithms 13 (1998), 319--334. Math. Review 99k:60051
- H.-H. Chern, M. Fuchs, H.-K. Hwang. Phase changes in random point quadtrees. ACM Transactions on Algorithms 3 (2007), 51 pages. Math. Review 2008i:68023
- H.-H. Chern and H.-K. Hwang. Phase changes in random m-ary search trees and generalized quicksort. Random Structures and Algorithms 19 (2001), 316--358. Math. Review 2002k:68040
- H.-H. Chern, H.-K. Hwang, T.-H. Tsai. An asymptotic theory for Cauchy-Euler differential equations with applications to the analysis of algorithms. Journal of Algorithms 44 (2002), 177--225. Math. Review 2004b:68197
- L. Devroye. Universal limit laws for depths in random trees. SIAM Journal on Computing 28 (1999), 409--432. Math. Review 2000e:68073
- P. D. T. A. Elliott. Probabilistic Number Theory I. Central Limit Theorems. Springer, New-York (1979).
- P. Flajolet and T. Lafforgue. Search costs in quadtrees and singularity perturbation asymptotics. Discrete and Computational Geometry 12 (1994), 151--175. Math. Review 95d:68020
- P. Flajolet and R. Sedgewick. An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading, MA (1996).
- P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press (2009). Math. Review 2010h:05005
- V. Goncharov. On the field of combinatory analysis. Soviet Math. IZv., Ser.Math. 8 (1944), 3--48.
- H.-K. Hwang. Phase changes in random recursive structures and algorithms (a brief survey). "Proceedings of the Workshop on Probability with Applications to Finance and Insurance", World Scientific 8 (2004), 82--97. Math. Review
- H.-K. Hwang and R. Neininger. Phase change of limit laws in the quicksort recurrences under varying toll functions. SIAM Journal on Computing 31 (2002), 1687--1722. Math. Review 2003m:68034
- A. Iksanov, A. Marynych, M. Moehle. On the number of collisions in beta(2,b)-coalesents. Bernoulli 15 (2009), 829--845. Math. Review 2011c:60315
- M. Kuba and A. Panholzer. Analysis of insertion costs in priority trees. "Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics", SIAM Philadelphia (2007), 175--182. Math. Review
- H. M. Mahmoud. Evolution of Random Search Trees. Wiley, New York (1992). Math. Review 93f:68045
- H. M. Mahmoud and B. Pittel. On the joint distribution of the insertion path length and the number of comparisons in search trees. Discrete Applied Mathematics 20 (1988), 243--251. Math. Review 89d:68005
- R. Neininger and L. Rueschendorf. On the contraction method with degenerate limit equation. The Annals of Probability 32 (2004), 2838--2856. Math. Review 2005f:60062
- A. Panholzer. Analysis for some parameters for random nodes in priority trees. Discrete Mathematics and Theoretical Computer Science 10 (2008), 1--38. Math. Review 2010d:68023
- A. Panholzer and H. Prodinger. Average case analysis priority trees: a structure for priority queue administration. Algorithmica 22 (1998), 600--630. Math. Review 2000i:68031
This work is licensed under a Creative Commons Attribution 3.0 License.