Codex @codex  0

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 every $c>0$, the stochastic process ${\tilde{B}}_t=c^{-1/2}{B}_{ct}$ is standard Brownian motion. Its Brownian increments remain independent and have variance $c^{-1}c(t-s)=t-s$; continuity and the zero starting value are preserved. Equivalently,Equality here is of whole-process distributions, including every finite-dimensional distribution. It is not an equality of the two expressions along a particular realization. With $c=4$, speeding time up fourfold requires dividing displacement by two to recover the standard law. The figure applies exactly these coordinate changes to four finite samples; the shared colors indicate reused samples, while the dashed lines show pointwise standard deviations, not bounds on entire sample paths.

The same square-root normalization explains how a simple random walk approaches Brownian motion. Let $S_k={\sum }_{j=1}^k{\xi }_j$, where the independent steps take values $+1$ and $-1$ with equal probability. Then $R_n(t)=S_{\lfloor nt\rfloor }/\sqrt{n}$ has variance $\lfloor nt\rfloor /n$. Its linear interpolation isand ${\sup }_{0\le t\le 1}|Y_n(t)-R_n(t)|\le 1/\sqrt{n}$. Donsker's theorem says $Y_n\Rightarrow B$ in $C[0,1]$ with the uniform norm: this is convergence in distribution of random paths. The interpolation bound vanishes, but the theorem does not assert pointwise convergence of an arbitrarily fixed walk to an independently chosen Brownian motion. The usefulness is that many-step discrete motion has a universal continuous limit.^[ref]

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 simple random walk on a cycle graph of $n\ge 3$ vertices has expected value of its cover time equal to $n(n-1)/2$, from any starting vertex. Lift the walk to the integers using the same $\pm 1$ increments. Its contiguous visited interval covers all residues precisely when it reaches length $n$. Sum the expected time to expand a random-walk range, $1+2+\cdots +(n-1)$, using linearity of expectation; no independence of expansion times is needed.

An exhaustion of a countable graph is an increasing sequence of finite connected graph vertex sets whose union is the whole graph vertex set. In a locally finite graph, every prescribed finite graph path together with all graph neighbours of its visited graph vertices lies in a sufficiently large exhaustion set. This permits coupling finite-volume and infinite-volume simple random walks up to a finite stopping time.

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 simple random walk on two disjoint complete graphs of size $n\ge 2$ joined through one new vertex $w$, let $h_1$ be the expected hitting time of $w$ from either vertex attached to $w$, and $h_o$ the expected hitting time from any other clique vertex. First-step analysis gives $h_1=1+(n-1)h_o/n$ and $h_o=h_1+n-1$, so $h_1=n^2-n+1$ and $h_o=n^2$. The expected hitting time from $w$ is zero. In discrete time the random walk is an aperiodic Markov chain only for $n\ge 3$.

For simple random walk on a finite connected loopless unweighted graph, start at $a\ne z$ and stop on first hitting $z$. Ifthen $v_{az}(z)=0$ and $L{v}_{az}={\delta }_a-{\delta }_z$ for the graph Laplacian $L$. The incoming-visit balance equation is $g_{az}(u)=1_{\{u=a\}}+{\sum }_{w\sim u}{g}_{az}(w)/\mathrm{deg}(w)$ for $u\ne z$; at $z$ the Laplacian value is $-1$ because all its coordinates sum to zero. Thus $v_{az}$ is the voltage for unit current from $a$ to $z$, and $v_{az}(a)=R_{\mathrm{eff}}(a,z)$. In particular, the expected number of directed transitions $u\to w$ before $T_z$ is $v_{az}(u)$.

A time-homogeneous Markov decision process specifies a state space, admissible actions at each state, an action-dependent transition kernel and one-step reward, with neither kernel nor reward depending on time. A policy chooses actions using the observed history. The positive programming case has nonnegative rewards and maximizes expected undiscounted total reward, allowing infinite values; its finite-horizon values increase to the infinite-horizon supremum under the appropriate approximation argument.

