The-square-and-add Markov chain (Q2153973)

If \(q\) is a prime power, the authors use \(\mathbb{F}_q\) to denote the field with \(q\) elements, and thus if \(p\) is prime, \(\mathbb{F}_p\) is the field of integers modulo \(p\). A simple random walk (drunkard's walk) on \(\mathbb{F}_p\) goes from \(j\) to \(j+1\) or \(j-1\) with probability \(1/2\). As time goes on, this converges to the uniform distribution on \(\mathbb{F}_p\). But the convergence speed is slow and it takes about \(p^2\) steps for this convergence to kick in. Define a new walk as follows (let \(X_0=0\)): \[ X_n=2X_{n-1}+\varepsilon_n\ (\mbox{mod}\ p), \] where \(\varepsilon_n=\pm 1\) with probability \(1/2\) independently from step to step. [\textit{F. R. K. Chung} et al., Ann. Probab. 15, 1148--1165 (1987; Zbl 0622.60016)] showed that order-\(\log(p)\) steps are necessary and sufficient for convergence. Seeking to understand such speedups, the authors consider the random walk \[ X_n=X_{n-1}^2+\varepsilon_n\ (\mbox{mod}\ p). \] As to the above random walk, a little is known. Refer to the end of the paper for some examples and discussions. The main part of the paper considers the corresponding problem over the field \(\mathbb{F}_q\), where \(q=2^d\). Choose a basis \(\mathcal{B}\) for \(\mathbb{F}_q\) over its prime subfield \(\mathbb{F}_2\) such that \(|\mathcal{B}|=d\). Define the random walk on \(\mathbb{F}_q\) by setting \(X_0=0\) and \[ X_n=X_{n-1}^2+\varepsilon_n \] for \(n>0\). Here \(\varepsilon_n\) is randomly chosen from the set \(\{0\}\cup \mathcal{B}\), where the probability that \(\varepsilon_n=0\) is 1/2, and for each element \(\alpha\in \mathcal{B}\), the probability \(\varepsilon_n=\alpha\) is \(\frac{1}{2d}\). The unique stationary distribution for this walk is the uniform distribution and about \(\frac{1}{2}d\log(d)\) steps are necessary and sufficient for convergence under some conditions on \(d\) and the basis \(\mathcal{B}\) (see the main result Theorem 1).