The probability of avoiding consecutive patterns in the Mallows distribution

Harry Crane, Stephen DeSalvo, Sergi Elizalde

Research output: Contribution to journalArticle

3 Scopus citations

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 qinv(π), 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.

Original languageEnglish (US)
Pages (from-to)417-447
Number of pages31
JournalRandom Structures and Algorithms
Volume53
Issue number3
DOIs
StatePublished - Oct 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • Mallows distribution
  • Stein's method
  • consecutive pattern
  • inversion
  • permutation

Fingerprint Dive into the research topics of 'The probability of avoiding consecutive patterns in the Mallows distribution'. Together they form a unique fingerprint.

  • Cite this