Random walk on the symplectic forms over a finite field. (English) Zbl 1460.60003
Summary: Random transvections generate a walk on the space of symplectic forms on \(\mathbb{F}_q^{2n} \). 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.
MSC:
| 60B15 | Probability measures on groups or semigroups, Fourier transforms, factorization |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 60G50 | Sums of independent random variables; random walks |
References:
| [1] | Bannai, Eiichi; Kawanaka, Noriaki; Song, Sung-Yell, The character table of the Hecke algebra \(\mathscr{H}(\text{GL}_{2n}(\mathbf{F}_q),\text{Sp}_{2n}(\mathbf{F}_q))\), J. Algebra, 129, 2, 320-366 (1990) · Zbl 0761.20013 · doi:10.1016/0021-8693(90)90224-C |
| [2] | Ceccherini-Silberstein, Tullio; Scarabotti, Fabio; Tolli, Filippo, Harmonic analysis on finite groups: Representation theory, Gelfand pairs and Markov chains, 108, xiv+440 p. pp. (2008), Cambridge University Press, Cambridge · Zbl 1149.43001 · doi:10.1017/CBO9780511619823 |
| [3] | Diaconis, Persi, Group representations in probability and statistics, 11, vi+198 p. pp. (1988), Institute of Mathematical Statistics, Hayward, CA · Zbl 0695.60012 |
| [4] | Diaconis, Persi; Holmes, Susan P., Random walks on trees and matchings, Electron. J. Probab., 7, 17 p. pp. (2002) · Zbl 1007.60071 · doi:10.1214/EJP.v7-105 |
| [5] | Diaconis, Persi; Saloff-Coste, Laurent, Comparison theorems for reversible Markov chains, Ann. Appl. Probab., 3, 3, 696-730 (1993) · Zbl 0799.60058 · doi:10.1214/aoap/1177005359 |
| [6] | Diaconis, Persi; Shahshahani, Mehrdad, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete, 57, 2, 159-179 (1981) · Zbl 0485.60006 · doi:10.1007/BF00535487 |
| [7] | Diaconis, Persi; Shahshahani, Mehrdad, Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM J. Math. Anal., 18, 1, 208-218 (1987) · Zbl 0617.60009 · doi:10.1137/0518016 |
| [8] | Green, James A., The characters of the finite general linear groups, Trans. Amer. Math. Soc., 80, 2, 402-447 (1955) · Zbl 0068.25605 · doi:10.1090/S0002-9947-1955-0072878-2 |
| [9] | He, Jimmy, A characteristic map for the symmetric space of symplectic forms over a finite field (2019) · Zbl 1447.05209 |
| [10] | Hildebrand, Martin, Generating random elements in \({\text{SL}}_n(\mathbf{F}_q)\) by random transvections, J. Algebraic Combin., 1, 2, 133-150 (1992) · Zbl 0766.60089 · doi:10.1023/A:1022472220105 |
| [11] | Levin, David A.; Peres, Yuval, Markov Chains and Mixing Times (2017), American Mathematical Society: American Mathematical Society, Providence, RI · Zbl 1391.60175 |
| [12] | Macdonald, Ian G., Symmetric functions and Hall polynomials, viii+180 p. pp. (1979), The Clarendon Press, Oxford University Press: The Clarendon Press, Oxford University Press, New York · Zbl 0487.20007 |
| [13] | Méliot, Pierre-Loïc, The cut-off phenomenon for Brownian motions on compact symmetric spaces, Potential Anal., 40, 4, 427-509 (2014) · Zbl 1295.58011 · doi:10.1007/s11118-013-9356-7 |
| [14] | O’Meara, O. Timothy, Symplectic groups, 16, xi+122 p. pp. (1978), American Mathematical Society: American Mathematical Society, Providence, R.I. · Zbl 0383.20001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
