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

m a t h b b F_{p}

, where

a i n m a t h b b F_{p}

is fixed and

b_{n}

are independent and identically distributed random variables in

m a t h b b 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 i n m a t h b b F_{p}

. We also obtain weaker, but unconditional, upper bounds for the mixing time.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: Cut-off phenomenon for the \(ax+b\) Markov chain over a finite field