Random walks on finite fields

Random walks on finite fields

-
Peter Varju, Cambridge University
Fine Hall 214

Let p be a prime and denote by F_p the finite field of order p. I will discuss estimates for the mixing time of the random walk on F_p with steps given by x -> a x + A_n, where a is a fixed element of F_p and A_n is a sequence of i.i.d. random elements of F_p.

This problem has been well studied in the case, when a is a fixed small (compared to p) integer. In particular, Chung, Diaconis and Graham considered the case a=2 and their work has been subsequently extended and refined by Hildebrand.

The talk will focus on the case, when a is allowed to vary with p. One of the results I will discuss asserts that for most choices of the prime p and for most choices of a in F_p, the random walk exhibits the cut-off phenomenon provided GRH holds. This is a joint work with Emmanuel Breuillard.