The probability of avoiding consecutive patterns in the Mallows distribution. Issue 3 (2nd April 2018)

• Record Type: Journal Article
• Authors: Crane, Harry; DeSalvo, Stephen; Elizalde, Sergi
• Is Part Of: Random structures & algorithms. Volume 53:Issue 3(2018)
• Page Start: 417
• Page End: 447
• Publication Date: 2018-04-02
• Subjects: consecutive pattern -- inversion -- Mallows distribution -- permutation -- Stein's method; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20776
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 π by q 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.