License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2020.1
URN: urn:nbn:de:0030-drops-120317
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12031/
Go to the corresponding LIPIcs Volume Portal

Asinowski, Andrei ; Banderier, Cyril

On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution

pdf-format:
LIPIcs-AofA-2020-1.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{asinowski_et_al:LIPIcs:2020:12031,
  author =	{Andrei Asinowski and Cyril Banderier},
  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 =	{Michael Drmota and Clemens Heuberger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12031},
  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}
}

Keywords: Lattice path, Dyck path, Motzkin path, generating function, algebraic function, kernel method, context-free grammar, multivariate Gaussian distribution
Collection: 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Issue Date: 2020
Date of publication: 10.06.2020

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