2 Search Results for "Straub, Jasmin"


Document
On the Contraction Method with Reduced Independence Assumptions

Authors: Ralph Neininger and Jasmin Straub

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)


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.

Cite as

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)


Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.AofA.2022.14},
  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}
}
Document
Convergence Rates in the Probabilistic Analysis of Algorithms

Authors: Ralph Neininger and Jasmin Straub

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{neininger_et_al:LIPIcs.AofA.2020.22,
  author =	{Neininger, Ralph and Straub, Jasmin},
  title =	{{Convergence Rates in the Probabilistic Analysis of Algorithms}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.22},
  URN =		{urn:nbn:de:0030-drops-120529},
  doi =		{10.4230/LIPIcs.AofA.2020.22},
  annote =	{Keywords: weak convergence, probabilistic analysis of algorithms, random trees, probability metrics}
}
  • Refine by Author
  • 2 Neininger, Ralph
  • 2 Straub, Jasmin

  • Refine by Classification
  • 2 Theory of computation → Divide and conquer
  • 2 Theory of computation → Sorting and searching

  • Refine by Keyword
  • 1 Contraction Method
  • 1 Probabilistic Analysis of Algorithms
  • 1 Probability Metrics
  • 1 probabilistic analysis of algorithms
  • 1 probability metrics
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022

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