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{Xn+1=v | Xn=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∈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 Zk. Since this graph is transitive, the starting vertex makes absolutely no difference, and we assume X0=0.

A connection to Brownian motion

Think of simple random walk on Zd as a measure μZd on paths on Rd (of course, only "quantized" paths which take steps along the grid are taken into account). Now consider the sequence of graphs Zd, 0.5*Zd, 0.25*Zd, ..., 2-k*Zd, each as a subgraph of the next (we're approximating Rd 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.

Log in or register to write something here or to contact authors.