Document Open Access Logo

Convergence Rates in the Probabilistic Analysis of Algorithms

Authors Ralph Neininger, Jasmin Straub

PDF
Thumbnail PDF

File

LIPIcs.AofA.2020.22.pdf
  • Filesize: 437 kB
  • 13 pages

Document Identifiers

Author Details

Ralph Neininger
  • Institute for Mathematics, Goethe University, 60054 Frankfurt am Main, Germany
Jasmin Straub
  • Institute for Mathematics, Goethe University, 60054 Frankfurt am Main, Germany

Cite As Get BibTex

Ralph Neininger and Jasmin Straub. Convergence Rates in the Probabilistic Analysis of Algorithms. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.AofA.2020.22

Abstract

In this extended abstract a general framework is developed to bound rates of convergence for sequences of random variables as they mainly arise in the analysis of random trees and divide-and-conquer algorithms. The rates of convergence are bounded in the Zolotarev distances. Concrete examples from the analysis of algorithms and data structures are discussed as well as a few examples from other areas. They lead to convergence rates of polynomial and logarithmic order. Our results show how to obtain a significantly better bound for the rate of convergence when the limiting distribution is Gaussian.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sorting and searching
  • Theory of computation → Divide and conquer
Keywords
  • weak convergence
  • probabilistic analysis of algorithms
  • random trees
  • probability metrics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Zhi-Dong Bai, Hsien-Kuei Hwang, Wen-Qi Liang, and Tsung-Hsi Tsai. Limit theorems for the number of maxima in random samples from planar regions. Electron. J. Probab., 6:no. 3, 41 pp. (electronic), 2001. URL: https://doi.org/10.1214/EJP.v6-76.
  2. Zhi-Dong Bai, Hsien-Kuei Hwang, and Tsung-Hsi Tsai. Berry-Esseen bounds for the number of maxima in planar regions. Electron. J. Probab., 8:no. 9, 26, 2003. URL: https://doi.org/10.1214/EJP.v8-137.
  3. Hua-Huai Chern, Michael Fuchs, and Hsien-Kuei Hwang. Phase changes in random point quadtrees. ACM Trans. Algorithms, 3(2):Art. 12, 51, 2007. URL: https://doi.org/10.1145/1240233.1240235.
  4. Hua-Huai Chern and Hsien-Kuei Hwang. Phase changes in random m-ary search trees and generalized quicksort. Random Structures Algorithms, 19(3-4):316-358, 2001. Analysis of algorithms (Krynica Morska, 2000). URL: https://doi.org/10.1002/rsa.10005.
  5. Luc Devroye. Limit laws for local counters in random binary search trees. Random Structures Algorithms, 2(3):303-315, 1991. URL: https://doi.org/10.1002/rsa.3240020305.
  6. James Allen Fill and Svante Janson. Quicksort asymptotics. J. Algorithms, 44(1):4-28, 2002. Analysis of algorithms. URL: https://doi.org/10.1016/S0196-6774(02)00216-X.
  7. Philippe Flajolet, Gilbert Labelle, Louise Laforest, and Bruno Salvy. Hypergeometrics and the cost structure of quadtrees. Random Structures Algorithms, 7(2):117-144, 1995. URL: https://doi.org/10.1002/rsa.3240070203.
  8. Michael Fuchs, Noela S. Müller, and Henning Sulzbach. Refined asymptotics for the number of leaves of random point quadtrees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, volume 110 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 23, 16. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. Google Scholar
  9. Hsien-Kuei Hwang. Second phase changes in random m-ary search trees and generalized quicksort: convergence rates. Ann. Probab., 31(2):609-629, 2003. URL: https://doi.org/10.1214/aop/1048516530.
  10. Hsien-Kuei Hwang, Michael Fuchs, and Vytas Zacharovas. Asymptotic variance of random symmetric digital search trees. Discrete Math. Theor. Comput. Sci., 12(2):103-165, 2010. Google Scholar
  11. Philippe Jacquet and Wojciech Szpankowski. Analytical de-Poissonization and its applications. Theoret. Comput. Sci., 201(1-2):1-62, 1998. URL: https://doi.org/10.1016/S0304-3975(97)00167-9.
  12. Hosam M. Mahmoud. Evolution of random search trees. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., New York, 1992. A Wiley-Interscience Publication. Google Scholar
  13. Ralph Neininger and Ludger Rüschendorf. Rates of convergence for Quicksort. J. Algorithms, 44(1):51-62, 2002. Analysis of algorithms. URL: https://doi.org/10.1016/S0196-6774(02)00206-7.
  14. Ralph Neininger and Ludger Rüschendorf. A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab., 14(1):378-418, 2004. URL: https://doi.org/10.1214/aoap/1075828056.
  15. Ralph Neininger and Ludger Rüschendorf. On the contraction method with degenerate limit equation. Ann. Probab., 32(3B):2838-2856, 2004. URL: https://doi.org/10.1214/009117904000000171.
  16. Mireille Régnier. A limiting distribution for quicksort. RAIRO Inform. Théor. Appl., 23(3):335-343, 1989. URL: https://doi.org/10.1051/ita/1989230303351.
  17. Uwe Rösler. A limit theorem for "Quicksort". RAIRO Inform. Théor. Appl., 25(1):85-100, 1991. URL: https://doi.org/10.1051/ita/1991250100851.
  18. Werner Schachinger. Asymptotic normality of recursive algorithms via martingale difference arrays. Discrete Math. Theor. Comput. Sci., 4(2):363-397, 2001. Google Scholar
  19. V. M. Zolotarev. Approximation of the distributions of sums of independent random variables with values in infinite-dimensional spaces. Teor. Verojatnost. i Primenen., 21(4):741-758, 1976. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact