A Class of Long Range Circulant Random Walks on ${\mathbb{Z}}_q^d$

Abstract

This paper studies a class of long range random walks $(X_t{)}_{t=0}^{\infty }$ on the direct product of cyclic groups ${\mathbb{Z}}_q^d$ for $d\ge 1$ and $q\ge 2$. $X_{t+1}=X_t+Z_t\mathrm{mod}q$, with $(Z_t{)}_{t=1}^{\infty }$ \iid on $\{0,1,\dots ,q-1{\}}^d$. Entries of $Z_t$ are updated by circulant matrices, possibly with dependence. Multiple entries of $Z_t$ can be non-zero in a transition. An emphasis is on finding the structure of such random walks and spectral expansions for the transition functions. An extension is made to processes on a $d$-dimensional torus, scaling entries in $\{0,1,\dots ,q-1\}$ by dividing by $q$ and letting $q\to \infty$. The state space is then $d$ circles of unit perimeter, where $0$ and $1$ are identified as the same point in each circle. If the entries of $X_t$ are exchangeable then a grouping of $X_t$ is made by taking counts of the types $0,\dots ,q-1$ in $X_t$. In this grouping the multivariate Krawtchouk polynomials become the eigenvectors. Examples consider cutoff times and mixing times in these processes. A limit form for the multivariate Krawtchouk polynomials is used to find a central limit theorem for the transition distributions in the grouped model as $d\to \infty$.