Premium
The probability of avoiding consecutive patterns in the Mallows distribution
Author(s) -
Crane Harry,
DeSalvo Stephen,
Elizalde Sergi
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20776
Subject(s) - permutation (music) , mathematics , combinatorics , monotone polygon , distribution (mathematics) , weighting , random permutation , uniform distribution (continuous) , probability distribution , statistics , discrete mathematics , mathematical analysis , symmetric group , geometry , medicine , physics , acoustics , radiology
We use combinatorial and probabilistic techniques to study growth rates for the probability that a random permutation from the Mallows distribution avoids consecutive patterns. The Mallows distribution is a q ‐analogue of the uniform distribution weighting each permutation π byq inv ( π ), where inv ( π ) is the number of inversions in π and q is a positive, real‐valued parameter. We prove that the growth rate exists for all patterns and all q > 0, and we generalize Goulden and Jackson's cluster method to keep track of the number of inversions in permutations avoiding a given consecutive pattern. Using singularity analysis, we approximate the growth rates for length‐3 patterns, monotone patterns, and non‐overlapping patterns starting with 1, and we compare growth rates between different patterns. We also use Stein's method to show that, under certain assumptions on q and σ, the number of occurrences of a given pattern σ is well approximated by the normal distribution.