Random walk ($S_n=S_0+{\sum }_{j=1}^n{\xi }_j$)

A random walk is a stochastic process formed by accumulating random steps. In its additive form, the increments ${\xi }_j$ are independent and identically distributed random variables and the position after $n$ steps isThe steps can have more choices than $-1$ and $+1$: they may be integers, real numbers, or vectors. A random walk on a graph instead describes steps between vertices along edges; its available moves can depend on the current vertex.

For example, starting at zero, the steps $+1,-1,+1,+1$ produce the positions $0,1,0,1,2$. This is one sample path; other step sequences can have the same endpoint. A simple random walk on the integer line makes this distinction particularly tangible: repeated Bernoulli trials determine both a whole sample path and an endpoint with a binomial distribution. All positions below are dimensionless quantities measured in steps of length one, and $n$ counts discrete updates.

The model is useful because it separates an average tendency from accumulated fluctuations. A fair simple symmetric random walk has zero expected value at every time, yet its standard deviation grows: cancellation across many possible sample paths does not keep each walker near zero. The two figures below compare sample paths with exact endpoint probabilities. For the basic additive construction and its independent increments, see MIT, Stochastic Processes I, section 2.

An upward skip-free random walk has integer-valued increments bounded above by one. Arbitrarily large downward jumps are permitted, but a first crossing of a nonnegative integer level $k$ from below must land exactly at $k$. This removes the overshoot from the stopped likelihood ratio under exponential tilting and permits the exact geometric maximum of an upward skip-free random walk. For a real threshold $k$, the first crossing is the crossing of $\lceil k\rceil$, so the overshoot-free formula must use that integer level.

Let the increments define an upward skip-free random walk, and suppose $\varphi (\lambda )=\mathbb{E}{e}^{\lambda X_1}$ is finite for all $\lambda \ge 0$. If ${\lambda }_0>0$ satisfies $\varphi ({\lambda }_0)=1$ and ${\varphi }^{\prime }({\lambda }_0)>0$, the exponential tilting at ${\lambda }_0$ gives integrable increments of positive mean. The strong law of large numbers makes every nonnegative integer level attainable under this tilted law. Upward jumps are at most one, so the value at a first level hit is exactly that level. The stopped likelihood ratio under exponential tilting therefore gives hitting probability $e^{-{\lambda }_{0}k}$ for integer $k\ge 0$. Subtracting consecutive tail probabilities yields the displayed geometric distribution on $j=0,1,\dots$. For real thresholds use $\lceil k\rceil$ in place of $k$.

For independent $N(0,1)$ increments, a random walk has $S_j\sim N(0,j)$. If $B$ is a bounded measurable set, its occupation time probability obeys $\mathbb{P}(S_j\in B)\le |B|/\sqrt{2\pi j}$. Consequently $\mathbb{E}{\sum }_j{1}_B(S_j)/j<\infty$, and Tonelli's theorem makes this series finite almost surely. Kronecker lemma then gives the displayed zero occupation density. This also shows why its empirical occupation probabilities cannot converge to a probability measure simultaneously on all bounded intervals and the whole real line: continuity from below would contradict the preserved total mass one.

Independent planar unit steps with uniformly distributed direction have zero vector expected value. The squared Euclidean norm of their sum has expectation $n$, because each diagonal term is one and all cross terms vanish by independence. More generally, zero-mean independent steps with common second moment $s^2$ give mean-square displacement $n{s}^2$; nonzero drift adds a quadratic contribution.

For a random walk with independent and identically distributed random variables as increments and finite moment-generating function at $\theta$, put $\kappa (\theta )=\log \mathbb{E}{e}^{\theta X_1}$. Then $e^{\theta S_n-n\kappa (\theta )}$ is a martingale by conditioning on the next independent increment. In particular, if $r>0$ and $\mathbb{E}{r}^{X_1}=1$, then $r^{S_n}$ is a martingale. Stopping at a finite interval exit can make this process bounded, allowing the dominated convergence theorem to justify passage from bounded stopping times to the exit time.

For a random walk with independent and identically distributed random variables as increments, let $M_n=e^{\lambda S_n}/\varphi (\lambda {)}^n$ define its finite-time exponential tilting. Under the tilted law, $L_n=M_n^{-1}$ is a martingale: the conditional mean of $\varphi (\lambda )e^{-\lambda X_{n+1}}$ is one. For a stopping time $T$, partition $\{T\le n\}$ into $\{T=j\}$ and apply the tower property of conditional expectation to obtain the displayed identity. Only finite-time absolute continuity of measures is needed; there need not be an infinite-horizon likelihood-ratio density.

Let $S_n$ have integrable, mean-zero independent and identically distributed random variables as increments, taking integer values at most one, with $\mathbb{P}(X_1=1)>0$. For a positive integer $b$, put $T_b=\inf \{n:S_n=b\}$ and $M(\tau )=\mathbb{E}{e}^{\tau X_1}$, $\tau >0$. Then $T_b$ is finite almost surely. Indeed, $b-S_{n\wedge T_b}$ is a nonnegative martingale; finite convergence on $\{T_b=\infty \}$ would force its integer increments eventually to vanish, contrary to the Borel-Cantelli lemmas applied to $\{X_n=1\}$.

The exponential martingale of a random walk $e^{\tau S_n}/M(\tau {)}^n$ stopped at $T_b$ is bounded by $e^{\tau b}$ because $S_{n\wedge T_b}\le b$ and $M(\tau )\ge 1$. The dominated convergence theorem therefore preserves its mean one at the limit and proves the displayed first-passage time transform. This argument accommodates arbitrarily large negative jumps; the restriction concerns upward jumps. For a simple symmetric random walk, $M(\tau )=\cosh \tau$, giving $\mathbb{E}{e}^{-\alpha T_b}=(e^{\alpha }-\sqrt{e^{2\alpha }-1}{)}^b$.

For independent and identically distributed random variables with law $N(-1,1)$, $e^{2S_n}$ is a nonnegative martingale, since the increment's moment-generating function equals one at parameter two. The Doob maximal inequality gives $\mathbb{P}(Z>t)\le e^{-2t}$ for the all-time maximum $Z\ge 0$. Integrating the tail gives the displayed bound. For $b\le 0$, $e^{bZ}\le 1$. The strong law of large numbers guarantees finiteness and attainment of the maximum because $S_n\to -\infty$.

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

A non-backtracking random walk remembers its preceding vertex and excludes that neighbor from the next choice. At vertices of degree at least two, it is a Markov chain on directed edges: $(a,b)$ moves to $(b,c)$ with probability $1/(\mathrm{deg}b-1)$ for each neighbor $c\ne a$. Dead ends require an additional convention. An initial vertex without a preceding edge uses the ordinary first-step neighbor distribution.

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.

Deleting an edge of a locally finite recurrent graph leaves recurrent Markov chain connected components. On an infinite component choose a root away from the deleted edge's endpoints, so its vertex degree does not change. The Rayleigh monotonicity principle increases resistance to wired outer boundaries, and effective resistance to infinity therefore remains infinite. Finite components are recurrent Markov chain too. This is a recurrence-type comparison; at an endpoint, changes in the vertex degree factor prevent a blanket monotonicity claim about first-return probabilities.

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.

In a finite connected electrical network, run the conductance random walk from $s$ until its first visit to a distinct vertex $t$. Let $G(s,x)$ be the expected visits to $x$ before stopping, and $w_x={\sum }_y{w}_{xy}$. The expected signed number of traversals of $\{x,y\}$ is the displayed expression. Its divergence is $1_{x=s}-1_{x=t}$ by telescoping each path, and its resistance-weighted sum around a cycle is zero because $G(s,x)/w_x$ is a voltage. Uniqueness follows by summing ${\sum }_{\{x,y\}}{w}_{xy}(v_x-v_y{)}^2$: a zero-divergence voltage flow has zero energy. Thus the expected net traversals are exactly the unit source-to-sink current.

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 the conductance-weighted random walk on a graph, set $d(x)={\sum }_v{c}_{xv}$. The voltage $h(u)=P_u(T_x<T_y)$ has boundary values one and zero. The total electric current is ${\sum }_v{c}_{xv}(1-h(v))=1/R(x,y)$. The first-step analysis therefore gives the displayed positive-return-time formula. Wiring the exterior of finite sets and taking limits gives $P_x(T_x^{+}=\infty )=1/(d(x)R(x,\infty ))$.

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 vertex in the current vertex's graph neighbourhood with equal probability, assuming there is at least one available neighbour. On the integer line there are two choices, one unit left or right, so each has probability $1/2$. This is the one-dimensional simple symmetric random walk. Terminology varies: a simple random walk on the integer line is also often allowed unequal step probabilities, with “symmetric” specifying the fair case.

For a simple symmetric random walk starting at $S_0=0$, each increment has the Rademacher distribution, with expected value zero and variance one. Thus linearity of expectation and the variance of a sum of independent random variables giveFor example, after $80$ steps the expected value is zero, the variance is $80$, and the standard deviation is $\sqrt{80}\approx 8.944$. Doubling the typical distance scale takes four times as many steps. This square-root growth explains why a random walk can wander far even when there is no preferred direction.

The colored curves are illustrative sample paths, not averages over all possible walks. The dashed curves show the expected values; the shaded bands show the expected value plus or minus one standard deviation at each time. These bands are a scale of spread, not confidence intervals, and give no guarantee that an entire sample path stays inside them.

