Simple random walk

A simple random walk on a locally finite graph chooses each neighbouring vertex with equal probability.

On the $n$-dimensional hypercube graph, simple random walk flips one uniformly chosen coordinate at each step. Its stationary distribution is uniform on the $2^n$ vertices, so its mean return time is $2^n$.

For random walk on $\{-1,1{\}}^n$ that chooses a coordinate uniformly and flips it with probability $1/2$, the Walsh characters $f_J(x)={\prod }_{j\in J}{x}_j$ form an orthonormal eigenbasis under the uniform distribution on a finite set. Flipping a coordinate in $J$ negates $f_J$, so $P{f}_J=(1-|J|/n)f_J$. Hence $1-k/n$ has multiplicity $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, and the ordinary and absolute spectral gaps both equal $1/n$.

A simple random walk on ${\mathbb{Z}}^2$ visits its starting point infinitely often almost surely and hits every fixed vertex almost surely.