A simple random walk on an undirected graph is a Markov chain which, from its current vertex, moves to each
neighboring vertex with equal probability. On the integer
lattice 
, its successive increments are independent and uniformly
distributed over the 
vectors 
.
The simple random walk on 
is recurrent for 
and 2, meaning that it returns to its starting point with
probability 1, and transient for 
. On a finite connected
graph, the stationary probability of a vertex is proportional
to its vertex degree.
