Mixing time of fractional random walk on finite fields

DOI10.1214/22-EJP858zbMath1498.60305arXiv2102.02781MaRDI QIDQ2084834

Max Wenqiang Xu, Jimmy He, Huy-Tuan Pham

Publication date: 13 October 2022

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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

zbMATH Keywords

finite field; spectral gap; mixing times

Mathematics Subject Classification ID

60G50: Sums of independent random variables; random walks

60J10: Markov chains (discrete-time Markov processes on discrete state spaces)

05C25: Graphs and abstract algebra (groups, rings, fields, etc.)

11T23: Exponential sums

05C81: Random walks on graphs

Related Items

On the multiplicative Chung-Diaconis-Graham process, Accelerating abelian random walks with hyperbolic dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expansion in \(\text{SL}_d(\mathbb Z/q\mathbb Z)\), \(q\) arbitrary.
• Strong uniform expansion in \(\text{SL}(2,p)\).
• Concentration of points on two and three dimensional modular hyperbolas and applications
• Affine linear sieve, expanders, and sum-product
• Comparison theory for Markov chains on different state spaces and application to random walk on derangements
• Random walks arising in random number generation
• Comparison theorems for reversible Markov chains
• Comparison techniques for random walk on finite groups
• Cutoff at the ``entropic time for sparse Markov chains
• Expansion in perfect groups.
• Spectral gap of sparse bistochastic matrices with exchangeable rows
• Cut-off phenomenon for the \(ax+b\) Markov chain over a finite field
• Universality of cutoff for graphs with an added random matching
• Markov chains on finite fields with deterministic jumps
• Cutoff on graphs and the Sarnak-Xue density of eigenvalues
• Speeding up Markov chains with deterministic jumps
• Modular hyperbolas and bilinear forms of Kloosterman sums
• On a lower bound for the Chung-Diaconis-Graham random process
• Growth and generation in \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\).
• Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).
• Saving the logarithmic factor in the error term estimates of some congruence problems
• On the Chung-Diaconis-Graham random process
• Mixing time of the Chung-Diaconis-Graham random process
• Zariski Density and Genericity
• On the logarithmic factor in error term estimates in certain additive congruence problems
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• A lower bound for the Chung-Diaconis-Graham random process
• Mathematics and Computation
• A sharp continuity estimate for the von Neumann entropy
• On the concentration of points on modular hyperbolas and exponential curves