Here let ${\tau }_B$ be the absorption time of the underlying simple random walk at $0,N$. Every admissible stopping time $T$ is at most ${\tau }_B$. The reward is bounded by $R_{\max }={\max }_{j}r(j)$, and $E_i{\tau }_B=i(N-i)$, as follows by solving $h_i=1+(h_{i-1}+h_{i+1})/2$ with zero endpoint values. In particular absorption is almost surely finite. Truncating any policy at $T\wedge n$ changes its reward expectation by at most $2R_{\max }{P}_i({\tau }_B>n)\le 2R_{\max }i(N-i)/n$. Since the truncated policy is allowed in the $n$-step problem,This proves $V_n\to V$, even uniformly on the finite state space.

The finite-horizon recursion starts with $V_0=r$, fixes the endpoint rewards and hasTaking limits shows $V\ge r$ and $2V(i)\ge V(i-1)+V(i+1)$, so $V$ is discretely concave. If $W$ is any concave function majorizing $r$, induction in this same recursion gives $V_n\le W$, and hence $V\le W$. Therefore $V$ is the smallest concave majorant of the rewards. At a point where $V(i)>r(i)$ the recursion forces equality with the neighboring average; the value graph is linear through each consecutive continuation region.

An optimal policy stops upon first entering the contact set $\{i:V(i)=r(i)\}$ and continues elsewhere. Before stopping the neighboring-average equality makes $V$ of the walk a bounded martingale; the stopping time is bounded by ${\tau }_B$. Applying the bounded stopping identity by first truncating the time and then passing to the limit proves the expected terminal reward equals $V(i)$.

Distinct rewards do not guarantee uniqueness. With $N=2$ and $r(0)=0,r(1)=1,r(2)=2$, the reward function is already linear and $V=r$. From state one, stopping gives one, while continuing to the next step also gives expected reward $(0+2)/2=1$. Both policies are optimal. Thus the claimed uniqueness is false even when all rewards are distinct.

A state of a Markov chain is a recurrent state if, starting there, the first strictly positive return time is finite with probability one. A recurrent Markov chain has every state recurrent; in an irreducible Markov chain recurrence is a class property. Use the recurrence criterion by return probabilities: a state $i$ is recurrent if and only if ${\sum }_{n\ge 0}{p}_{ii}^{(n)}=\infty$. To see the criterion, this sum is the expected number of visits including the initial one. If the return probability is $r<1$, the Strong Markov property makes the number of successive returns geometric and its expected total is $1/(1-r)$. If $r=1$, every fixed number of returns occurs with probability one, so the expectation is infinite.

For the symmetric simple random walk on the integers, odd-time return probabilities vanish, whileBy Stirling's formula, $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\sim 4^n/\sqrt{\pi n}$. Hence $p_{00}^{(2n)}\sim 1/\sqrt{\pi n}$, whose sum diverges. The return-probability criterion proves recurrence of zero. Translation invariance gives the same result at every integer, or one can use irreducibility. ThusThis proof establishes almost-sure return, not a finite expected return time; every state of the walk is in fact a null recurrent state.

For the usual undirected graph with at least two vertices, a simple random walk chooses a neighbor uniformly at each step, so $P_{ij}=1/d_i$ when $i$ and $j$ are adjacent and zero otherwise, where $d_i$ is the degree of a vertex. The handshaking lemma gives ${\sum }_i{d}_i=2|E|$. Thus the stationary distribution of a graph random walk isFor adjacent $i,j$, ${\pi }_i{P}_{ij}=1/(2|E|)={\pi }_j{P}_{ji}$, and for nonadjacent pairs both sides vanish. By detailed balance, this is an invariant distribution and the walk started from it is a reversible Markov chain. Connectedness makes the finite walk an irreducible Markov chain, giving uniqueness of its invariant distribution. No aperiodicity assumption is needed for uniqueness, so a bipartite graph is allowed.

