2026-07-21T14:12:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16100 2024-03-06T10:56:57Z ddc:004 open_access

On the Contraction Method with Reduced Independence Assumptions Neininger, Ralph Straub, Jasmin Probabilistic Analysis of Algorithms random Trees weak Convergence Probability Metrics Contraction Method 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ralph Neininger and Jasmin Straub 2022 Is Part Of LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2022.14 urn:nbn:de:0030-drops-161008 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.14 eng https://creativecommons.org/licenses/by/4.0/legalcode