Random walk on the symplectic forms over a finite field

DOI10.5802/ALCO.131MaRDI QIDQ2004049zbMATH OpenOpenAlexFDO

Authors Jimmy He

Publication date 14 October 2020

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.10823

zbMATH Keywords

characteristic mapGelfand pairMarkov chainsymmetric functions

Mathematics Subject Classification ID

Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Random transvections generate a walk on the space of symplectic forms on $mathbf{F}_q^{2n}$. The main result is establishing cutoff for this Markov chain. After $n+c$ steps, the walk is close to uniform while before $n-c$, 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.

Recommendations

• Generating random elements in \(SL_ n(F_ q)\) by random transvections
• Enumeration and random walks on finite groups
• The random k cycle walk on the symmetric group
• The cut-off phenomenon for random reflections
• Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique

Cites work

• A characteristic map for the symmetric space of symplectic forms over a finite field
• Comparison theorems for reversible Markov chains
• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• Generating a random permutation with random transpositions
• Generating random elements in \(SL_ n(F_ q)\) by random transvections
• Harmonic analysis on finite groups. Representation theory, Gelfand pairs and Markov chains
• scientific article; zbMATH DE number 3766017 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 3595390 (Why is no real title available?)
• Random walks on trees and matchings
• The character table of the Hecke algebra \({\mathcal H}(GL_{2n}(\mathbb{F}_ q),Sp_{2n}(\mathbb{F}_ q))\)
• The Characters of the Finite General Linear Groups
• The cut-off phenomenon for Brownian motions on compact symmetric spaces
• Time to Reach Stationarity in the Bernoulli–Laplace Diffusion Model

Cited in

(4)

• Generating random elements in \(SL_ n(F_ q)\) by random transvections
• The nearest neighbor random walk on subspaces of a vector space and rate of convergence
• Statistical enumeration of groups by double cosets
• scientific article; zbMATH DE number 1058075 (Why is no real title available?)

This page was built for publication: Random walk on the symplectic forms over a finite field

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2004049)