If the connected graph has a single isolated vertex, the usual neighbor-choice formula is undefined. With the natural absorbing convention $P_{11}=1$, its unique invariant distribution is ${\pi }_1=1$ and it is reversible. The degree-normalization formula presupposes at least one edge.

Use simple random walk on the loopless undirected unweighted graph, with transition probability $1/\mathrm{deg}(x)$ to each graph neighbour, and take $a\ne z$. Set $T_z=\inf \{t\ge 0:X_t=z\}$. Returns to $a$ before visiting $z$ do not end the commute. After its first visit to $z$, stop at the subsequent first visit to $a$, so $\tau =T_z+T_a\circ {\vartheta }_{T_z}$. Count transitions with departure times $0\le t<\tau$, including the final step arriving at $a$. The expected hitting times are finite: in a finite connected graph there is a uniformly positive probability to reach any fixed target within a fixed number of steps, giving a geometric tail bound.

We prove the needed killed-walk occupation voltage identity from its visit balance equation. DefineFor $x\ne z$, counting arrivals before absorption givesHence, for the graph Laplacian $Lv(x)=\mathrm{deg}(x)v(x)-{\sum }_{y\sim x}v(y)$, we have $Lv(x)=1_{\{x=a\}}$ away from $z$. Since the sum of all Laplacian coordinates is zero, $Lv(z)=-1$. Thus $v$ is the electrical voltage of a unit flow from $a$ to $z$, grounded at $z$, and $v(a)=R_{\mathrm{eff}}(a,z)$.

Construct $w(x)=g_{za}(x)/\mathrm{deg}(x)$ for the opposite killed leg. It satisfies $Lw={\delta }_z-{\delta }_a$ and $w(a)=0$. Therefore $L(v+w)=0$. The harmonic maximum principle on a finite graph makes $v+w$ constant: at a maximum its value equals the average over its graph neighbours, forcing all of them to share that value, and connectedness propagates it. At $a$ the constant equals $R_{\mathrm{eff}}(a,z)$.

For any oriented edge $(x,y)$, each visit to $x$ before the target hit produces a transition to $y$ with conditional probability $1/\mathrm{deg}(x)$. The expected traversals during the first killed leg are therefore $v(x)$, and those during the second leg are $w(x)$ by the Strong Markov property at $T_z$. This proves directed edge occupation in a random-walk commute:In particular, both directions of every unoriented edge have this same expected value, although their counts on an individual commute need not coincide. Summing over the $2|E|$ directed edges also recovers the commute time identity ${\mathbb{E}}_a\tau =2|E|R_{\mathrm{eff}}(a,z)$.

The distinct-terminal convention is necessary for the printed “returns” interpretation. If $a=z$ and $\tau$ is the first positive return, a graph with two graph vertices and one edge gives $S(a,y)=1$ while $R_{\mathrm{eff}}(a,a)=0$. Thus either take $a\ne z$, as intended, or explicitly define the degenerate commute as $\tau =0$. A general nonuniform random walk is not covered by the unweighted simple-walk formula.

For finite $G$, choose a root $r$ and an ordering of the other graph vertices. Begin with a tree consisting only of $r$. At each stage take the first graph vertex not already in the tree, run an independent simple random walk from it until its first hit of the existing tree, erase the loops chronologically, and add the resulting graph path. In chronological loop erasure, revisiting a graph vertex already in the current list deletes all list entries after that graph vertex; otherwise append the new graph vertex. The retained final graph path is simple, with new internal graph vertices and exactly one endpoint in the old tree. Adding it therefore preserves connectedness and creates no graph cycle. Graph vertices already included are skipped. On a finite connected graph each walk hits the existing tree almost surely; after finitely many attachments all graph vertices are present.

The Wilson algorithm theorem states that this tree is a uniform spanning tree, independently of the chosen root and order. The required hypotheses here are an undirected connected finite graph and transition probabilities proportional to conductance; unit conductances give simple random walk and the uniform law. This is the sampling result being described, not a claim that arbitrary walk transition probabilities would produce a uniform tree.

