DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2024.25

Patricia’s Bad Distributions

Authors: Louigi Addario-Berry, Pat Morin, and Ralph Neininger

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract

The height of a random PATRICIA tree built from independent, identically distributed infinite binary strings with arbitrary diffuse probability distribution μ on {0,1}^ℕ is studied. We show that the expected height grows asymptotically sublinearly in the number of leaves for any such μ, but can be made to exceed any specific sublinear growth rate by choosing μ appropriately.

Cite as

Louigi Addario-Berry, Pat Morin, and Ralph Neininger. Patricia’s Bad Distributions. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 25:1-25:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{addarioberry_et_al:LIPIcs.AofA.2024.25,
  author =	{Addario-Berry, Louigi and Morin, Pat and Neininger, Ralph},
  title =	{{Patricia’s Bad Distributions}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{25:1--25:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.25},
  URN =		{urn:nbn:de:0030-drops-204600},
  doi =		{10.4230/LIPIcs.AofA.2024.25},
  annote =	{Keywords: PATRICIA tree, random tree, height of tree, analysis of algorithms}
}

Document

Keynote Speakers

DOI: 10.4230/LIPIcs.AofA.2018.2

Assumptionless Bounds for Random Trees (Keynote Speakers)

Authors: Louigi Addario-Berry

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract

Let T be any Galton-Watson tree. Write vol(T) for the volume of T (the number of nodes), ht(T) for the height of T (the greatest distance of any node from the root) and wid(T) for the width of T (the greatest number of nodes at any level). We study the relation between vol(T), ht(T) and wid(T). In the case when the offspring distribution p = (p_i, i >= 0) has mean one and finite variance, both ht(T) and wid(T) are typically of order vol(T)^{1/2}, and have sub-Gaussian upper tails on this scale. Heuristically, as the tail of the offspring distribution becomes heavier, the tree T becomes "shorter and bushier". I will describe a collection of work which can be viewed as justifying this heuristic in various ways In particular, I will explain how classical bounds on Lévy's concentration function for random walks may be used to show that for any offspring distribution, the random variable ht(T)/wid(T) has sub-exponential tails. I will also describe a more combinatorial approach to coupling random trees with different degree sequences which allows the heights of randomly sampled vertices to be compared.

Cite as

Louigi Addario-Berry. Assumptionless Bounds for Random Trees (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{addarioberry:LIPIcs.AofA.2018.2,
  author =	{Addario-Berry, Louigi},
  title =	{{Assumptionless Bounds for Random Trees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and 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.2018.2},
  URN =		{urn:nbn:de:0030-drops-88951},
  doi =		{10.4230/LIPIcs.AofA.2018.2},
  annote =	{Keywords: Random trees, simply generated trees}
}

Search Results

Documents authored by Addario-Berry, Louigi

Patricia’s Bad Distributions

Abstract

Cite as

Assumptionless Bounds for Random Trees (Keynote Speakers)

Abstract

Cite as

Thanks for your feedback!

Could not send message