{
  "id": "0910.1077",
  "version": "v3",
  "published": "2009-10-06T19:21:01.000Z",
  "updated": "2010-07-14T18:34:14.000Z",
  "title": "Discrete low-discrepancy sequences",
  "authors": [
    "Omer Angel",
    "Alexander E. Holroyd",
    "James B. Martin",
    "James Propp"
  ],
  "comment": "Since posting the preprint, we have learned that our main result was proved by Tijdeman in the 1970s and that his proof is the same as ours",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "Holroyd and Propp used Hall's marriage theorem to show that, given a probability distribution pi on a finite set S, there exists an infinite sequence s_1,s_2,... in S such that for all integers k >= 1 and all s in S, the number of i in [1,k] with s_i = s differs from k pi(s) by at most 1. We prove a generalization of this result using a simple explicit algorithm. A special case of this algorithm yields an extension of Holroyd and Propp's result to the case of discrete probability distributions on infinite sets.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2010-07-14T18:34:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "82C20",
      "20K01",
      "05C25"
    ],
    "keywords": [
      "discrete low-discrepancy sequences",
      "probability distribution pi",
      "simple explicit algorithm",
      "discrete probability distributions",
      "halls marriage theorem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0910.1077A"
    }
  }
}