---
tag: BS2H0G0T90
kind: definition
name: Random walk on a group
msc: [60B15, 60G50, 20P05]
defines: WAS9EANSJJ
uses: [G5S1M9, 059TJN0NZ1, 0PNRKMRC55, 0G48PYM96Q, 0GYQK9NDJF]
sources:
  - url: https://en.wikipedia.org/wiki/Random_walk
---

## Definition

Let $G$ be a countable [[group|G5S1M9]] with identity $e$, and let $\mu$ be a [[probability measure|059TJN0NZ1]] on $G$.
Let $X_1, X_2, \dots$ be independent [[random variables|0PNRKMRC55]] with values in $G$, each with distribution $\mu$.
The *random walk* on $G$ with step distribution $\mu$ is the sequence $(Z_n)_{n \ge 0}$ with
$$Z_0 = e, \qquad Z_n = X_1 X_2 \cdots X_n \quad (n \ge 1).$$

## Remarks

The sequence $(Z_n)$ is a [[Markov chain|0G48PYM96Q]] on $G$ with transition probabilities $p(g, h) = \mu(g^{-1} h)$.
These satisfy $p(kg, kh) = p(g, h)$ for all $k \in G$.
The distribution of $Z_n$ is the $n$-fold convolution $\mu^{*n}$.

Example: on $\Z^d$, written additively, let $\mu$ give mass $\frac{1}{2d}$ to each of the $2d$ vectors $\pm e_1, \dots, \pm e_d$.
Then $Z_n = X_1 + \cdots + X_n$ is the simple random walk on the lattice $\Z^d$, which is the walk on the [[Cayley graph|0GYQK9NDJF]] for the standard generators.

Non-example: on $\Z$, let $X_1$ be $\pm 1$ with probability $\frac{1}{2}$ each, and let $X_n = X_1$ for all $n$.
Each $X_n$ has the same distribution, but they are not independent, so $Z_n = n X_1$ is not a random walk on $\Z$ in this sense.