Yuwen Wang
(joint work with Laurent Saloff-Coste)
Cornell University

Fingerlakes probability seminar | April 19, 2019

Long jump random walk on finite groups

Let $G$ be a finite group, $S = (s_1, s_2, \dotsb, s_k)$ be a generating set. Let $\def\al{{\bf{\unicode{x3B1}}}}\al= (\alpha_1, \dotsb, \alpha_k)$, where $\alpha_i \in (0, 2)$.

The long jump random walk on $G$ associated with $S$ and $\al$ is defined to be $\{X_n\}$, where $X_0 = e$ and

\[ X_n = \xi_1 \xi_2 \dotsb \xi_n, \]

and $\xi_n$ is an i.i.d. random variable chosen as follows:

Uniformly choose $s_i$ from $S$

Choose $k$ according to the probability measure on $\def\Z{\mathbb{Z}}\Z$: $p(k) = \frac{c_{\alpha_i}}{(1+|k|)^{1+\alpha_i}}$.

Choose $k$ from the probability measure $p(k) = \frac{c}{(1+|k|)^{2}}$.

Add $(k \floor{\sqrt{n}}, 0)$ to the previous position.

Question

Consider any simple random walk on a finite abelian group $G$ with generating set $S$.
We know that the mixing time is comparable to $\text{diam}(G)^2$.
What is the mixing time with the long jump modification with $\al$?

Main result

If $G$ is a finite abelian group and a generating set $S$ of bounded size, then the mixing time is comparable to a computable quantity in terms $S$ and $\al$, $D_{S,\al}$.

Definition of $D_{S,\al}$

Define the cost of $g$ to be

\[ ||g||_{S,\al} = \min_{\substack{m_1, \dotsc, m_k : \\ g = m_1 s_1 + \dotsb + m_k s_k}} \max_{i} |m_i|^{\alpha_i} \]
and the diameter to be

\[D_{S,\al} = \max_{g \in G} ||g||_{S,\al}.\]

When $\alpha_i > 2$, we can recover the simple random walk.

We can generalize the cost and result for finite nilpotent groups.

$G = \Z/25\Z$
$S = (1, 5)$
$\al = (1,1)$

Compute cost:

$B(e,0)$

$B(e,1)$

$B(e,2)$

$D_{S,\al} = 2$

Some examples

$\begin{align*} G = \Z/n\Z \qquad \al = (1, 1/10). \end{align*}$