Random transvections generate a walk on the space of symplectic forms on . The main result is to establish cutoff for this Markov chain. After steps, the walk is close to uniform while before steps, 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.
Revised: 2020-06-09
Accepted: 2020-06-09
Published online: 2020-10-12
Classification: 60J10, 60B15, 20C33
Keywords: Markov Chain, Gelfand Pair, Characteristic map, Symmetric functions
@article{ALCO_2020__3_5_1165_0, author = {He, Jimmy}, title = {Random walk on the symplectic forms over a finite field}, journal = {Algebraic Combinatorics}, pages = {1165--1181}, publisher = {MathOA foundation}, volume = {3}, number = {5}, year = {2020}, doi = {10.5802/alco.131}, language = {en}, url = {alco.centre-mersenne.org/item/ALCO_2020__3_5_1165_0/} }
He, Jimmy. Random walk on the symplectic forms over a finite field. Algebraic Combinatorics, Volume 3 (2020) no. 5, pp. 1165-1181. doi : 10.5802/alco.131. https://alco.centre-mersenne.org/item/ALCO_2020__3_5_1165_0/
[1] The character table of the Hecke algebra , J. Algebra, Volume 129 (1990) no. 2, pp. 320-366 | Article | MR 1040942 | Zbl 0761.20013
[2] Harmonic analysis on finite groups: Representation theory, Gelfand pairs and Markov chains, Cambridge Studies in Advanced Mathematics, Volume 108, Cambridge University Press, Cambridge, 2008, xiv+440 pages | Article | Zbl 1149.43001
[3] Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, Volume 11, Institute of Mathematical Statistics, Hayward, CA, 1988, vi+198 pages | MR 964069 | Zbl 0695.60012
[4] Random walks on trees and matchings, Electron. J. Probab., Volume 7 (2002), no. 6, 17 pages | Article | MR 1887626 | Zbl 1007.60071
[5] Comparison theorems for reversible Markov chains, Ann. Appl. Probab., Volume 3 (1993) no. 3, pp. 696-730 | Article | MR 1233621 | Zbl 0799.60058
[6] Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete, Volume 57 (1981) no. 2, pp. 159-179 | Article | MR 626813 | Zbl 0485.60006
[7] Time to reach stationarity in the Bernoulli–Laplace diffusion model, SIAM J. Math. Anal., Volume 18 (1987) no. 1, pp. 208-218 | Article | MR 871832 | Zbl 0617.60009
[8] The characters of the finite general linear groups, Trans. Amer. Math. Soc., Volume 80 (1955) no. 2, pp. 402-447 | Article | MR 72878 | Zbl 0068.25605
[9] A characteristic map for the symmetric space of symplectic forms over a finite field (2019) (https://arxiv.org/abs/1906.05966)
[10] Generating random elements in by random transvections, J. Algebraic Combin., Volume 1 (1992) no. 2, pp. 133-150 | Article | MR 1226348 | Zbl 0766.60089
[11] Markov Chains and Mixing Times, American Mathematical Society, Providence, RI, 2017
[12] Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979, viii+180 pages | Zbl 0487.20007
[13] The cut-off phenomenon for Brownian motions on compact symmetric spaces, Potential Anal., Volume 40 (2014) no. 4, pp. 427-509 | Article | MR 3201989 | Zbl 1295.58011
[14] Symplectic groups, Mathematical Surveys, Volume 16, American Mathematical Society, Providence, R.I., 1978, xi+122 pages | MR 502254 | Zbl 0383.20001