Long jump random walks on finite nilpotent groups

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}}$.
  • Set $\xi_n = s_i^k$


Example

$$G_n = (\Z/ n\Z) \times (\Z/ n\Z) \newcommand{\floor}[1]{\lfloor #1 \rfloor}$$ $$S = (s_1, s_2, s_3)$$ $$\al = (\alpha_1, \alpha_2, \alpha_3)$$

$\begin{align*} s_1 &= (1, 0) &s_2 &= (\floor{\sqrt{n}}, 0)& s_3 &= (0, 1) \\ \alpha_1 &= 1/2 &\alpha_2 &= 1 & \alpha_3 &= 3/2 \end{align*}$

One particular step could go like this:

  1. Choose $s_2$
  2. Choose $k$ from the probability measure $p(k) = \frac{c}{(1+|k|)^{2}}$.
  3. 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*}$

$n$ $s_1$ $s_2$ Diameter
100 1 10 5
100 1 11 ≈1.45
101 1 10 ≈1.45

Thank you!