{
  "id": "0912.2759",
  "version": "v1",
  "published": "2009-12-14T21:39:29.000Z",
  "updated": "2009-12-14T21:39:29.000Z",
  "title": "Improved mixing time bounds for the Thorp shuffle",
  "authors": [
    "Ben Morris"
  ],
  "comment": "8 pages",
  "categories": [
    "math.PR"
  ],
  "abstract": "E. Thorp introduced the following card shuffling model. Suppose the number of cards $n$ is even. Cut the deck into two equal piles. Drop the first card from the left pile or from the right pile according to the outcome of a fair coin flip. Then drop from the other pile. Continue this way until both piles are empty. We show that if $n$ is a power of 2 then the mixing time of the Thorp shuffle is $O(\\log^3 n)$. Previously, the best known bound was $O(\\log^4 n)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-12-14T21:39:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60J10"
    ],
    "keywords": [
      "mixing time bounds",
      "thorp shuffle",
      "fair coin flip",
      "equal piles",
      "first card"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0912.2759M"
    }
  }
}