Tutorials › Probability Theory (Graduate) › Harmonic Measure in Finite Domains

Home  /  Tutorials  /  Random Walks and Potential Theory

Random Walks and Potential Theory · Tutorial 937 of 946

Harmonic Measure in Finite Domains

Learn to define harmonic measure as an exit distribution and compute its boundary probabilities from first-step equations or expected visit counts.

Advanced 11 min read

What You'll Learn

  • Define the exit boundary and harmonic measure for a walk in a finite domain.
  • State conditions ensuring that the walk exits almost surely.
  • Prove that harmonic measure has total mass one and is harmonic inside the domain.
  • Express exit probabilities using expected visit counts and one-step transition probabilities.
  • Compute harmonic measure for an interval, a small lattice rectangle, and a finite graph domain.

Why the Exit Location Matters

A random walk in a finite region eventually reaches its exterior under a suitable accessibility condition. The location where it first exits is itself random, and its distribution records how the geometry of the region and the transition rules influence the walk.

This distribution is called harmonic measure. It answers questions more detailed than the probability of hitting one particular target: it assigns a probability to every possible exit point. The probabilities can be computed by conditioning on the first step, or by counting expected visits to interior states before exit.

Finite Domains and Their Exit Boundaries

Let \((X_n)_{n\geq 0}\) be a Markov chain on a countable state space \(V\), with transition probabilities \(P(x,y)=\mathbb P(X_{n+1}=y\mid X_n=x)\). Let \(D\subset V\) be finite. Its one-step exit boundary is

$$ \partial D=\{y\in V\setminus D:\ P(x,y)>0\text{ for some }x\in D\}. $$

Starting from \(x\in D\), define the exit time

$$ \tau_D=\inf\{n\geq 0:X_n\notin D\}. $$

For an initial state in \(D\), the event \(\{\tau_D<\infty\}\) means that the walk eventually exits. We will assume that this happens almost surely from each state in \(D\). A convenient sufficient condition is that from every \(x\in D\) there is a finite path of positive transition probability leading to \(V\setminus D\). Since \(D\) is finite, choose one such path from each state. Their lengths have a finite maximum \(m\), and the probabilities of following those paths have a positive minimum \(\delta\). Consequently, from any state in \(D\), the probability of exiting within \(m\) steps is at least \(\delta\); repeated conditioning gives \(\mathbb P_x(\tau_D>km)\leq(1-\delta)^k\), which tends to zero.

Definition: If \(\tau_D<\infty\) almost surely from every \(x\in D\), the harmonic measure of \(D\), viewed from \(x\), is the probability distribution on \(\partial D\) given by $$ \omega_D(x,y)=\mathbb P_x(X_{\tau_D}=y),\qquad y\in\partial D. $$

The exit location belongs to \(\partial D\): immediately before exit, the walk is at a state of \(D\), and its next transition has positive probability to the state it enters. Harmonic measure is therefore a probability distribution on the possible one-step exit points, not on all states outside \(D\).

Basic Properties of Harmonic Measure

For a fixed boundary point \(y\), the function \(x\mapsto\omega_D(x,y)\) is harmonic at interior states: its value at a state is the transition-weighted average of its values after one step, with the exit value set to one at \(y\) and zero at other boundary points.

Theorem: Under the almost-sure exit assumption, for every \(x\in D\), $$ \sum_{y\in\partial D}\omega_D(x,y)=1. $$ For \(x\in D\) and \(y\in\partial D\), $$ \omega_D(x,y)=\sum_{z\in D}P(x,z)\omega_D(z,y)+P(x,y). $$ Here \(P(x,y)=0\) for any \(y\notin\partial D\).
Proof. The exit location is almost surely a single element of \(\partial D\). The events \(\{X_{\tau_D}=y\}\), for \(y\in\partial D\), are disjoint and their union has probability one. Summing their probabilities proves the first identity. For the second identity, condition on \(X_1\). If \(X_1=y\), the walk has exited at \(y\), contributing \(P(x,y)\). If \(X_1=z\in D\), the walk has not exited, and the conditional probability of eventually exiting at \(y\) is \(\omega_D(z,y)\), by the Markov property. If \(X_1\) is a different boundary state, the exit location is already determined and is not \(y\). These cases give the stated equation.