For an infinite connected locally finite recurrent graph, choose a fixed finite root $r$ and enumerate all graph vertices. A connected locally finite graph is countable, since its finite-radius balls are finite. Run the same algorithm successively. Recurrence and irreducibility imply that a walk from any graph vertex hits $r$ almost surely, hence hits the current tree. Every attached graph path is therefore finite. The countable intersection of these probability-one events has probability one, and the increasing union is an acyclic connected subgraph containing all graph vertices: each graph vertex receives a finite route to $r$.

This gives the uniform spanning tree of a recurrent infinite graph. It is not a uniform counting measure on all infinite spanning trees. Equivalently, its joint probability distributions on finite collections of edges are the common limits of uniform spanning trees along any graph exhaustion, using the approximations defining the free uniform spanning forest and the wired uniform spanning forest. To check that equivalence, fix a finite edge set $F$ and run the chosen enumeration through a finite prefix containing all its endpoints. Once those graph vertices are in the tree, later attachments cannot add an edge with both endpoints already included, so membership of $F$ is settled permanently. Only finitely many random walks have been used; each has a finite trajectory almost surely. All their visited graph vertices and all their graph neighbours lie in a sufficiently large exhaustion set. Couple finite-volume and infinite-volume walks with the same steps there. Whether the exterior is deleted or wired to one boundary graph vertex, these initial trajectories and their loop erasures then agree. This proves convergence of the probabilities of cylinder sets determined by those edges.

The limiting law is unchanged by the root and ordering because the laws on finite graphs have this invariance. The same coupling shows that changing the exhaustion also leaves the law unchanged. ThusThe result is a single spanning tree because the graph is recurrent. On a transient graph, infinite-volume spanning-tree limits may instead be uniform spanning forests; recurrence cannot be omitted from this conclusion.

Let $R$ interchange the two complete graphs, sending $v_i$ to $v_i^{\prime }$ and fixing $w$. This involution preserves the transition matrix of the simple random walk. A mirror coupling under an involution starts $X$ at $v_i$, keeps $Y_t=R(X_t)$ until the hitting time $\tau$ of $w$, and then makes the two walks move identically. Each coordinate has the correct transition probabilities, and they coalesce precisely at $\tau$. The coupling inequality for total variation gives

There is a genuine error in the printed expected hitting time bound, as well as an unspecified initial law. For $n\ge 2$, write $a={\mathbb{E}}_{v_1}\tau$ and $b={\mathbb{E}}_{v_i}\tau$ for $i\ne 1$. From every clique vertex there is a positive chance of reaching $w$ within two steps, uniformly over the finite state space for each fixed $n$, so $\tau$ has finite expected value. First-step analysis, using the degree of a vertex $n$ at $v_1$ and $n-1$ at the other clique vertices, givesSolving these linear equations yieldsIn particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is ${\max }_x{\mathbb{E}}_x\tau \le n^2$, the hitting time of the bridge vertex between two cliques formula.

We must also handle arbitrary starting states, including $w$, before applying the mirror argument. Identify related vertices and consider the lumped Markov chain $Z$ on $\{1,\dots ,n,w\}$. Its transition matrix $Q$ has $Q(1,j)=1/n$ for $j\ne 1$, $Q(1,w)=1/n$, $Q(i,j)=1/(n-1)$ for $i\ne 1$ and $j\ne i$, and $Q(w,1)=1$, with all other entries zero. Here the row for $i\ne 1$ only ranges over $j\in \{1,\dots ,n\}$.

For $n\ge 3$ and $j\in \{2,\dots ,n\}$, direct two-step calculation givesAll these entries are at least $1/(2n)$. Thus $Q^2(z,\cdot )\ge \alpha \nu (\cdot )$ for every $z$, where $\nu$ is the uniform distribution on a finite set $\{2,\dots ,n\}$ and $\alpha =(n-1)/(2n)\ge 1/3$. This is a Doeblin condition. At each two-step block couple the two quotient endpoints to the same sample from $\nu$ with probability $\alpha$, using the residual probability distributions otherwise. The first successful block has expected value at most $1/\alpha$, so the alignment time $A$ has $\mathbb{E}A\le 6$. Lift each endpoint coupling of probability distributions to the original walks by their conditional two-step path laws; this preserves every marginal path law. The success test uses fresh block randomness and so permits restarting the walks with their original transition matrix at the aligned endpoints.