Zero expected value does not make this a stationary process: its one-time probability distribution changes with $n$, as the increasing variance already proves. It does have stationary increments and independent increments, because blocks of fresh steps have the same probability distribution at any starting time and disjoint blocks use independent random variables. This separation of position from increment is one reason the random walk is such a useful first example of a stochastic process.

A simple symmetric random walk starting from $S_0$ haswhere the increments ${\xi }_k$ are independent and satisfy

For the nearest-neighbor symmetric walk on ${\mathbb{Z}}^3$, a return at time $2n$ uses $i,j,k$ positive and the same numbers of negative steps along each axis, with $i+j+k=n$. Counting arrangements gives the displayed identity. The sum of squares of the three-category multinomial distribution probabilities is at most their maximum. This maximum occurs at balanced counts and is $O(n^{-1})$ by Stirling's formula; the central binomial factor is $O(n^{-1/2})$. The total return probability is therefore summable. The expected number of visits is finite, so the probability of returning after time zero is strictly below one, proving that the origin is a transient state.

For a simple symmetric random walk starting from zero, its first hitting time of $1$ is almost surely finite but has infinite expectation. Stopping at exit from $[-m,1]$, the optional stopping theorem for $S_n$ gives upper-exit probability $m/(m+1)$, while stopping $S_n^2-n$ gives mean exit time $m$. The first probabilities tend to one, and the exit times are bounded above by the first passage to $1$, proving both conclusions. Finite-time stopping and bounded stopped positions justify passage to the exit time.

Suppose two independent planar simple symmetric random walks are compared while one stays at its $j$th position throughout a deterministic time block. If each block has an unconditional probability bounded below by a positive constant that the other walk visits the origin, simultaneous origin visits occur infinitely often almost surely. Markov-chain recurrence gives infinitely many origin blocks for the sleepy walk. The block bound yields positive probability of infinitely many coincidences; eventual coupling of planar symmetric random walks then makes this future event have probability zero or one. Conditional block bounds or independence of capture attempts are not required.

For a simple symmetric random walk, the estimate $\mathbb{E}{e}^{\theta S_n}\le e^{n{\theta }^2/2}$ and the exponential maximal inequality give $\mathbb{P}({\max }_{k\le n}{S}_k\ge t\sqrt{n})\le e^{-t^2/2}$ for $t\ge 0$.

For the simple symmetric random walk on $\mathbb{Z}$, the renewal equation relates first-return and return probability generating functions. The central-binomial return series is $U(s)=(1-s^2{)}^{-1/2}$, giving $F(s)=1-U(s{)}^{-1}$. Its value tends to one at $s=1$, but its derivative diverges there: the walk has null recurrent states.

For a simple symmetric random walk on the integers, let $T_k$ be the first time that $k$ distinct vertices have been visited. The visited set is an interval, and at $T_k$ the walk is at an endpoint. The Strong Markov property turns the time to add one vertex into gambler's ruin between the two immediately exterior vertices, starting one step from a boundary. The expected duration of symmetric gambler's ruin is therefore $k$. This also holds at $k=1$.

For a simple symmetric random walk, $S_n^2-n$ is a martingale because the next increment has conditional mean zero and conditional square one.

If $T$ is a stopping time with finite mean, thenStopping first at $T\wedge n$ and using the $L^2$ martingale convergence theorem justifies passage to an unbounded $T$.

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.

A simple random walk on the integer line starts at $S_0=0$ and takes independent and identically distributed random variables ${\xi }_j$ as unit increments, withThe simple symmetric random walk has $p=1/2$; a biased random walk has $p\ne 1/2$. At $p=0$ or $p=1$ every step is deterministic, giving $S_n=-n$ or $S_n=n$ respectively.

Count the rightward steps using indicator functions:Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at $n=4$ the endpoint $S_4=2$ means exactly three rightward steps and one leftward step. There are $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ possible orders, so its probability is $4p^3(1-p)$, equal to $1/4$ in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass functionIn particular, the endpoint must have the same integer parity as $n$: $S_n\equiv n(\mathrm{mod}2)$. For $0<p<1$ the support of a probability distribution is exactly $\{-n,-n+2,\dots ,n\}$. At $n=80$ only even integers in $[-80,80]$ are reachable; at $n=81$ only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.

The endpoint identity and the binomial distribution give the expected value, variance, and standard deviationA short direct check gives $\mathbb{E}{\xi }_j=2p-1$ and $\mathbb{E}{\xi }_j^2=1$, hence $\mathrm{Var}({\xi }_j)=1-(2p-1{)}^2=4p(1-p)$. Then apply linearity of expectation and the variance of a sum of independent random variables.

