The most common type of random walk is *simple* random walk, or SRW. SRW goes independently and uniformly to any of the current vertex's neighbours in the graph. So

p(u,v) = P{X_{n+1}=v | X_{n}=u} = 1/d(u)

where d(u) is the

degree (number of neighbours) of u.

Very much indeed is known about SRW; the rest of this writeup gives some examples.

When G is finite, if simple random walk is ergodic (see random walk for conditions on G -- basically G must be connected and not bipartite) it is particularly easy to express the stationary distribution: p(u)=d(u)/Z, where Z=|E|/2=∑_{u∈V}d(u). In other words, the asymptotic probability of finding the random walk at a vertex u is directly proportional to its degree. In terms of edges, simple random walk on a finite graph traverses each edge equally.

The most famous G's on which SRW has been studied are of course the k-dimensional grids **Z**^{k}. Since this graph is transitive, the starting vertex makes absolutely no difference, and we assume X_{0}=0.

- When k=1, we may write X
_{n}=Y_{1}+...+Y_{n}, where the Y_{i} are IID Bernoulli random variables which are +1 with probability 1/2 and -1 with probability 1/2. The central limit theorem and various theorems about large deviations give a precise description of where we expect to find the random walk: after n steps, |X_{n}| ~ √n with high probability. Naturally, this SRW is recurrent.
- When k=2, SRW is still recurrent; the expected return time to the origin is, however, infinite.
- When k≥3, SRW is transient: almost surely, it will visit any given point only finitely many points, and it will
*not* visit all points!

Think of simple random walk on **Z**^{d} as a measure μ_{Zd} on paths on **R**^{d} (of course, only "quantized" paths which take steps along the grid are taken into account). Now consider the sequence of graphs **Z**^{d}, 0.5***Z**^{d}, 0.25***Z**^{d}, ..., 2^{-k}***Z**^{d}, each as a subgraph of the next (we're approximating **R**^{d} by progressively finer grids). Then it can be shown that Brownian motion is in fact a limit (in some appropriate sense) of these measures μ_{2-k*Zd}.