5 Search Results for "Banderier, Cyril"

Document
DOI: 10.4230/LIPIcs.AofA.2020.1
On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution

Authors: Andrei Asinowski and Cyril Banderier

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

Abstract
In this article, we analyse the joint distribution of some given set of patterns in fundamental combinatorial structures such as words and random walks (directed lattice paths on ℤ²). Our method relies on a vectorial generalization of the classical kernel method, and on a matricial generalization of the autocorrelation polynomial (thus extending the univariate case of Guibas and Odlyzko). This gives access to the multivariate generating functions, for walks, meanders (walks constrained to be above the x-axis), and excursions (meanders constrained to end on the x-axis). We then demonstrate the power of our methods by obtaining closed-form expressions for an infinite family of models, in terms of simple combinatorial quantities. Finally, we prove that the joint distribution of the patterns in walks/bridges/excursions/meanders satisfies a multivariate Gaussian limit law.
Cite as

Andrei Asinowski and Cyril Banderier. On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution. 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. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{asinowski_et_al:LIPIcs.AofA.2020.1,
  author =	{Asinowski, Andrei and Banderier, Cyril},
  title =	{{On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{1:1--1:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.1},
  URN =		{urn:nbn:de:0030-drops-120317},
  doi =		{10.4230/LIPIcs.AofA.2020.1},
  annote =	{Keywords: Lattice path, Dyck path, Motzkin path, generating function, algebraic function, kernel method, context-free grammar, multivariate Gaussian distribution}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.2
Latticepathology and Symmetric Functions (Extended Abstract)

Authors: Cyril Banderier, Marie-Louise Lackner, and Michael Wallner

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

Abstract
In this article, we revisit and extend a list of formulas based on lattice path surgery: cut-and-paste methods, factorizations, the kernel method, etc. For this purpose, we focus on the natural model of directed lattice paths (also called generalized Dyck paths). We introduce the notion of prime walks, which appear to be the key structure to get natural decompositions of excursions, meanders, bridges, directly leading to the associated context-free grammars. This allows us to give bijective proofs of bivariate versions of Spitzer/Sparre Andersen/Wiener - Hopf formulas, thus capturing joint distributions. We also show that each of the fundamental families of symmetric polynomials corresponds to a lattice path generating function, and that these symmetric polynomials are accordingly needed to express the asymptotic enumeration of these paths and some parameters of limit laws. En passant, we give two other small results which have their own interest for folklore conjectures of lattice paths (non-analyticity of the small roots in the kernel method, and universal positivity of the variability condition occurring in many Gaussian limit law schemes).
Cite as

Cyril Banderier, Marie-Louise Lackner, and Michael Wallner. Latticepathology and Symmetric Functions (Extended Abstract). 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. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2020.2,
  author =	{Banderier, Cyril and Lackner, Marie-Louise and Wallner, Michael},
  title =	{{Latticepathology and Symmetric Functions (Extended Abstract)}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{2:1--2:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.2},
  URN =		{urn:nbn:de:0030-drops-120329},
  doi =		{10.4230/LIPIcs.AofA.2020.2},
  annote =	{Keywords: Lattice path, generating function, symmetric function, algebraic function, kernel method, context-free grammar, Sparre Andersen formula, Spitzer’s identity, Wiener - Hopf factorization}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.11
Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language

Authors: Andrew Elvey Price, Wenjie Fang, and Michael Wallner

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

Abstract
We show that the number of minimal deterministic finite automata with n+1 states recognizing a finite binary language grows asymptotically for n → ∞ like Θ(n! 8ⁿ e^{3 a₁ n^{1/3}} n^{7/8}), where a₁ ≈ -2.338 is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two-parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Netwon polygons.
Cite as

Andrew Elvey Price, Wenjie Fang, and Michael Wallner. Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language. 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. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{elveyprice_et_al:LIPIcs.AofA.2020.11,
  author =	{Elvey Price, Andrew and Fang, Wenjie and Wallner, Michael},
  title =	{{Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{11:1--11: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.11},
  URN =		{urn:nbn:de:0030-drops-120419},
  doi =		{10.4230/LIPIcs.AofA.2020.11},
  annote =	{Keywords: Airy function, asymptotics, directed acyclic graphs, Dyck paths, bijection, stretched exponential, compacted trees, minimal automata, finite languages}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.10
Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem

Authors: Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger

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

Abstract
In a companion article dedicated to the enumeration aspects, we showed how to obtain closed form formulas for the generating functions of walks, bridges, meanders, and excursions avoiding any fixed word (a pattern p). The autocorrelation polynomial of this forbidden pattern p (as introduced by Guibas and Odlyzko in 1981, in the context of regular expressions) plays a crucial role. In this article, we get the asymptotics of these walks. We also introduce a trivariate generating function (length, final altitude, number of occurrences of p), for which we derive a closed form. We prove that the number of occurrences of p is normally distributed: This is what Flajolet and Sedgewick call an instance of Borges's theorem. We thus extend and refine the study by Banderier and Flajolet in 2002 on lattice paths, and we unify several dozens of articles which investigated patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. Our approach relies on methods of analytic combinatorics, and on a matricial generalization of the kernel method. The situation is much more involved than in the Banderier-Flajolet work: forbidden patterns lead to a wider zoology of asymptotic behaviours, and we classify them according to the geometry of a Newton polygon associated with these constrained walks, and we analyse what are the universal phenomena common to all these models of lattice paths avoiding a pattern.
Cite as

Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger. Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem. 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, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{asinowski_et_al:LIPIcs.AofA.2018.10,
  author =	{Asinowski, Andrei and Bacher, Axel and Banderier, Cyril and Gittenberger, Bernhard},
  title =	{{Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{10:1--10:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.10},
  URN =		{urn:nbn:de:0030-drops-89035},
  doi =		{10.4230/LIPIcs.AofA.2018.10},
  annote =	{Keywords: Lattice paths, pattern avoidance, finite automata, context-free languages, autocorrelation, generating function, kernel method, asymptotic analysis, Gaussian limit law}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.11
Periodic Pólya Urns and an Application to Young Tableaux

Authors: Cyril Banderier, Philippe Marchal, and Michael Wallner

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

Abstract
Pólya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial non-linear partial differential equation indeed leads to linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.
Cite as

Cyril Banderier, Philippe Marchal, and Michael Wallner. Periodic Pólya Urns and an Application to Young Tableaux. 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, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2018.11,
  author =	{Banderier, Cyril and Marchal, Philippe and Wallner, Michael},
  title =	{{Periodic P\'{o}lya Urns and an Application to Young Tableaux}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{11:1--11:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.11},
  URN =		{urn:nbn:de:0030-drops-89045},
  doi =		{10.4230/LIPIcs.AofA.2018.11},
  annote =	{Keywords: P\'{o}lya urn, Young tableau, generating functions, analytic combinatorics, pumping moment, D-finite function, hypergeometric function, generalized Gamma distribution, Mittag-Leffler distribution}
}
  • Refine by Author
  • 4 Banderier, Cyril
  • 3 Wallner, Michael
  • 2 Asinowski, Andrei
  • 1 Bacher, Axel
  • 1 Elvey Price, Andrew
  • Show More...

  • Refine by Classification
  • 5 Mathematics of computing → Generating functions
  • 4 Mathematics of computing → Distribution functions
  • 4 Theory of computation → Random walks and Markov chains
  • 3 Theory of computation → Grammars and context-free languages
  • 2 Mathematics of computing → Enumeration
  • Show More...

  • Refine by Keyword
  • 3 generating function
  • 3 kernel method
  • 2 Lattice path
  • 2 algebraic function
  • 2 context-free grammar
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 3 2020
  • 2 2018

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact