Random walk on the symplectic forms over a finite field

He, Jimmy

doi:10.5802/alco.131

He, Jimmy ¹

¹ Department of Mathematics Stanford University Stanford, CA 94305, USA

Algebraic Combinatorics, Volume 3 (2020) no. 5, pp. 1165-1181.

Abstract

Random transvections generate a walk on the space of symplectic forms on $F_{q}^{2 n}$ . The main result is to establish cutoff for this Markov chain. After $n + c$ steps, the walk is close to uniform while before $n - c$ 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 $n - c$ steps are taken. The result can be viewed as a $q$ -deformation of a result of Diaconis and Holmes on a random walk on matchings.

Received: 2019-11-20
Revised: 2020-06-09
Accepted: 2020-06-09
Published online: 2020-10-12

DOI: 10.5802/alco.131

Classification: 60J10, 60B15, 20C33
Keywords: Markov Chain, Gelfand Pair, Characteristic map, Symmetric functions

Author's affiliations:

He, Jimmy ¹

¹ Department of Mathematics Stanford University Stanford, CA 94305, USA

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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 = {https://alco.centre-mersenne.org/articles/10.5802/alco.131/}
}

TY  - JOUR
AU  - He, Jimmy
TI  - Random walk on the symplectic forms over a finite field
JO  - Algebraic Combinatorics
PY  - 2020
SP  - 1165
EP  - 1181
VL  - 3
IS  - 5
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.131/
DO  - 10.5802/alco.131
LA  - en
ID  - ALCO_2020__3_5_1165_0
ER  -

%0 Journal Article
%A He, Jimmy
%T Random walk on the symplectic forms over a finite field
%J Algebraic Combinatorics
%D 2020
%P 1165-1181
%V 3
%N 5
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.131/
%R 10.5802/alco.131
%G en
%F 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/articles/10.5802/alco.131/

References
Cited by

[1] Bannai, Eiichi; Kawanaka, Noriaki; Song, Sung-Yell The character table of the Hecke algebra $ℋ ({GL}_{2 n} (F_{q}), {Sp}_{2 n} (F_{q}))$ , J. Algebra, Volume 129 (1990) no. 2, pp. 320-366 | DOI | MR | Zbl

[2] Ceccherini-Silberstein, Tullio; Scarabotti, Fabio; Tolli, Filippo Harmonic analysis on finite groups: Representation theory, Gelfand pairs and Markov chains, Cambridge Studies in Advanced Mathematics, 108, Cambridge University Press, Cambridge, 2008, xiv+440 pages | DOI | Zbl

[3] Diaconis, Persi Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Institute of Mathematical Statistics, Hayward, CA, 1988, vi+198 pages | MR | Zbl

[4] Diaconis, Persi; Holmes, Susan P. Random walks on trees and matchings, Electron. J. Probab., Volume 7 (2002), Paper no. no. 6, 17 pages | DOI | MR | Zbl

[5] Diaconis, Persi; Saloff-Coste, Laurent Comparison theorems for reversible Markov chains, Ann. Appl. Probab., Volume 3 (1993) no. 3, pp. 696-730 | DOI | MR | Zbl

[6] Diaconis, Persi; Shahshahani, Mehrdad Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete, Volume 57 (1981) no. 2, pp. 159-179 | DOI | MR | Zbl

[7] Diaconis, Persi; Shahshahani, Mehrdad Time to reach stationarity in the Bernoulli–Laplace diffusion model, SIAM J. Math. Anal., Volume 18 (1987) no. 1, pp. 208-218 | DOI | MR | Zbl

[8] Green, James A. The characters of the finite general linear groups, Trans. Amer. Math. Soc., Volume 80 (1955) no. 2, pp. 402-447 | DOI | MR | Zbl

[9] He, Jimmy A characteristic map for the symmetric space of symplectic forms over a finite field (2019) (https://arxiv.org/abs/1906.05966)

[10] Hildebrand, Martin Generating random elements in ${SL}_{n} (F_{q})$ by random transvections, J. Algebraic Combin., Volume 1 (1992) no. 2, pp. 133-150 | DOI | MR | Zbl

[11] Levin, David A.; Peres, Yuval Markov Chains and Mixing Times, American Mathematical Society, Providence, RI, 2017

[12] Macdonald, Ian G. Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979, viii+180 pages | Zbl

[13] Méliot, Pierre-Loïc The cut-off phenomenon for Brownian motions on compact symmetric spaces, Potential Anal., Volume 40 (2014) no. 4, pp. 427-509 | DOI | MR | Zbl

[14] O’Meara, O. Timothy Symplectic groups, Mathematical Surveys, 16, American Mathematical Society, Providence, R.I., 1978, xi+122 pages | MR | Zbl

Cited by Sources: