Consider the following Dirichlet problem on the unit square :
where is a given function on the boundary.
To get an approximate solution, we may replace the unit square by a grid. Let be large and set . The grid points are
Next, we replace the Laplacian by a finite difference operator:
And the Dirichlet problem is replaced by the following system of linear equations:
As , we may expect that the solution tends to the solution of the original problem.
Now let be any function on the grid. The operator
is called the discrete Laplacian on the grid.
Note that the averaging operator also arises as the transition function of the simple random walk on the grid. Suppose moves around the grid randomly and stops when it hits the boundary. If is at an interior grid point , then in the next step it jumps to one of the neighboring points with equal probability. Then
We shall see that this is no coincidence. In fact, we shall interpret the solution in terms of the random walk.
Now we generalize the above situation. Let be a finite set, called the state space.
Definition. A transition function on is a matrix such that for all and for all .
We may also say that is a stochastic matrix, but we emphasize that it is an operator of functions (column vectors) on :
If then .
(Note: It is also an operator of measures (row vectors) on :
If then .
But we shall not need this here.)
Let be the identity operator (or matrix). We think of as the discrete Laplacian. This motivates:
Definition. Let and . We say that is superharmonic on if for all . If equality holds everywhere on , we say that is harmonic on .
Now we may formulate the Dirichlet problem. Let and . Let be a given function on . The Dirichlet problem is to find such that
The first condition says that is harmonic on .
We shall formulate conditions such that the problem can be uniquely solved. To see that such conditions are necessary, suppose that , and . Then any function on is harmonic and we are free to choose . The problem here is that does not connect to .
Definition. We say that the pair is irreducible if for any , there exists a path such that for all .
Proposition (uniqueness). Assume that is irreducible. Then the solution of the Dirichlet problem is unique.
Proof: Suppose and are solutions to the Dirichlet problem. We show that . Suppose that attains its maximum at . Then from
we see that whenever . If one of such lies in , then and we are done. If not, we iterate until we hit a point in . Similarly, the minimum is also . Hence .
(Note: The method of proof is the discrete analogue of the classical maximum principle.)
From now on we assume that is irreducible. How about existence?
In matrix form, the Dirichlet problem can be written as
where and . Hence, if the matrix is invertible, then
(This also yields uniqueness.)
It is possible to prove analytically (try) that the inverse exists, but we shall switch to probabilistic language. We first define a Markov chain that corresponds to the transition function .
Let be the space of all paths from to . For each , let be the -th projection map, i.e.
Finally, let be the sigma-field on generated by sets of the form , where . We need the following existence theorem.
Theorem (Kolmogorov). For any probability measure on , there exists a unique probability measure on such that for ,
For , we write .
The stochastic process is called the Markov chain on with transition function . We think of as the position of a random particle at time , and as the probability under the condition that .
Recall that we have chosen . Let be the stopping time
In words, is the first time that the particle leaves . Obviously, if , then . The following lemma shows that the particle eventually hits .
Lemma. For all , .
Sketch of proof: By irreducibility, there exists and such that for all . By strong Markov property, . If we sum this over , it is finite. We finish by Borel-Cantelli lemma.
Now, consider the expectation
as a function of the starting position . By the lemma, and are well-defined. Also, it is clear that for all .
Proposition. The function defined above is harmonic on .
Proof: Let . Then . We condition on the first step:
By Markov property,
Hence we get
Hence, we have proved
Theorem. The solution of the Dirichlet problem exists and can be expressed as
A consequence of this result is that we may estimate the solution by Markov chain simulations.
Finally, note that we may write
Comparing this with the formula , we see that is nothing but the matrix
Another way to see this is to write
Then the entries of are the probabilities that first hits a point in at exactly time . They are also called harmonic measures.
Analogus results hold for the classical Dirichlet problem on bounded domains. The harmonic measures become the hitting distributions of Brownian motion.