zbMATH — the first resource for mathematics

Mixing time and cutoff for a random walk on the ring of integers mod \(n\). (English) Zbl 1429.60008
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.

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)
Full Text: DOI Euclid