{
  "id": "1905.05646",
  "version": "v1",
  "published": "2019-05-14T14:41:54.000Z",
  "updated": "2019-05-14T14:41:54.000Z",
  "title": "Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations",
  "authors": [
    "Toufik Mansour",
    "Reza Rastegar",
    "Alexander Roitershtein"
  ],
  "comment": "33 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "The main theme of this paper is the enumeration of the occurrence of a pattern in words and permutations. We mainly focus on asymptotic properties of the sequence $f_r^v(k,n),$ the number of $n$-array $k$-ary words that contain a given pattern $v$ exactly $r$ times. In addition, we study the asymptotic behavior of the random variable $X_n,$ the number of pattern occurrences in a random $n$-array word. The two topics are closely related through the identity $P(X_n=r) = $ $\\frac{1}{k^n}f_r^v(k,n).$ In particular, we show that for any $r\\geq 0,$ the Stanley-Wilf sequence $\\bigl(f_r^v(k,n)\\bigr)^{1/n}$ converges to a limit independent of $r,$ and determine the value of the limit. We then obtain several limit theorems for the distribution of $X_n,$ including a CLT, large deviation estimates, and the exact growth rate of the entropy of $X_n.$ Furthermore, we introduce a concept of weak avoidance and link it to a certain family of non-product measures on words that penalize pattern occurrences but do not forbid them entirely. We analyze this family of probability measures in a small parameter regime, where the distributions can be understood as a perturbation of a uniform measure. Finally, we extend some of our results for words, including the one regarding the equivalence of the limits of the Stanley-Wilf sequences, to pattern occurrences in permutations.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-14T14:41:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A15",
      "05A16",
      "68Q45",
      "60C05"
    ],
    "keywords": [
      "probabilistic method",
      "occurrence enumeration",
      "finite automata",
      "permutations",
      "pattern occurrences"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}