{
  "id": "1609.01370",
  "version": "v1",
  "published": "2016-09-06T02:05:20.000Z",
  "updated": "2016-09-06T02:05:20.000Z",
  "title": "The probability of avoiding consecutive patterns in the Mallows distribution",
  "authors": [
    "Harry Crane",
    "Stephen DeSalvo",
    "Sergi Elizalde"
  ],
  "comment": "34 pages, 12 figures",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We use various 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 behaves like a $q$-analogue of the uniform distribution by weighting each permutation $\\pi$ by $q^{inv(\\pi)}$, where $inv(\\pi)$ is the number of inversions in $\\pi$ 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$, the length of $\\sigma$, and $inv(\\sigma)$, the number of occurrences of a given pattern $\\sigma$ is well approximated by the normal distribution.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-09-06T02:05:20.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "60C05",
      "05A15",
      "05A16",
      "62E17",
      "62E20",
      "05A30"
    ],
    "keywords": [
      "avoiding consecutive patterns",
      "probability",
      "mallows distribution avoids consecutive patterns",
      "permutation",
      "mallows distribution behaves"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}