## 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}.$

###### 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