License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2022.14
URN: urn:nbn:de:0030-drops-161008
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16100/
Go to the corresponding LIPIcs Volume Portal

Neininger, Ralph ; Straub, Jasmin

On the Contraction Method with Reduced Independence Assumptions

pdf-format:
LIPIcs-AofA-2022-14.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{neininger_et_al:LIPIcs.AofA.2022.14,
  author =	{Neininger, Ralph and Straub, Jasmin},
  title =	{{On the Contraction Method with Reduced Independence Assumptions}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{14:1--14:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16100},
  URN =		{urn:nbn:de:0030-drops-161008},
  doi =		{10.4230/LIPIcs.AofA.2022.14},
  annote =	{Keywords: Probabilistic Analysis of Algorithms, random Trees, weak Convergence, Probability Metrics, Contraction Method}
}

Keywords: Probabilistic Analysis of Algorithms, random Trees, weak Convergence, Probability Metrics, Contraction Method
Collection: 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Issue Date: 2022
Date of publication: 08.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI