{
  "id": "2002.09059",
  "version": "v1",
  "published": "2020-02-20T23:18:55.000Z",
  "updated": "2020-02-20T23:18:55.000Z",
  "title": "Three steps mixing for general random walks on the hypercube at criticality",
  "authors": [
    "Andrea Collevecchio",
    "Robert Griffiths"
  ],
  "comment": "27 pages, 1 figure",
  "categories": [
    "math.PR"
  ],
  "abstract": "We introduce a general class of random walks on the $N$-hypercube, study cut-off for the mixing time, and provide several types of representation for the transition probabilities. We observe that for a sub-class of these processes with long range (i.e. non-local) there exists a critical value of the range that allows an \"almost-perfect\" mixing in at most three steps. In other words, the total variation distance between the three steps transition and the stationary distribution decreases geometrically in $N$, which is the dimension of the hypercube. In some cases, the walk mixes almost-perfectly in exactly two steps. Notice that a well-known result (Theorem 1 in Diaconis and Shahshahani (1986)) shows that there exist no random walk on Abelian groups (such as the hypercube) which mixes perfectly in exactly two steps.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-02-20T23:18:55.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60J10"
    ],
    "keywords": [
      "general random walks",
      "steps mixing",
      "criticality",
      "total variation distance",
      "stationary distribution decreases"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}