Dirichlet Problems from Exit Distributions

From Boundary Data to an Interior Solution

A Dirichlet problem prescribes values on the boundary of a domain and asks for a function inside the domain that is harmonic: at each interior state, its value is the transition-weighted average of its values after one step. A random walk turns this averaging rule into a probabilistic formula. Starting at an interior state, follow the walk until it first exits; the solution at the starting state is the expected value of the prescribed boundary data at that exit point.

For this representation to be a genuine solution, the walk must exit with probability one. Finiteness of the domain alone does not ensure that: a chain could remain forever in a closed class inside it. We first state a condition that guarantees exit, then prove the representation and uniqueness.

Finite Domains and Their Exit Boundaries

Let $(X_n)_{n\geq 0}$ be a time-homogeneous Markov chain on a finite state space $E$, with transition probabilities $P(x,y)=\mathbb{P}(X_{n+1}=y\mid X_n=x)$. Let $D\subsetneq E$ be a nonempty set of interior states, and put $B=E\setminus D$. For a starting state $x$, write $\mathbb{P}_x$ and $\mathbb{E}_x$ for probability and expectation when $X_0=x$.

Definition: The first exit time from $D$ is $\tau_B=\inf\{n\geq 0:X_n\in B\}$. For $x\in D$, the exit distribution assigns to $y\in B$ the probability $\mathbb{P}_x(X_{\tau_B}=y)$, provided $\tau_B$ is finite almost surely.

In a nearest-neighbor walk, $B$ can be taken to include the states just outside the domain that the walk can reach in one step. More generally, using all of $E\setminus D$ is convenient: states in $B$ that cannot be reached on exit simply have exit probability zero. Boundary data are a function $g:B\to\mathbb{R}$. The associated finite-domain Dirichlet problem is to find $u:E\to\mathbb{R}$ such that $u=g$ on $B$ and

u(x)=\sum_{y\in E}P(x,y)u(y),\qquad x\in D.

The equation says that the value at an interior state equals the expected value after one transition. Values on $B$ are prescribed rather than determined by this equation.

When Is Exit Guaranteed?

For a finite state space, a useful sufficient condition is that every interior state can reach $B$ along a path of positive-probability transitions. The path may be chosen to have no repeated interior state, so its length is at most $|D|$. Since there are finitely many starting states, the smallest of the positive probabilities of following these chosen paths is positive.

Proposition: Suppose that for every $x\in D$ there is a finite path from $x$ to $B$ whose transition probabilities are all positive. Then $\tau_B<\infty$ almost surely from every $x\in D$, and $\mathbb{E}_x[\tau_B]<\infty$.

Proof. For each $x\in D$, choose a path to $B$ with no repeated interior state. Let $M=|D|$, and let $\delta_x>0$ be the probability of following the chosen path from $x$. Its length is at most $M$, so the probability of exiting within the next $M$ steps, starting from any state in $D$, is at least $\delta=\min_{x\in D}\delta_x>0$. The minimum is positive because $D$ is finite.

Apply the Markov property at times $M,2M,\ldots$. Conditional on not yet having exited by time $kM$, the chain is in $D$, and its conditional probability of remaining in $D$ for the next $M$ steps is at most $1-\delta$. Therefore, for every integer $k\geq 0$,

\mathbb{P}_x(\tau_B>kM)\leq (1-\delta)^k.

The right-hand side tends to zero, so $\mathbb{P}_x(\tau_B=\infty)=0$. The same geometric tail bound implies finite expectation: grouping the tail probabilities into blocks of $M$ consecutive times gives $\mathbb{E}_x[\tau_B]\leq M\sum_{k\geq 0}(1-\delta)^k=M/\delta$. $\square$

The Exit-Distribution Representation

Theorem: Under the path condition of the proposition, for any boundary data $g:B\to\mathbb{R}$, the unique solution of the finite-domain Dirichlet problem is $$ u(x)=\mathbb{E}_x[g(X_{\tau_B})],\qquad x\in D, $$ together with $u=g$ on $B$.

Proof. Since $B$ is finite and $g$ is real-valued, $g$ is bounded. The proposition shows that $\tau_B$ is almost surely finite, so the expectation in the formula is well-defined. Define $u=g$ on $B$ and define $u(x)=\mathbb{E}_x[g(X_{\tau_B})]$ for $x\in D$.

For $x\in D$, condition on the first transition. If the chain moves to $y\in B$, its exit point is $y$. If it moves to $y\in D$, the remaining process has the law of the chain started from $y$. The Markov property therefore gives

\mathbb{E}_x[g(X_{\tau_B})] =\sum_{y\in B}P(x,y)g(y) +\sum_{y\in D}P(x,y)\mathbb{E}_y[g(X_{\tau_B})] =\sum_{y\in E}P(x,y)u(y).

Thus $u$ satisfies the harmonic equation and the prescribed boundary values.

To prove uniqueness, let $v$ be any other solution and set $h=v-u$. Then $h=0$ on $B$, and $h(x)=\sum_yP(x,y)h(y)$ for $x\in D$. The stopped process $h(X_{n\wedge\tau_B})$ is a martingale: before exit, its conditional expected next value is $h(X_n)$ by the harmonic equation, and after exit it stays constant. Because $E$ is finite, this process is bounded. Hence for each $n$, $\mathbb{E}_x[h(X_{n\wedge\tau_B})]=h(x)$. Almost surely, $\tau_B<\infty$, so $h(X_{n\wedge\tau_B})$ tends to $h(X_{\tau_B})=0$. Bounded convergence gives $h(x)=0$. This holds for every $x\in D$, proving uniqueness. $\square$

