Discrete Harmonic Functions and First-Step Equations

From One-Step Transitions to Boundary-Value Equations

A random walk on a graph evolves one transition at a time, but many questions concern what happens when it reaches a specified set. For example, starting from a vertex in a domain, what is the probability that the walk exits through one part of the boundary? How long does it take, on average, to reach the boundary?

The transition operator provides a direct way to express these quantities. A function that is unchanged by one application of this operator is called harmonic. Hitting probabilities are harmonic away from the boundary, while expected hitting times satisfy a related equation with an additional constant term.

Harmonic Functions for a Markov Chain

Let $S$ be a finite or countable state space, and let $P(x,y)$ be the transition probability from $x$ to $y$. For a bounded function $f:S\to\mathbb{R}$, the transition operator is

(Pf)(x)=\sum_{y\in S}P(x,y)f(y).

The sum is well-defined for bounded $f$, since the transition probabilities are nonnegative and sum to one. This operator gives the conditional expected value of $f$ after one step, given the current state.

Definition: Given a subset $D\subseteq S$, a function $f:S\to\mathbb{R}$ is harmonic on $D$ if its value at each state in $D$ equals its one-step conditional average. In symbols, $$ (Pf)(x)=f(x),\qquad x\in D. $$

When the chain is a simple random walk on a locally finite graph, each neighbor of $x$ is chosen with equal probability. Harmonicity then says that the value at $x$ is the average of the values at its neighbors. For a general Markov chain, the average is weighted by the transition probabilities.

Often, values are specified on a boundary $B\subseteq S$, and the question is to find a harmonic function on the remaining domain $D=S\setminus B$. The specified boundary values encode the event or quantity being studied.

First-Step Equations for Hitting Probabilities

For a set $B$, define its hitting time by $\tau_B=\inf\{n\in\mathbb{N}_0:X_n\in B\}$, with the infimum of the empty set taken to be infinity. Let $A\subseteq B$ be the part of the boundary designated as a successful exit. Define $h(x)$ to be the probability, starting at $x$, that the walk first reaches $B$ in $A$. If the walk never reaches $B$, this event does not occur.

Theorem: The hitting probability $h$ has boundary values $h(x)=1$ for $x\in A$ and $h(x)=0$ for $x\in B\setminus A$. At every $x\notin B$, it satisfies the first-step equation $$ h(x)=\sum_{y\in S}P(x,y)h(y)=(Ph)(x). $$

Proof. If $x\in A$, the walk has already reached the designated part of the boundary, so $h(x)=1$. If $x\in B\setminus A$, it has already reached the boundary at an unsuccessful state, so $h(x)=0$. Now fix $x\notin B$. Condition on the state $X_1$. Given $X_1=y$, the probability of eventual success is $h(y)$: if $y\in B$, this is precisely the boundary value; otherwise the chain continues from $y$ with the same transition law. Summing over the possible first states gives $$ h(x)=\sum_{y\in S}\mathbb{P}_x(X_1=y)h(y) =\sum_{y\in S}P(x,y)h(y). $$ This argument does not require that $B$ be reached almost surely. If it is not reached, the event of reaching $B$ in $A$ simply fails. $\square$

This is a local equation: the value at a state depends on the values at states that can follow it in one step. The boundary values distinguish the particular event whose probability is being computed. In particular, if $A$ and $C$ are disjoint and $B=A\cup C$, then $h$ gives the probability of reaching $A$ before $C$.

Worked Example: A Hitting Probability on a Path

Consider the path with states $0,1,2,3$, where $0$ and $3$ are boundary states. From state $1$, the chain moves to $0$ with probability $1/3$ and to $2$ with probability $2/3$. From state $2$, it moves to $1$ with probability $1/4$ and to $3$ with probability $3/4$. Let $h(i)$ be the probability of reaching $3$ before $0$. The boundary values are $h(0)=0$ and $h(3)=1$. The first-step equations are

