Random walk on the symplectic forms over a finite field
arXiv:1910.10823 · doi:10.5802/alco.131
Abstract
Random transvections generate a walk on the space of symplectic forms on . The main result is establishing cutoff for this Markov chain. After steps, the walk is close to uniform while before , it is far from uniform. The upper bound is proved by explicitly finding and bounding the eigenvalues of the random walk. The lower bound is found by showing that the support of the walk is exponentially small if only steps are taken. The result can be viewed as a -deformation of a result of Diaconis and Holmes on a random walk on matchings.
arXiv commentv2 appendix incorporated into main text, minor changes. 20 pages, 1 figure. Comments are welcome!