Mixing time and cutoff for a random walk on the ring of integers mod \(n\). (English) Zbl 1429.60008

Bate, Michael; Connor, Stephen

Bernoulli 24, No. 2, 993-1009 (2018).

Summary: We analyse a random walk on the ring of integers mod \(n\), which at each time point can make an additive ‘step’ or a multiplicative ‘jump’. When the probability of making a jump tends to zero as an appropriate power of \(n\), we prove the existence of a total variation pre-cutoff for this walk. In addition, we show that the process obtained by subsampling our walk at jump times exhibits a true cutoff, with mixing time dependent on whether the step distribution has zero mean.

MSC:

60B15	Probability measures on groups or semigroups, Fourier transforms, factorization
60B10	Convergence of probability measures
60J10	Markov chains (discrete-time Markov processes on discrete state spaces)

Keywords:

cutoff phenomenon; group representation theory; mixing time; pre-cutoff; random number generation; random walk