\(\square\)

Equivalently, extend the function to \(V\setminus D\) by setting its value to one at \(y\) and zero at every other exterior state. Then its value at \(x\in D\) is the transition average of the extended function over the next state. This is the first-step equation for the exit probability.

Exit Probabilities from Expected Visit Counts

A second computation is useful when expected visits inside the domain are easier to find than the exit probabilities directly. Define the expected number of visits to \(z\in D\), before exit, by

$$ G_D(x,z)=\mathbb E_x\!\left[\sum_{n=0}^{\tau_D-1}\mathbf 1_{\{X_n=z\}}\right]. $$

This is the Green function killed on leaving \(D\); it counts visits at times strictly before exit. The following identity turns those visits into exit probabilities.

Theorem: For \(x\in D\) and \(y\in\partial D\), $$ \omega_D(x,y)=\sum_{z\in D}G_D(x,z)P(z,y). $$
Proof. For each \(n\geq 0\), exit at \(y\) on step \(n+1\) occurs exactly when \(n<\tau_D\), \(X_n=z\) for some \(z\in D\), and the next transition is from \(z\) to \(y\). These exit events, indexed by the exit time, are disjoint. Conditioning on the state at time \(n\) gives $$ \mathbb P_x(X_{\tau_D}=y) =\sum_{n=0}^{\infty}\sum_{z\in D} \mathbb P_x(n<\tau_D,\ X_n=z)P(z,y). $$ All terms are nonnegative, so the sums can be regrouped. For each \(z\), the sum over \(n\) of \(\mathbb P_x(n<\tau_D,\ X_n=z)\) is \(G_D(x,z)\), by the definition of expected visits. Substitution proves the formula.

\(\square\)

Worked Example: Harmonic Measure on an Interval

Worked Example: Harmonic Measure on an Interval

Consider the nearest-neighbor walk on \(\{0,1,\ldots,N\}\), with \(N\geq2\), and let \(D=\{1,\ldots,N-1\}\). From each interior state the walk moves right with probability \(p\) and left with probability \(q=1-p\), where \(0<p<1\). The exit boundary is \(\{0,N\}\). Write \(h(i)=\omega_D(i,N)\). The first-step equation gives \(h(i)=p h(i+1)+q h(i-1)\), with boundary values \(h(0)=0\) and \(h(N)=1\).

When \(p=q=1/2\), the equation says the successive differences \(h(i+1)-h(i)\) are constant. The boundary values make this constant \(1/N\), so \(h(i)=i/N\). Since exit occurs at either endpoint, \(\omega_D(i,0)=1-i/N\). For example, with \(N=5\) and \(i=2\), the exit probabilities are \(2/5\) at \(5\) and \(3/5\) at \(0\).

For \(p\ne q\), set \(r=q/p\). The equation implies that the differences satisfy \(h(i+1)-h(i)=r\bigl(h(i)-h(i-1)\bigr)\). Thus the differences form a geometric sequence, and summing them from \(0\) to \(N\) gives $$ h(i)=\frac{1-r^i}{1-r^N}. $$ For instance, if \(p=2/3\), \(q=1/3\), and \(N=3\), then \(r=1/2\) and \(h(1)=(1-1/2)/(1-1/8)=4/7\). The probability of exiting at \(0\) is \(1-h(1)=3/7\). Both probabilities are nonnegative and sum to one.

Worked Example: A Rectangular Lattice Domain

Worked Example: A Two-by-Two Rectangle in the Square Lattice

