{
  "id": "1805.10653",
  "version": "v1",
  "published": "2018-05-27T16:57:28.000Z",
  "updated": "2018-05-27T16:57:28.000Z",
  "title": "Preferential Attachment When Stable",
  "authors": [
    "Svante Janson",
    "Subhabrata Sen",
    "Joel Spencer"
  ],
  "comment": "44 pages",
  "categories": [
    "math.PR",
    "cs.DM",
    "math.CO"
  ],
  "abstract": "We study an urn process with two urns, initialized with a ball each. Balls are added sequentially, the urn being chosen independently with probability proportional to the $\\alpha^{th}$ power $(\\alpha >1)$ of the existing number of balls. We study the (rare) event that the urn compositions are balanced after the addition of $2n-2$ new balls. We derive precise asymptotics of the probability of this event by embedding the process in continuous time. Quite surprisingly, a fine control on this probability may be leveraged to derive a lower tail Large Deviation Principle (LDP) for $L = \\sum_{i=1}^{n} \\frac{S_i^2}{i^2}$, where $\\{S_n : n \\geq 0\\}$ is a simple symmetric random walk started at zero. We provide an alternate proof of the LDP via coupling to Brownian motion, and subsequent derivation of the LDP for a continuous time analogue of $L$. Finally, we turn our attention back to the urn process conditioned to be balanced, and provide a functional limit law describing the trajectory of the urn process.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-27T16:57:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60F10",
      "60F17",
      "60C05"
    ],
    "keywords": [
      "preferential attachment",
      "urn process",
      "lower tail large deviation principle",
      "simple symmetric random walk",
      "functional limit law"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 44,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}