The formula is not just a way to produce a harmonic function: it identifies the unique one. It also describes the solution as a weighted average of boundary values, with weights given by the exit probabilities. This is the probabilistic form of the finite-domain Dirichlet problem.

Worked Example: A Biased Walk on an Interval

Consider the walk on $E=\{0,1,2,3,4,5\}$ that moves one step right with probability $2/3$ and one step left with probability $1/3$, with $0$ and $5$ absorbing. Take $D=\{1,2,3,4\}$, and prescribe $g(0)=2$ and $g(5)=11$. Let $q_i$ be the probability, starting at $i$, of exiting at $5$. Then $q_0=0$, $q_5=1$, and for $1\leq i\leq4$, $q_i=(2/3)q_{i+1}+(1/3)q_{i-1}$.

The characteristic equation for this recurrence has roots $1$ and $1/2$, giving $q_i=A+C(1/2)^i$. The boundary conditions yield $A+C=0$ and $A+C/32=1$, so $A=32/31$ and $C=-32/31$. Thus $q_i=(1-(1/2)^i)/(1-(1/2)^5)$. In particular, $q_2=(3/4)/(31/32)=24/31$. The exit value is $11$ with probability $24/31$ and $2$ otherwise, so

u(2)=11\frac{24}{31}+2\frac{7}{31}=\frac{278}{31}.

Equivalently, $u(i)=2+9q_i$. Since $q_i$ satisfies the harmonic recurrence and has the required endpoint values, this function solves the Dirichlet problem. In particular, $u(0)=2$ and $u(5)=11$, as prescribed.

Worked Example: Two Interior States in a Grid

Take the nearest-neighbor simple random walk on the rectangular grid $E=\{0,1,2,3\}\times\{0,1,2\}$, with equal probabilities for the available moves at the two interior states below. Let $D=\{A,B\}$, where $A=(1,1)$ and $B=(2,1)$; all other grid vertices form $B_{\!D}=E\setminus D$, the exit boundary. (The subscript distinguishes this boundary set from the state named $B$.) Prescribe the values $g(0,1)=1$, $g(1,0)=0$, $g(1,2)=2$, $g(3,1)=3$, $g(2,0)=1$, and $g(2,2)=0$. Values at other boundary vertices do not affect the calculation because they are not one-step neighbors of $A$ or $B$.

Each interior vertex has four neighbors. The Dirichlet equations are therefore

u(A)=\frac{1+0+2+u(B)}{4}=\frac{3+u(B)}{4}, \qquad u(B)=\frac{3+1+0+u(A)}{4}=\frac{4+u(A)}{4}.

Substituting the second equation into the first gives $u(A)=(3+1+u(A)/4)/4$, hence $15u(A)/16=1$ and $u(A)=16/15$. Then $u(B)=1+u(A)/4=19/15$. These are also the expected boundary values at the exit point: the theorem identifies each solution value with that expectation, while the equations compute those expectations through one-step conditioning.

Worked Example: Exit Probabilities in a Finite Chain

Let $E=\{a,b,L,R\}$, with interior $D=\{a,b\}$ and boundary $\{L,R\}$. From $a$, the chain moves to $L,b,R$ with probabilities $1/4,1/2,1/4$; from $b$, it moves to $L,a,R$ with probabilities $1/2,1/4,1/4$. The boundary states can be made absorbing. From either interior state there is a probability at least $1/4$ of exiting on the next step, so exit occurs almost surely. Set $g(L)=0$ and $g(R)=6$.

Write $r_a=\mathbb{P}_a(X_{\tau_B}=R)$ and $r_b=\mathbb{P}_b(X_{\tau_B}=R)$. Conditioning on the first step gives

r_a=\frac12r_b+\frac14,\qquad r_b=\frac14r_a+\frac14.

Substitute the second equation into the first: $r_a=r_a/8+3/8$, so $r_a=3/7$, and then $r_b=5/14$. Since the boundary value is six at $R$ and zero at $L$, the exit-value expectations are $u(a)=6r_a=18/7$ and $u(b)=6r_b=15/7$. Checking the harmonic equations directly gives $u(a)=u(b)/2+3/2=18/7$ and $u(b)=u(a)/4+3/2=15/7$, as required.

Boundary Values, Exit Points, and a Common Pitfall

The exit distribution determines how strongly each boundary value influences the solution: if $p_x(y)=\mathbb{P}_x(X_{\tau_B}=y)$, then $u(x)=\sum_{y\in B}p_x(y)g(y)$. These probabilities are nonnegative and sum to one, so every interior solution value lies between the smallest and largest boundary values. This is consistent with the discrete maximum principle.

A frequent error is to assign data only to a visually chosen edge while ignoring where the chain can actually go on its first step out of the domain. For walks with jumps, an exit may overshoot that edge. The boundary for the probabilistic formula must include every possible exit state, and the boundary data must be specified there. Another necessary check is that exit really occurs: if the chain has a closed class contained in $D$, the exit expectation may not be defined and the representation theorem does not apply as stated.

For a finite domain satisfying the path condition, the representation gives both existence and uniqueness without requiring a separate guess for the interior values. One can compute the exit probabilities directly, solve the harmonic equations, or use whichever description is most convenient. In each case, the solution is the average boundary value seen by the walk at its first exit.

Check Your Understanding

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

What condition on paths from interior states to the boundary ensures almost-sure exit in the finite-state setting?
Why does conditioning on the first step yield the harmonic equation for the expected exit value?
In the biased interval example, what is the probability of exiting at $5$ when starting at $2$, and how does it give $u(2)$?
Why does a harmonic solution with zero boundary data have to vanish under the theorem’s assumptions?
Why can a walk with jumps require boundary data at states beyond a visually chosen edge?