Mixing time of fractional random walk on finite fields

Abstract

We study a random walk on ${\mathbb{F}}_p$ defined by $X_{n+1}=1/X_n+{\epsilon }_{n+1}$ if $X_n\ne 0$, and $X_{n+1}={\epsilon }_{n+1}$ if $X_n=0$, where ${\epsilon }_{n+1}$ are independent and identically distributed. This can be seen as a non-linear analogue of the Chung--Diaconis--Graham process. We show that the mixing time is of order $\log p$, answering a question of Chatterjee and Diaconis.

17 pages, literature and references updated

References in corpus (1)

• A Sharp Fannes-type Inequality for the von Neumann Entropy