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.
- When k=1, we may write Xn=Y1+...+Yn, where the Yi 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, |Xn| ~ √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 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.