LIPIcs.AofA.2022.14.pdf
- Filesize: 0.6 MB
- 13 pages
Document
On the Contraction Method with Reduced Independence Assumptions
Authors
-
Part of:
Volume:
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-08
Cite As Get BibTex
Ralph Neininger and Jasmin Straub. On the Contraction Method with Reduced Independence Assumptions. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 14:1-14:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.AofA.2022.14
Abstract
Recursive sequences of laws of random variables (and random vectors) are considered where an independence assumption which is usually made within the setting of the contraction method is dropped. This restricts the study to sequences which after normalization lead to asymptotic normality. We provide a general univariate central limit theorem which can directly be applied to problems from the analysis of algorithms and random recursive structures without further knowledge of the contraction method. Also multivariate central limit theorems are shown and bounds on rates of convergence are provided. Examples include some previously shown central limit analogues as well as new applications on Fibonacci matchings.
Subject Classification
ACM Subject Classification
- Theory of computation → Sorting and searching
- Theory of computation → Divide and conquer
Keywords
- Probabilistic Analysis of Algorithms
- random Trees
- weak Convergence
- Probability Metrics
- Contraction Method
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Patrick Bindjeme and James Allen Fill. Exact L²-distance from the limit for QuickSort key comparisons (extended abstract). In 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), Discrete Math. Theor. Comput. Sci. Proc., AQ, pages 339-348. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012.
- Persi Diaconis and Brett Kolesnik. Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs. Adv. in Appl. Math., 131:Article 102247, 2021. URL: https://doi.org/10.1016/j.aam.2021.102247.
-
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.
-
Noela Müller. Central limit theorems for multicolour urn models. PhD thesis, Goethe University Frankfurt a.M., 2017. urn:nbn:de:hebis:30:3-453587.
- Noela Müller and Ralph Neininger. Refined asymptotics for the composition of cyclic urns. Electron. J. Probab., 23:Paper no. 117, 20, 2018. URL: https://doi.org/10.1214/18-EJP243.
- Ralph Neininger. Refined Quicksort asymptotics. Random Structures Algorithms, 46(2):346-361, 2015. URL: https://doi.org/10.1002/rsa.20497.
- 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.
-
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, volume 159 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 22, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020.
- 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.
- 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.
- Uwe Rösler and Ludger Rüschendorf. The contraction method for recursive algorithms. Algorithmica, 29(1-2):3-33, 2001. Average-case analysis of algorithms (Princeton, NJ, 1998). URL: https://doi.org/10.1007/BF02679611.
- Jasmin Straub. On Rates of Convergence in the Probabilistic Analysis of Algorithms. PhD thesis, Goethe University Frankfurt a.M., 2021. URL: https://doi.org/10.21248/gups.62402.