{
  "id": "math/0609385",
  "version": "v2",
  "published": "2006-09-14T08:09:38.000Z",
  "updated": "2008-01-22T13:37:41.000Z",
  "title": "A functional limit theorem for the profile of search trees",
  "authors": [
    "Michael Drmota",
    "Svante Janson",
    "Ralph Neininger"
  ],
  "comment": "Published in at http://dx.doi.org/10.1214/07-AAP457 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Applied Probability 2008, Vol. 18, No. 1, 288-333",
  "doi": "10.1214/07-AAP457",
  "categories": [
    "math.PR"
  ],
  "abstract": "We study the profile $X_{n,k}$ of random search trees including binary search trees and $m$-ary search trees. Our main result is a functional limit theorem of the normalized profile $X_{n,k}/\\mathbb{E}X_{n,k}$ for $k=\\lfloor\\alpha\\log n\\rfloor$ in a certain range of $\\alpha$. A central feature of the proof is the use of the contraction method to prove convergence in distribution of certain random analytic functions in a complex domain. This is based on a general theorem concerning the contraction method for random variables in an infinite-dimensional Hilbert space. As part of the proof, we show that the Zolotarev metric is complete for a Hilbert space.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-01-22T13:37:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60F17",
      "68Q25",
      "68P10",
      "60C05"
    ],
    "keywords": [
      "functional limit theorem",
      "contraction method",
      "random analytic functions",
      "infinite-dimensional hilbert space",
      "random search trees"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......9385D"
    }
  }
}