{
  "id": "math/0510663",
  "version": "v2",
  "published": "2005-10-31T01:46:32.000Z",
  "updated": "2005-11-01T21:05:30.000Z",
  "title": "Avoiding defeat in a balls-in-bins process with feedback",
  "authors": [
    "Roberto Oliveira",
    "Joel Spencer"
  ],
  "comment": "30 pages; to be submitted. V.2 has some minor corrections",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Imagine that there are two bins to which balls are added sequentially, and each incoming ball joins a bin with probability proportional to the p-th power of the number of balls already there. A general result says that if p>1/2, there almost surely is some bin that will have more balls than the other at all large enough times, a property that we call eventual leadership. In this paper, we compute the asymptotics of the probability that bin 1 eventually leads when the total initial number of balls $t$ is large and bin 1 has a fraction \\alpha<1/2 of the balls; in fact, this probability is \\exp(c_p(\\alpha)t + O{t^{2/3}}) for some smooth, strictly negative function c_p. Moreover, we show that conditioned on this unlikely event, the fraction of balls in the first bin can be well-approximated by the solution to a certain ordinary differential equation.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-11-01T21:05:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60J10",
      "60J20"
    ],
    "keywords": [
      "balls-in-bins process",
      "avoiding defeat",
      "ordinary differential equation",
      "general result says",
      "total initial number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math.....10663O"
    }
  }
}