The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from $\sqrt{20}\approx 4.472$ to $\sqrt{80}\approx 8.944$, while ${\sigma }_n/n$ shrinks from $0.2236$ to $0.1118$. At $n=80,p=0.65$, the standard deviation is $\sqrt{72.8}\approx 8.532$, or $0.9539$ times the fair width, and ${\sigma }_n/n\approx 0.1067$. Centering and dividing by each walk's own standard deviation gives, for $n>0$,This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is $2/{\sigma }_n$: approximately $0.4472$ for the fair $20$-step walk, $0.2236$ for the fair $80$-step walk, and $0.2344$ for the biased $80$-step walk.

The positions themselves are dependent. For $1\le m\le n$, $S_n=S_m+(S_n-S_m)$, where the second term is independent of $S_m$. Their covariance is thereforeFor example, in the fair case $S_1=1$ allows $S_2=0$ or $2$, whereas $S_1=-1$ allows $S_2=-2$ or $0$. Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities areThese transition probabilities are the same at every time and every integer position: shifting both $x$ and $y$ by the same integer leaves $P(x,y)$ unchanged. Thus the Markov property and independent increments coexist with dependent positions.

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$.

A biased random walk on the integer line takes unit steps right and left with unequal probabilities $p$ and $1-p$, using independent and identically distributed random variables as increments. For $S_0=0$, the expected value is $n(2p-1)$: positive for $p>1/2$ and negative for $p<1/2$. Changing $p$ to $1-p$ reverses the preferred direction. The exact endpoint probability mass function is given under simple random walk on the integer line.

For example, with $p=0.65$ each step has expected value $0.30$ and variance $0.91$. After $80$ steps,The displacement of the expected value from zero is about $24/8.532\approx 2.813$ standard deviations, yet individual sample paths still move left as well as right, as the figure under simple random walk illustrates. Bias lets this elementary stochastic process model an average directional tendency while retaining fluctuations. Boundary and return questions have their own treatments under gambler's ruin and the specialized children below.

For a walk with increments $+1$ with probability $p$ and $-1$ with probability $1-p$, putThen $\exp (\theta S_n-n\psi (\theta ))$ is a martingale. Optional stopping at the first linear-boundary crossing and optimization over $\theta$ gives exponential maximal-deviation bounds governed by the Legendre transform of a cumulant-generating function.

On $\{0,\dots ,N\}$, stop at zero, move left with probability $q>1/2$ and right with probability $p=1-q$ at interior states, and move deterministically from $N$ to $N-1$. For $m_i={\mathbb{E}}_i{T}_0$, the first-step analysis gives $m_0=0$, $m_i=1+q{m}_{i-1}+p{m}_{i+1}$ and $m_N=1+m_{N-1}$. Setting $D_i=m_i-m_{i-1}$ gives $q{D}_i-p{D}_{i+1}=1$, $D_N=1$, hence $D_i=[1-2p(p/q{)}^{N-i}]/(q-p)$. Summing these differences proves the displayed formula, and more generally $m_i=i/(q-p)-2pq(p/q{)}^{N-i}[1-(p/q{)}^i]/(q-p{)}^2$. A downward block has a uniformly positive probability of reaching zero, which supplies a geometric tail bound and justifies finiteness of these expectations.

For independent lattice steps of length $a$ at intervals $\tau$, with probabilities $\alpha +\beta =1$, the diffusive scaling $a^2/\tau \to 2D$ and $(\alpha -\beta )a/\tau \to V$ requires a bias of order $a$. Expanding the master equation gives the advection-diffusion equation $p_t+V{p}_x=D{p}_{xx}$. The finite-step variance coefficient is $2a^2\alpha \beta /\tau$; it has the same limit because the squared bias vanishes. Fixed nonzero bias does not give finite drift under this diffusive scaling.

For a nearest-neighbour random walk with upward probability $0<p<q=1-p$, start at $S_0=0$ and put $M={\sup }_{n\ge 0}{S}_n$. Its probability distribution is geometric on the nonnegative integers, with the displayed mass and expected value $p/(q-p)$. To prove this, the exponential martingale of a biased simple random walk $Z_n=(q/p{)}^{S_n}$ has expectation one. Stop at the first hit $H_k$ of $k$. Before that hit, $Z_{n\wedge H_k}\le (q/p{)}^k$; the strong law of large numbers gives $S_n\to -\infty$ on paths without a hit. Dominated convergence theorem therefore gives $1=(q/p{)}^k\mathbb{P}(H_k<\infty )$. Taking differences of $\mathbb{P}(M\ge k)=(p/q{)}^k$ yields the mass. If time zero is excluded, the maximum can equal $-1$ with probability $q-p$ and does not have this nonnegative geometric distribution.

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.

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