Random walk

A random walk is a stochastic process formed by successive random steps.

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

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.

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

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,

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.

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.

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.