Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one-dimensional labels

Abstract

We consider uniform random permutations drawn from a family enumerated through generating trees. We develop a new general technique to establish a central limit theorem for the number of consecutive occurrences of a fixed pattern in such permutations. We propose a technique to sample uniform permutations in such families as conditioned random colored walks. Building on that, we derive the behavior of the consecutive patterns in random permutations studying properties of the consecutive increments in the corresponding random walks. The method applies to families of permutations with a one-dimensional-labeled generating tree (together with some technical assumptions) and implies local convergence for random permutations in such families. We exhibit ten different families of permutations, most of them being permutation classes, that satisfy our assumptions. To the best of our knowledge, this is the first work where generating trees - which were introduced to enumerate combinatorial objects - have been used to establish probabilistic results.

arXiv commentNew version including referee's corrections, accepted for publication in Random Structures & Algorithms

References in corpus (15)

• Random walks in cones
• Berry Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing
• Patterns in random permutations avoiding the pattern 132
• Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• A decorated tree approach to random permutations in substitution-closed classes
• A Central Limit Theorem for Vincular Permutation Patterns
• Local convergence for permutations and local limits for uniform $\rho$-avoiding permutations with $|\rho |=3$
• Generating trees and pattern avoidance in alternating permutations
• Square permutations are typically rectangular
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Central limit theorems for patterns in multiset permutations and set partitions
• On Three Different Notions of Monotone Subsequences
• A code for square permutations and convex permutominoes
• Permutations with few inversions are locally uniform

Cited by in corpus (1)

• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes