{
  "id": "math/0508451",
  "version": "v1",
  "published": "2005-08-24T11:58:39.000Z",
  "updated": "2005-08-24T11:58:39.000Z",
  "title": "On the power of two choices: Balls and bins in continuous time",
  "authors": [
    "Malwina J. Luczak",
    "Colin McDiarmid"
  ],
  "comment": "Published at http://dx.doi.org/10.1214/105051605000000205 in 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 2005, Vol. 15, No. 3, 1733-1764",
  "doi": "10.1214/105051605000000205",
  "categories": [
    "math.PR"
  ],
  "abstract": "Suppose that there are n bins, and balls arrive in a Poisson process at rate \\lambda n, where \\lambda >0 is a constant. Upon arrival, each ball chooses a fixed number d of random bins, and is placed into one with least load. Balls have independent exponential lifetimes with unit mean. We show that the system converges rapidly to its equilibrium distribution; and when d\\geq 2, there is an integer-valued function m_d(n)=\\ln \\ln n/\\ln d+O(1) such that, in the equilibrium distribution, the maximum load of a bin is concentrated on the two values m_d(n) and m_d(n)-1, with probability tending to 1, as n\\to \\infty. We show also that the maximum load usually does not vary by more than a constant amount from \\ln \\ln n/\\ln d, even over quite long periods of time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2005-08-24T11:58:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "68R05",
      "90B80",
      "60K35",
      "60K30"
    ],
    "keywords": [
      "continuous time",
      "equilibrium distribution",
      "maximum load",
      "quite long periods",
      "independent exponential lifetimes"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......8451L"
    }
  }
}