Random walk on a graph

A random walk on a graph moves along an incident edge at each step.

An undirected graph may have repeated edges. Choosing an incident edge uniformly gives transition probability equal to the edge multiplicity divided by the vertex degree. Its stationary probability is proportional to degree and its stationary fluxes are symmetric, making it a reversible Markov chain.

A connected locally finite graph is recurrent if its simple random walk returns to its starting vertex almost surely. In that case the walk hits every fixed vertex almost surely from every starting vertex.

A weighted graph assigns a symmetric nonnegative conductance ${\mu }_{xy}$ to each edge. With killing weights ${\kappa }_x$, the associated discrete-time walk moves from $x$ to $y$ with probability ${\mu }_{xy}/{\mu }_x$ and is killed with probability ${\kappa }_x/{\mu }_x$, where ${\mu }_x={\kappa }_x+{\sum }_y{\mu }_{xy}$.

The killing measure assigns the weight ${\kappa }_x$ of the transition from $x$ to a cemetery state.

An electrical network is a weighted graph whose edge weights are interpreted as electrical conductances. Random-walk hitting quantities can then be expressed through voltages, currents, and effective resistance.

A voltage is a scalar potential on the vertices of an electrical network. Away from prescribed boundary vertices it is harmonic, and its difference across an edge drives current through that edge.

A current flow is an antisymmetric function on oriented edges satisfying Kirchhoff's node law away from its sources and sinks. For conductance $c(x,y)$ and voltage $u$, Ohm's law gives $i(x,y)=c(x,y)(u(x)-u(y))$.

The Kirchhoff cycle law says the directed sum of voltage drops around every graph cycle is zero. For unit edge resistance this is the sum of signed currents around the graph cycle. With unit edge resistance, the current is a voltage gradient: define the voltage difference by summing drops along a graph path. The difference of the sums along two graph paths is a sum around closed walks; decomposing these into graph cycles makes it zero. Together with the Kirchhoff node law, the resulting Graph Laplacian equation determines current uniquely on a finite connected network.

The Kirchhoff node law says the sum of outward currents at a graph vertex is zero unless that graph vertex is a source or sink. In an electrical network, it is flow conservation; a unit flow has divergences $+1$ and $-1$ at its terminals.

The effective resistance between vertices $a$ and $z$ is the voltage difference required to send one unit of current from $a$ to $z$.

For a finite connected unweighted loopless graph with $n$ graph vertices,The edge-inclusion formula for a uniform spanning tree gives the left-hand side as $\mathbb{E}|T|$, and every spanning tree has $n-1$ edges. On the same finite connected graph with positive edge conductances $c_e>0$, the corresponding identity is ${\sum }_e{c}_e{R}_{\mathrm{eff}}(e)=n-1$.

The effective resistance to infinity is the limit of the effective resistance from a fixed vertex to the wired complement of increasing finite sets. It is finite exactly when the finite-energy flow criterion for transience holds.

Increasing edge resistances, including deleting edges, cannot decrease effective resistance. Decreasing resistances or identifying vertices cannot increase effective resistance. These statements also follow from the Thomson principle.

The effective conductance between two terminals is the reciprocal of their effective resistance. Under a unit voltage difference it equals the total current flowing from one terminal to the other.

Thomson principle says that effective resistance is the minimum energy among unit flows from $a$ to $z$:

If ${\Pi }_1,\dots ,{\Pi }_m$ are pairwise edge-disjoint cutsets separating $a$ from $z$ in an electrical network, then

For a random walk on a finite electrical network,

Let simple random walk travel from $a\ne z$ to its first visit to $z$, then stop on its subsequent first hit of $a$ in a finite connected unweighted loopless graph. Every directed edge $u\to v$ has expected traversal countThe Strong Markov property splits the count into the two killed legs. By killed-walk occupation voltage, their contributions are $v_{az}(u)$ and $v_{za}(u)$. Their Laplacians cancel, so the harmonic maximum principle on a finite graph makes the sum constant, with value $v_{az}(a)+v_{za}(a)=R_{\mathrm{eff}}(a,z)$. Summing over all directed edges recovers the commute time identity.

A bishop random walk moves uniformly among the current square and all chessboard squares sharing a diagonal with it.

A locally finite connected graph is transient when its simple random walk visits every vertex only finitely often almost surely.