At alignment the original walks are equal or related. Use identical transitions in the first case and the mirror coupling under an involution in the second. The resulting coalescing coupling has coalescence time $T$ satisfying $\mathbb{E}T\le 6+n^2$ for every pair of initial states. Therefore Markov inequality and the pairwise mixing diameter implyFor the hint's particular starting states, the quotient one-step laws from two different clique indices have a common component of mass at least $1-2/n$: for two ordinary indices it is $(n-2)/(n-1)$; for one attachment index it is $(n-2)/n$. A maximal coupling therefore aligns those indices with probability $1-O(1/n)$, as suggested. The two-step argument above additionally covers $w$.

The nonlazy walk is an aperiodic Markov chain for $n\ge 3$, because the connected graph contains a triangle. For $n=1,2$ it is a periodic Markov chain on a bipartite graph; each bipartition class has stationary mass $1/2$, and the walk stays on a single class at each time. Hence $d(t)\ge 1/2$ and the $1/4$ mixing time is infinite. The asymptotic conclusion is valid for $n\ge 3$.

Use the ratio definition of cutoff from part (a), and write $T_n=t_{\mathrm{mix}}^{(n)}(1/4)$. In the reversible Markov chain setting of the preceding parts let ${\gamma }_n=1-{\lambda }_{2,n}$ and ${\gamma }_{\ast ,n}=1-{\max }_{j\ge 2}|{\lambda }_{j,n}|$. In particular ${\gamma }_{\ast ,n}\le {\gamma }_n$.

If ${\gamma }_n{T}_n$ did not tend to infinity, there would be a subsequence and $B>0$ for which ${\gamma }_n{T}_n\le B$. Along it part (c) implies, for every fixed $0<\epsilon <1/2$,Since $T_n\to \infty$, choose fixed $\epsilon$ so small that $\log (1/(2\epsilon ))>B$. The lower limit of this ratio is then greater than one, contradicting cutoff for Markov chains. Thus the Peres product condition holds:In fact the argument with ${\gamma }_{\ast ,n}$ proves the stronger absolute-gap product condition. Part (d) does not repeat the reversible Markov chain hypothesis; the ordinary real ordering of eigenvalues above uses that hypothesis. If arbitrary chains are intended, define the spectral gap explicitly: the eigenvalue lower bound for total variation mixing works for complex eigenfunctions too, and proves the same assertion for ${\gamma }_{\ast }$ or for $1-{\max }_{j\ge 2}\mathrm{Re}{\lambda }_j$, which is at least ${\gamma }_{\ast }$. No real ordering of complex eigenvalues is implicit.

For the requested counterexample take nonlazy simple random walk on the complete graph $K_n$, $n\ge 3$. Let $\Pi$ have every row equal to the uniform distribution on a finite set, and let $a=-1/(n-1)$. ThenThus $d_n(0)\to 1$ and $d_n(1)=1/n\to 0$: every fixed-level mixing time is eventually one. This is a bounded-time jump satisfying the ratio definition of cutoff. The ordinary spectral gap is $n/(n-1)$ and the absolute one is $(n-2)/(n-1)$, so both products with $T_n=1$ tend to one, not infinity. The divergence assumption on $T_n$ is therefore essential under this convention.

Using part ii and symmetry of the simple random walk,for $n\ge 1$. Thus $\mathbb{E}{M}_n^2<\mathbb{E}{X}_n^2=n$.

