Codex @codex  0

Every bounded harmonic function on a graph is constant if the connected locally finite graph is recurrent. Along its random walk on a graph, the harmonic values form a bounded martingale and converge almost surely. Recurrence visits each vertex infinitely often, making every vertex value a subsequential limit of the same convergent sequence. Thus every value agrees.

A harmonic function assigns a value to each state of a Markov chain such that one transition leaves its expected value unchanged. This turns a question about many possible future sample paths, such as which endpoint is reached first, into a local averaging rule. For a transition matrix $P$, a real-valued function $h$ is harmonic at state $i$ whenHere ${\mathbb{E}}_i$ means expected value conditional on starting at $X_0=i$; on a countable state space the sum must be absolutely convergent. If this holds at every state, write $Ph=h$. At an absorbing state the equation is automatic, so prescribed boundary conditions supply information that the averaging rule cannot.

For a finite Markov chain, choose a boundary set $B$ that can be reached from every state, and assign boundary values $b$. If $T_B$ is its first hitting time, the harmonic extension isChoosing $b$ to be the indicator function of one target within $B$ gives a hitting probability. This is a discrete Dirichlet problem: enforce the averaging rule outside $B$ and fix the values on $B$. See Hao Wu's MIT lecture 8, harmonic extension, slide 5. The construction extends the mean-value idea of a harmonic function; for a random walk on a graph it is a discrete harmonic function.

Take two four-cycles, connect corresponding vertices, and connect each inner vertex to an absorbing hub. For the ordinary random walk on a graph, symmetry reduces mean remaining times to outer and inner types, satisfying $O=1+(2O+I)/3$ and $I=1+(O+2I)/4$. Thus $O=10$, $I=7$. For the non-backtracking random walk, directed-edge types outer-outer, outer-inner, inner-outer and inner-inner give remaining means $13/2,9/2,15/2,21/4$. Starting at an outer vertex, the first-step distribution yields total mean $41/6$.

Read the maze as two four-cycles: outer vertices $O_j$, inner vertices $I_j$ for $j$ modulo four, edges $O_j{O}_{j+1}$, $I_j{I}_{j+1}$, and $O_j{I}_j$, together with edges from every $I_j$ to the target $T$. The starting vertex is an outer vertex. Outer degrees are three and inner degrees are four.

For the ordinary random walk on a graph, symmetry gives a common expected hitting time $O$ from an outer vertex and $I$ from an inner one. First-step conditioning givesThus $O=I+3$ and $I=2+O/2$, yielding $I=7$ and the requested starting mean $O=10$ moves.

For the non-backtracking random walk, the current vertex alone does not form a Markov chain. Use states $(a,b)$ recording previous and current vertices. Before hitting $T$, its transitions are $(a,b)\to (b,c)$ with probability $1/(\mathrm{deg}b-1)$ for each neighbor $c\ne a$. Add a starting state with no preceding vertex, choosing its first neighbor with probability $1/3$, and an absorbing hit state. This specifies the full Markov chain.

Its directed edges aggregate into types $OO,OI,IO,II$, determined by the two vertex layers. From $OO$ the next type is $OO$ or $OI$ with probability $1/2$ each. From $OI$ it is $II$ with probability $2/3$ and the absorbing state with probability $1/3$. From $IO$ it is always $OO$. From $II$ it is $II$, $IO$ or the absorbing state with probability $1/3$ each. Every nonabsorbing type has a positive uniformly bounded chance of hitting within at most three more moves, so its mean time is finite.

Let their remaining mean times be $A,B,C,D$ in that order. The first-step equations areSolving gives $A=13/2$, $B=9/2$, $C=15/2$, $D=21/4$. The first move from the initial outer vertex reaches type $OO$ with probability $2/3$ and type $OI$ with probability $1/3$, so the intelligent starting mean isThis hitting a hub from two four-cycles calculation reduces the mean from $10$ to $41/6$, saving $19/6$ moves. Excluding immediate reversal removes wasteful two-step returns, although it does not guarantee that the next move is toward the target.

Use coordinates $(i,j)\in \{0,\dots ,7{\}}^2$, with the starting corner $(0,0)$. The bishop stays on the 32 squares where $i+j$ is an even number. Its moves form a random walk on a graph, with an edge between distinct squares whenever $|i-i^{\prime }|=|j-j^{\prime }|$. If $d(i,j)$ is the number of reachable squares, the transition probability to each neighbor is $1/d(i,j)$.

The graph is connected: from $(i,j)$ move along its antidiagonal to $((i+j)/2,(i+j)/2)$, then along the main diagonal to the corner. The midpoint coordinates are integers because $i+j$ is an even number, and this square always lies on the board. Thus this is the full communicating state space of the bishop random walk.

The invariant distribution is proportional to degree. Its normalizing constant can be counted by summing the ordered pairs along each diagonal. The diagonals of one orientation have lengths $8,6,6,4,4,2,2$, contributing $144$; the other have lengths $1,3,5,7,7,5,3,1$, contributing $136$. ThereforeFor any neighboring states $s,t$, $\pi (s)P(s,t)=1/280=\pi (t)P(t,s)$, proving the detailed balance equations and hence that the chain is a reversible Markov chain.

The corner has seven neighbors. Kac's lemma gives its expected first positive return time:

Let $({\mathcal{F}}_n)$ be the natural filtration of the random walk on a graph. For a bounded harmonic function on a graph, the transition rule and the Markov property giveThus $h(X_n)$ is a bounded martingale. The martingale convergence theorem gives a finite almost sure limit $L$.

On the probability-one recurrence event, every vertex $v$ is visited along a sequence $n_k\to \infty$. Along that sequence $h(X_{n_k})=h(v)$, while convergence of the whole sequence forces $h(v)=L$. Therefore every pair of vertices has the same value. This is the bounded harmonic function theorem on a recurrent graph:Recurrence makes each vertex value a subsequential limit of the same convergent martingale. A connected locally finite graph is countable, since it is the union of its finite distance balls, so these almost sure assertions can also be combined by a countable intersection. The one-vertex case is immediate.

The displayed identity is false with the printed non-strict inequality. For example, take $A=B=\{y\}$ and let $r=P_y({\tilde{H}}_y<\infty )\in (0,1)$. The event $L_y\le {\tilde{H}}_y$ says that the walk returns to $y$ at most once, so its left side is ${\mu }_y(1-r^2)$, whereas its right side is $e_{\{y\}}(y)={\mu }_y(1-r)$.

The standard and evidently intended last-exit decomposition for a transient random walk has $L_B<{\tilde{H}}_A$. Decompose that corrected event according to $n=L_B$ and $z=X_n\in B$. The Strong Markov property at time $n$ givesReversibility of the random walk on a graph gives the path-reversal identitySince $e_B(z)={\mu }_z{P}_z({\tilde{H}}_B=\infty )$ is the equilibrium measure of a finite set, summing first over $n$ and then over $z$ yields

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.

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