On the Moment-Transfer Approach for Random Variables Satisfying a One-Sided Distributional Recurrence

Che-Hao Chen (National Chiao Tung University)
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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. L. Devroye. Universal limit laws for depths in random trees. SIAM Journal on Computing 28 (1999), 409--432. Math. Review 2000e:68073
  7. P. D. T. A. Elliott. Probabilistic Number Theory I. Central Limit Theorems. Springer, New-York (1979).
  8. 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
  9. P. Flajolet and R. Sedgewick. An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading, MA (1996).
  10. P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press (2009). Math. Review 2010h:05005
  11. V. Goncharov. On the field of combinatory analysis. Soviet Math. IZv., Ser.Math. 8 (1944), 3--48.
  12. 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
  13. 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
  14. 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
  15. 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
  16. H. M. Mahmoud. Evolution of Random Search Trees. Wiley, New York (1992). Math. Review 93f:68045
  17. 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
  18. 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
  19. 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
  20. 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
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.