• Mathematics of computing → Generating functions
  • Mathematics of computing → Distribution functions
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Grammars and context-free languages
Andrei Asinowski
University of Klagenfurt, Austria
Cyril Banderier
Université Paris 13 (LIPN, UMR CNRS 7030), France

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.