2 Search Results for "Borga, Jacopo"

Document

DOI: 10.4230/LIPIcs.AofA.2024.21

Binary Search Trees of Permuton Samples

Authors: Benoît Corsini, Victor Dubach, and Valentin Féray

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

Abstract

Binary search trees (BST) are a popular type of structure when dealing with ordered data. They allow efficient access and modification of data, with their height corresponding to the worst retrieval time. From a probabilistic point of view, BSTs associated with data arriving in a uniform random order are well understood, but less is known when the input is a non-uniform permutation. We consider here the case where the input comes from i.i.d. random points in the plane with law μ, a model which we refer to as a permuton sample. Our results show that the asymptotic proportion of nodes in each subtree only depends on the behavior of the measure μ at its left boundary, while the height of the BST has a universal asymptotic behavior for a large family of measures μ. Our approach involves a mix of combinatorial and probabilistic tools, namely combinatorial properties of binary search trees, coupling arguments, and deviation estimates.

Cite as

Benoît Corsini, Victor Dubach, and Valentin Féray. Binary Search Trees of Permuton Samples. 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. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{corsini_et_al:LIPIcs.AofA.2024.21,
  author =	{Corsini, Beno\^{i}t and Dubach, Victor and F\'{e}ray, Valentin},
  title =	{{Binary Search Trees of Permuton Samples}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{21:1--21:13},
  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.21},
  URN =		{urn:nbn:de:0030-drops-204562},
  doi =		{10.4230/LIPIcs.AofA.2024.21},
  annote =	{Keywords: Binary search trees, random permutations, permutons}
}

Document

DOI: 10.4230/LIPIcs.AofA.2020.7

Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes

Authors: Jacopo Borga and Mickaël Maazoun

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

Abstract

Baxter permutations, plane bipolar orientations, and a specific family of walks in the non-negative quadrant are well-known to be related to each other through several bijections. We introduce a further new family of discrete objects, called coalescent-walk processes, that are fundamental for our results. We relate these new objects with the other previously mentioned families introducing some new bijections. We prove joint Benjamini - Schramm convergence (both in the annealed and quenched sense) for uniform objects in the four families. Furthermore, we explicitly construct a new fractal random measure of the unit square, called the coalescent Baxter permuton and we show that it is the scaling limit (in the permuton sense) of uniform Baxter permutations. To prove the latter result, we study the scaling limit of the associated random coalescent-walk processes. We show that they converge in law to a continuous random coalescent-walk process encoded by a perturbed version of the Tanaka stochastic differential equation. This result has connections (to be explored in future projects) with the results of Gwynne, Holden, Sun (2016) on scaling limits (in the Peanosphere topology) of plane bipolar triangulations. We further prove some results that relate the limiting objects of the four families to each other, both in the local and scaling limit case.

Cite as

Jacopo Borga and Mickaël Maazoun. Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes. 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. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{borga_et_al:LIPIcs.AofA.2020.7,
  author =	{Borga, Jacopo and Maazoun, Micka\"{e}l},
  title =	{{Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{7:1--7:18},
  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.7},
  URN =		{urn:nbn:de:0030-drops-120370},
  doi =		{10.4230/LIPIcs.AofA.2020.7},
  annote =	{Keywords: Local and scaling limits, permutations, planar maps, random walks in cones}
}

Refine by Author
1 Borga, Jacopo
1 Corsini, Benoît
1 Dubach, Victor
1 Féray, Valentin
1 Maazoun, Mickaël

Refine by Classification
1 Mathematics of computing → Permutations and combinations
1 Mathematics of computing → Probabilistic algorithms
1 Mathematics of computing → Probability and statistics
1 Mathematics of computing → Trees

Refine by Keyword
1 Binary search trees
1 Local and scaling limits
1 permutations
1 permutons
1 planar maps
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2020
1 2024