h(1)=\frac{2}{3}h(2),\qquad h(2)=\frac{1}{4}h(1)+\frac{3}{4}.

Substitute the second equation into the first:

h(1)=\frac{2}{3}\left(\frac{1}{4}h(1)+\frac{3}{4}\right) =\frac{1}{6}h(1)+\frac{1}{2}.

Thus $h(1)=3/5$, and then $h(2)=\frac14(3/5)+\frac34=9/10$. Checking the original equations gives $\frac23(9/10)=3/5$ and $\frac14(3/5)+3/4=9/10$, as required.

First-Step Equations for Expected Hitting Times

Probability is not the only quantity that can be found by conditioning on the first step. Let $\tau_B$ be the hitting time of a boundary $B$, and define $e(x)=\mathbb{E}_x[\tau_B]$, allowing the value infinity. At a boundary state the remaining time is zero. At a state outside the boundary, one step is taken before the chain can continue.

Theorem: For $x\in B$, $e(x)=0$. For $x\notin B$, the expected hitting time satisfies the extended-value equation $$ e(x)=1+\sum_{y\in S}P(x,y)e(y). $$ In particular, this is an ordinary finite-valued equation wherever the expectation is finite.

Proof. If $x\in B$, then $\tau_B=0$, so $e(x)=0$. If $x\notin B$, the first step contributes one unit of time. Conditional on $X_1=y$, the expected additional time to reach $B$ is $e(y)$, including the value zero when $y\in B$. Therefore, conditioning on $X_1$ yields $$ \mathbb{E}_x[\tau_B] =1+\sum_{y\in S}\mathbb{P}_x(X_1=y)e(y) =1+\sum_{y\in S}P(x,y)e(y). $$ For nonnegative extended expectations, the equality remains valid if a term or the total expectation is infinite. $\square$

The constant $1$ matters: unlike a hitting probability, an expected time is not harmonic. It solves an inhomogeneous equation, often written $e=1+Pe$ on the interior. One should not infer from a solution to this equation alone that the expected time is finite; finiteness needs justification.

Worked Example: Expected Exit Time from a Path

Use the path chain from the previous example, and let $e(i)$ be the expected number of steps to hit either $0$ or $3$. The boundary values are $e(0)=e(3)=0$. At the two interior states,

e(1)=1+\frac{2}{3}e(2),\qquad e(2)=1+\frac{1}{4}e(1).

Substituting the second equation into the first gives $$ e(1)=1+\frac{2}{3}\left(1+\frac14e(1)\right) =\frac53+\frac16e(1), $$ so $e(1)=2$. Consequently $e(2)=1+\frac14(2)=3/2$. Direct substitution verifies $1+\frac23(3/2)=2$ and $1+\frac14(2)=3/2$. These are finite expectations because from either interior state there is a positive probability of exiting within a bounded number of steps; repeated trials make the probability of remaining inside decay geometrically.

A Tree Example: Hitting a Specified Leaf

On a tree, the equations reflect the degree of each vertex. Consider a tree with root $r$, children $u$ and $v$, and leaves $x,y,z$, where $u$ is adjacent to $r,x,y$, and $v$ is adjacent to $r,z$. Run simple random walk and stop when it first reaches a leaf. Let $h$ be the probability of stopping at $x$. The boundary values are $h(x)=1$, $h(y)=h(z)=0$. Each interior value is the average over neighboring vertices, so $$ h(u)=\frac{h(r)+1+0}{3},\qquad h(v)=\frac{h(r)+0}{2},\qquad h(r)=\frac{h(u)+h(v)}{2}. $$

Substitution into the root equation gives $$ h(r)=\frac12\left(\frac{h(r)+1}{3}+\frac{h(r)}{2}\right), $$ hence $h(r)=2/7$. It follows that $h(u)=3/7$ and $h(v)=1/7$. Checking each equation: $(2/7+1)/3=3/7$, $(2/7)/2=1/7$, and $(3/7+1/7)/2=2/7$. Thus the probability of stopping at $x$ from the root is $2/7$.

