The probability of avoiding consecutive patterns in the Mallows distribution

Harry Crane, Stephen DeSalvo, Sergi Elizalde

Research output: Contribution to journalArticle

1 Citation (Scopus)

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.

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

Fingerprint

Consecutive
Normal distribution
Inversion
Permutation
Stein's Method
Singularity Analysis
Random Permutation
Q-analogue
Uniform distribution
Weighting
Gaussian distribution
Monotone
Generalise

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

Cite this

Crane, Harry ; DeSalvo, Stephen ; Elizalde, Sergi. / The probability of avoiding consecutive patterns in the Mallows distribution. In: Random Structures and Algorithms. 2018 ; Vol. 53, No. 3. pp. 417-447.
@article{f15204703d0041e182011d1e4b8ee908,
title = "The probability of avoiding consecutive patterns in the Mallows distribution",
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.",
keywords = "Mallows distribution, Stein's method, consecutive pattern, inversion, permutation",
author = "Harry Crane and Stephen DeSalvo and Sergi Elizalde",
year = "2018",
month = "10",
day = "1",
doi = "10.1002/rsa.20776",
language = "English (US)",
volume = "53",
pages = "417--447",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Ltd",
number = "3",

}

The probability of avoiding consecutive patterns in the Mallows distribution. / Crane, Harry; DeSalvo, Stephen; Elizalde, Sergi.

In: Random Structures and Algorithms, Vol. 53, No. 3, 01.10.2018, p. 417-447.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The probability of avoiding consecutive patterns in the Mallows distribution

AU - Crane, Harry

AU - DeSalvo, Stephen

AU - Elizalde, Sergi

PY - 2018/10/1

Y1 - 2018/10/1

N2 - 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.

AB - 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.

KW - Mallows distribution

KW - Stein's method

KW - consecutive pattern

KW - inversion

KW - permutation

UR - http://www.scopus.com/inward/record.url?scp=85044775127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85044775127&partnerID=8YFLogxK

U2 - 10.1002/rsa.20776

DO - 10.1002/rsa.20776

M3 - Article

AN - SCOPUS:85044775127

VL - 53

SP - 417

EP - 447

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 3

ER -