simple random walk

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)

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∈Vd(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.

• When k=1, we may write X_n=Y₁+...+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!

A connection to Brownian motion

Think of simple random walk on Z^d as a measure μ_Z^d 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*Z^d.