{
  "id": "2003.02725",
  "version": "v1",
  "published": "2020-03-05T15:53:55.000Z",
  "updated": "2020-03-05T15:53:55.000Z",
  "title": "Central limit theorems for additive functionals and fringe trees in tries",
  "authors": [
    "Svante Janson"
  ],
  "comment": "74 pages",
  "categories": [
    "math.PR",
    "cs.DS"
  ],
  "abstract": "We give general theorems on asymptotic normality for additive functionals of random tries generated by a sequence of independent strings. These theorems are applied to show asymptotic normality of the distribution of random fringe trees in a random trie. Formulas for asymptotic mean and variance are given. In particular, the proportion of fringe trees of size $k$ (defined as number of keys) is asymptotically, ignoring oscillations, $c/(k(k-1))$ for $k\\ge2$, where $c=1/(1+H)$ with $H$ the entropy of the digits. Another application gives asymptotic normality of the number of $k$-protected nodes in a random trie. For symmetric tries, it is shown that the asymptotic proportion of $k$-protected nodes (ignoring oscillations) decreases geometrically as $k\\to\\infty$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-03-05T15:53:55.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C05",
      "68P05"
    ],
    "keywords": [
      "central limit theorems",
      "additive functionals",
      "random trie",
      "asymptotic normality",
      "random fringe trees"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 74,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}