Cut-off phenomenon for the ax+b Markov chain over a finite field

Abstract

We study the Markov chain $x_{n+1}=a{x}_n+b_n$ on a finite field ${\mathbb{F}}_p$, where $a\in {\mathbb{F}}_p$ is fixed and $b_n$ are independent and identically distributed random variables in ${\mathbb{F}}_p$. Conditionally on the Riemann hypothesis for all Dedekind zeta functions, we show that the chain exhibits a cut-off phenomenon for most primes $p$ and most values of $a\in {\mathbb{F}}_p$. We also obtain weaker, but unconditional, upper bounds for the mixing time.

arXiv comment27 pages, final accepted version, revision based on referee's comments, improved presentation, to appear in Probab. Theory Related Fields