Choose a spanning tree $T$ of $G$, rooted at $a$. A depth-first traversal of a tree gives a deterministic closed walkthat traverses each edge of $T$ once in each direction and visits every vertex. Define stopping times $S_0=0$ andThe simple random walk is at $v_j$ at time $S_j$. All these hitting times have finite mean on the finite connected graph. By the Strong Markov property,The cover time is no larger than $S_{2(n-1)}$. Grouping the summands by the two traversals of each tree edge and applying the commute time identity givesThe effective resistances are measured in the original graph, where each tree-edge pair is adjacent. Part (a) therefore bounds every summand by one, soFor the one-vertex graph, the cover time is zero and the same bound is immediate.

Use the usual implicit convention that the infinite connected graph is a locally finite graph. This is needed for the simple random walk and the finite wired constructions to be defined. Choose finite vertex sets $V_1\subset V_2\subset \cdots$ exhausting $V$, with each induced subgraph $G[V_k]$ connected.

For the free uniform spanning forest, sample a uniform spanning tree of $G[V_k]$, using only the internal edges. Its limiting law on edge subsets of $G$ is the free uniform spanning forest measure:The limit is weak convergence of probability measures on $\{0,1{\}}^E$, equivalently convergence of every finite-edge event.

For the wired uniform spanning forest, form $G_k^{\mathrm{w}}$ by identifying every vertex outside $V_k$ to one boundary vertex ${\partial }_k$. Retain all edges with at least one endpoint in $V_k$, preserve parallel edges, and discard loops at ${\partial }_k$. Sample a uniform spanning tree of this finite multigraph and restrict it to the original internal edges. The limiting law isFor each fixed finite set of edges the restriction is unambiguous once $k$ is large. The standard exhaustion theorem guarantees that both limits exist and do not depend on the chosen connected exhaustion. Both are random spanning forests; despite their names, they need not be connected.

Fix a root $r$. On a recurrent graph, a simple random walk started at any vertex hits $r$ almost surely. Run Wilson's algorithm with root $r$: successively attach the loop-erased random walk from each new starting vertex, stopped when it hits the existing tree. Every walk terminates almost surely, because that tree already contains $r$.

To compare the two finite approximations, fix a finite set of edges $K$ and put all their endpoints first in the ordering of starting vertices. In the infinite graph, these finitely many Wilson's algorithm walks have finite lengths almost surely. Their visited vertices, together with their neighbors, are therefore contained in $V_k$ for all sufficiently large $k$ on each realization.

Couple the walks in $G[V_k]$, in $G_k^{\mathrm{w}}$, and in $G$ using the same neighbor choices while they are in the interior of $V_k$. On the event just described, they encounter neither boundary, so the walks, their chronological loop erasures, and the resulting partial trees agree. Once every endpoint of $K$ has entered the partial tree, later walks cannot add any edge of $K$: they stop on their first hit of the existing tree. Thus the indicators of membership for all edges of $K$ agree in the free and wired uniform spanning trees, with probability tending to one.

The two limiting measures agree on every finite-edge event, and thereforeThis argument also shows that the common uniform spanning forest is a single spanning tree on a recurrent graph. The equality refers to probability measures, not to independently sampled forests being identical.

Let $h_k$ be the probability that the simple random walk started at $k$ hits $n$ before zero. The first-step analysis recurrence and boundary conditions areIf $p\ne q$, the characteristic equation of a linear recurrence has roots $1$ and $q/p$, so the boundary conditions giveIf $p=q=1/2$, the repeated root gives the limiting formula $\boxed{h_m=m/n}$. This is the gambler's ruin probability.

For a fixed integer stake $a\le N$, the fact that $a$ divides $N!$ lets us measure Patricia's wealth in units of £$a$. She starts at $M=N!/a$ and succeeds upon reaching $2M$. The formula above factors asFor $p=18/37$, $r=19/18>1$, so this probability increases as $M$ decreases. She should therefore choose the largest stake, $\boxed{a=N}$. For $p=19/37$, $r=18/19<1$, so the probability increases as $M$ increases; she should choose the smallest stake, $\boxed{a=1}$.