On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes (Q5936463): Difference between revisions

Geometric random walks are defined as certain Markov chains \(X_t\) on a \(d\)-dimensional space over a finite field. The behaviour of such walks is given by certain random matroid processes. In particular, the mixing time is given by expected stopping time, and the cutoff is equivalent to sharp threshold. A collection of examples and symmetric cases are shown, e.g. lazy random walks on a cube, random walks on a complete and edge-transitive graph, on a coordinate subspace and others. Applications to the coupon collector's problem are available. The main point of the paper is methodological. The connection between cutoff phenomenon for mixing of random walks and sharp threshold for random matroids and graphs is established. Several open questions regarding the matter are given.