For the walk on a weighted graph, the Green function normalized by vertex weight isSymmetry of the conductances makes $g(x,y)=g(y,x)$, and $\mathcal{E}(g(\cdot ,y),f)=f(y)$ for finitely supported $f$.

For simple random walk on ${\mathbb{Z}}^d$ with $d\ge 3$,Consequently the probability of ever hitting $x$ from the origin has the same order.

For a finite vertex set $A$, its equilibrium potential is $h_A(x)=P_x(H_A<\infty )$. It equals one on $A$, is harmonic off $A$, and belongs to the Dirichlet energy space with zero boundary at infinity.

The equilibrium measure is supported on $A$ and is given by

The capacity of a finite set is the total mass of its equilibrium measure of a finite set:Capacity is monotone under inclusion, though strict inclusion need not give strict inequality.

For a vertex $o$,

A last-exit decomposition partitions a transient path event according to the final visit to a finite set. Reversing the finite path before that visit and using detailed balance converts last-exit probabilities into hitting probabilities weighted by an equilibrium measure of a finite set.

A loop-erased random walk is the self-avoiding path obtained by chronologically erasing loops from a random-walk path.

The time reversal of a Brownian motion conditioned to exit at a boundary point can be coupled to radial ${\mathrm{SLE}}_2$ so that its loop-erasure is the radial curve. The coupling requires the Brownian path's first hit of each initial radial segment to occur at its tip. It is an existence theorem for a coupling and does not assert that the Brownian trace equals the simple radial curve, or that an elementary deterministic finite-loop algorithm is defined for all continuum paths.

On a finite connected unweighted graph, the graph path between $x$ and $y$ in a uniform spanning tree has the law of loop-erased random walk from $x$ to $y$. Root Wilson's algorithm at $y$ and process $x$ first: the first attached graph path is exactly that loop erasure, and later attachments cannot change it. Changing the root to $x$ proves reversibility of loop-erased random walk, even though chronological loop erasure does not commute with reversing each individual random-walk trajectory.

Chronological loop erasure removes each loop from a finite or transient infinite path as soon as the loop is formed, producing a self-avoiding path.

On a finite undirected graph, the reversal of a loop-erased random walk from $x$ to $y$ has the law of a loop-erased random walk from $y$ to $x$. The uniform-spanning-tree path representation proves the identity.

A simple random walk on a locally finite graph chooses each neighbouring vertex with equal probability.

On the $n$-dimensional hypercube graph, simple random walk flips one uniformly chosen coordinate at each step. Its stationary distribution is uniform on the $2^n$ vertices, so its mean return time is $2^n$.

For random walk on $\{-1,1{\}}^n$ that chooses a coordinate uniformly and flips it with probability $1/2$, the Walsh characters $f_J(x)={\prod }_{j\in J}{x}_j$ form an orthonormal eigenbasis under the uniform distribution on a finite set. Flipping a coordinate in $J$ negates $f_J$, so $P{f}_J=(1-|J|/n)f_J$. Hence $1-k/n$ has multiplicity $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, and the ordinary and absolute spectral gaps both equal $1/n$.

A simple random walk on ${\mathbb{Z}}^2$ visits its starting point infinitely often almost surely and hits every fixed vertex almost surely.

If the independent increments are $+1$ with probability $p$ and $-1$ with probability $q=1-p$, thenThus $\mathbb{E}{S}_n=n(p-q)$ and $\mathrm{var}(S_n)=4npq$.

For the symmetric walk and $V_{2n}=|\{0\le j\le 2n:S_j=0\}|$,Since the central binomial coefficient satisfies $\left(\genfrac{}{}{0ex}{}{2k}{k}\right)/4^k\asymp k^{-1/2}$, this expectation is of order $\sqrt{n}$.

For $d$ independent symmetric walks on $\mathbb{Z}$, the probability that all are at the origin at time $2n$ isThe Borel-Cantelli lemmas therefore show that simultaneous returns occur only finitely often almost surely when $d\ge 3$.

On a finite undirected graph, stationary mass is proportional to vertex degree.

A biased nearest-neighbor walk steps right and left with unequal probabilities.

Let a discrete-time chain move up with probability $q$ and down with probability $p=1-q$ away from zero, while at zero it moves up with probability $q$ and stays with probability $p$. It is transient for $q>p$, null recurrent for $q=p$, and positive recurrent for $q<p$. In the positive-recurrent case its invariant distribution isand aperiodicity from the self-loop at zero implies convergence to this distribution.