Finite Domains: Finiteness and Uniqueness

On a finite state space, a useful condition guarantees that the boundary is reached in finite expected time. Suppose that from every state in $D=S\setminus B$, there is a path to $B$ whose transitions all have positive probability. Since $D$ is finite, one can choose one such path from each state. The path lengths have a finite maximum $L$, and their probabilities have a positive minimum $\eta$. Thus, from any interior state, the probability of reaching $B$ within $L$ steps is at least $\eta$. Applying the Markov property in successive blocks gives $$ \mathbb{P}_x(\tau_B>kL)\leq (1-\eta)^k,\qquad k\in\mathbb{N}_0. $$ This geometric bound implies $\mathbb{E}_x[\tau_B]<\infty$.

Theorem: Under the finite-state path-to-boundary condition just described, there is at most one function on $S$ that takes prescribed values on $B$ and is harmonic on $D$.

Proof. Suppose $f$ and $g$ both have the prescribed boundary values and are harmonic on $D$. Set $v=f-g$; then $v=0$ on $B$ and $v=Pv$ on $D$. Let $Q(x,y)=P(x,y)$ for $x,y\in D$. The interior equations imply $v=Qv$ on $D$, and iteration gives $v=Q^n v$ for every positive integer $n$. If $M=\max_{y\in D}|v(y)|$, then $$ |v(x)|\leq M\sum_{y\in D}Q^n(x,y) =M\,\mathbb{P}_x(\tau_B>n). $$ The block bound above implies that this probability tends to zero as $n$ tends to infinity. Hence $v(x)=0$ for every $x\in D$, and $f=g$ on all of $S$. $\square$

This result ensures uniqueness, not just a method for solving the equations. The hitting probability itself supplies a solution for its boundary data. The expected exit time supplies a solution to the corresponding inhomogeneous equation when the stated finiteness condition holds.

Worked Example: Expected Exit Time in a Finite Domain

Consider two interior states $a,b$ and boundary states $g,d$. From $a$, the chain moves to $g$ with probability $1/2$ and to $b$ with probability $1/2$. From $b$, it moves to $a,g,d$, each with probability $1/3$. Let $t(a)$ and $t(b)$ be the expected times to reach $\{g,d\}$. The equations are

t(a)=1+\frac12t(b),\qquad t(b)=1+\frac13t(a).

Substitution yields $t(a)=1+\frac12(1+\frac13t(a))=\frac32+\frac16t(a)$, so $t(a)=9/5$. Then $t(b)=1+\frac13(9/5)=8/5$. Checking gives $1+\frac12(8/5)=9/5$ and $1+\frac13(9/5)=8/5$. The boundary values are zero. Exit is almost sure with finite expectation: from either interior state there is a positive-probability route to the boundary in at most two steps, so the finite-domain bound applies.

Why the Equations Need Their Conditions

First-step conditioning is simple, but it does not by itself guarantee that a proposed system of equations uniquely determines the desired quantity. On an infinite domain, a boundary may never be reached, and different harmonic functions can share the same boundary values. Even when a first-step equation is valid, one must distinguish the probabilistically defined solution from any other algebraic solution unless suitable conditions ensure uniqueness.

For finite domains, checking that every interior state has a positive-probability route to the boundary is a practical safeguard. It gives finite expected exit time and ensures uniqueness for the harmonic boundary problem. The equations then translate a probabilistic question into a finite system of linear equations, while the probabilistic definitions tell us which solution the system represents.

Check Your Understanding

Try answering these questions by writing the relevant first-step equations before calculating.

What does it mean for a function to be harmonic on a subset of a Markov chain's state space?
How do the boundary values encode the probability of reaching one part of a boundary before another?
Why does the expected hitting-time equation contain an added $1$, while the hitting-probability equation does not?
For the tree example, what equation would change if the walk chose neighbors with unequal transition probabilities?
Why does a positive-probability path from every state in a finite domain to its boundary imply finite expected exit time?