Let the walk be simple random walk on \(\mathbb Z^2\), moving to each of its four nearest neighbors with probability \(1/4\). Take the rectangular domain \(D=\{(0,0),(1,0),(0,1),(1,1)\}\). Its exit boundary consists of the eight points $$ (-1,0),(0,-1),(1,-1),(2,0),(2,1),(1,2),(0,2),(-1,1). $$ Start at \((0,0)\). To use the expected-visit formula, let \(v_{ij}=G_D((0,0),(i,j))\). By symmetry, \(v_{10}=v_{01}=y\). Write \(v_{00}=x\) and \(v_{11}=z\). The visit-count equations \(v=\delta_{(0,0)}+vQ\), where \(Q\) is the transition matrix restricted to \(D\), become $$ x=1+\frac{y}{2},\qquad y=\frac{x+z}{4},\qquad z=\frac{y}{2}. $$ Substituting \(z=y/2\) into the second equation gives \(y=x/4+y/8\), so \(y=2x/7\). The first equation then gives \(x=1+x/7\), hence \(x=7/6\), \(y=1/3\), and \(z=1/6\).

Each boundary point is reached by a single transition from one interior point. The two points \((-1,0)\) and \((0,-1)\) each have exit probability \(x/4=7/24\). The four points \((1,-1),(2,0),(-1,1),(0,2)\), adjacent to \((1,0)\) or \((0,1)\), each have probability \(y/4=1/12\). The remaining points \((2,1)\) and \((1,2)\), adjacent to \((1,1)\), each have probability \(z/4=1/24\). Their total mass is $$ 2\left(\frac{7}{24}\right)+4\left(\frac{1}{12}\right)+2\left(\frac{1}{24}\right)=1. $$ The asymmetry between the lower-left and upper-right sides reflects the starting point, not a difference in the walk's transition probabilities.

Worked Example: A Domain in a Finite Graph

Worked Example: Exit from Two Adjacent Vertices of a Cycle

Consider simple random walk on the four-cycle with vertices \(a,b,c,d\) and edges \(a\!-\!b\), \(b\!-\!c\), \(c\!-\!d\), \(d\!-\!a\). Take \(D=\{a,b\}\), so \(\partial D=\{c,d\}\). Starting from \(a\), let \(h(a)\) and \(h(b)\) be the probabilities of exiting at \(c\). From \(a\), the walk exits immediately at \(d\) with probability \(1/2\), or moves to \(b\). From \(b\), it exits at \(c\) with probability \(1/2\), or moves back to \(a\). Thus $$ h(a)=\frac12h(b),\qquad h(b)=\frac12+\frac12h(a). $$ Substitution yields \(h(a)=1/4+h(a)/4\), so \(h(a)=1/3\). Therefore \(\omega_D(a,c)=1/3\) and \(\omega_D(a,d)=2/3\). The latter is larger because \(d\) is reachable in one step from the starting vertex, whereas reaching \(c\) requires first moving to \(b\).

Interpretation and a Common Pitfall

Harmonic measure depends on three ingredients: the transition probabilities, the chosen domain, and the starting point. Even if the walk is symmetric, the exit distribution need not assign equal probabilities to boundary points. Boundary points can differ in how many interior states lead to them, and the walk may spend different expected amounts of time at those states before exiting.

A frequent error is to confuse the probability of visiting a boundary point at some time with the probability of exiting there. In the examples, a point in \(\partial D\) is outside \(D\), so the first time the walk reaches it is the exit time. A point farther outside might be reached only after the walk has already exited; it is not an exit point in the definition of \(\omega_D\).

The two computational viewpoints serve different purposes. First-step equations are compact when the domain has few states or strong symmetries. Expected visit counts are useful when the killed transition matrix or its visit-count equations are manageable. Both methods calculate the same distribution, and the total-mass identity provides a basic consistency check.

Check Your Understanding

Use the definitions and computations above to answer the following questions.

  1. What is the exit boundary of a domain in a Markov chain, and why must the exit location belong to it?
  2. What accessibility condition ensures almost-sure exit from a finite domain? Explain why finiteness matters in the argument.
  3. For a symmetric nearest-neighbor walk on \(\{0,\ldots,N\}\), what is the probability of exiting at \(N\) when starting at \(i\)?
  4. In the two-by-two lattice rectangle, why is the probability of exiting at \((-1,0)\) equal to \(G_D((0,0),(0,0))/4\)?
  5. For a domain \(D\), explain how expected visits to an interior state contribute to the probability of exiting at a specified boundary point.

Previous

Next

Back to Tutorials
Clinical Biostats