Mixing time of fractional random walk on finite fields
| Autor: | He, Jimmy, Pham, Huy Tuan, Xu, Max Wenqiang |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We study a random walk on $\mathbb{F}_p$ defined by $X_{n+1}=1/X_n+\varepsilon_{n+1}$ if $X_n\neq 0$, and $X_{n+1}=\varepsilon_{n+1}$ if $X_n=0$, where $\varepsilon_{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. Comment: 17 pages, literature and references updated |
| Databáze: | arXiv |
| Externí odkaz: |
|