Potential theory on finite sets

Posted on 09/12/2010 by leonardwong

Motivation

Consider the following Dirichlet problem on the unit square S = [0, 1] \times [0, 1]:

\Delta u = 0 on [0, 1] \times [0, 1]

u|_{\partial S} = g

where g is a given function on the boundary.

To get an approximate solution, we may replace the unit square by a grid. Let N be large and set h = 1 / N. The grid points are

(x_i, y_j) = (ih, jh), i, j = 0, 1, ..., N.

Next, we replace the Laplacian by a finite difference operator:

\Delta u(x_i, y_j) \sim \frac{1}{h^2}[u(x_{i-1}, y_j) + u(x_{i+1}, y_j) + u(x_i, y_{j-1}) + u(x_i, y_{j+1}) - 4u(x_i, y_j)]

And the Dirichlet problem is replaced by the following system of linear equations:

u(x_i, y_j) = \frac{1}{4}[u(x_{i-1}, y_j) + u(x_{i+1}, y_j) + u(x_i, y_{j-1}) + u(x_i, y_{j+1})] for i, j = 1, ..., N -1.

u|_{\partial S} = g

As N \rightarrow \infty, we may expect that the solution tends to the solution of the original problem.

Now let u be any function on the grid. The operator

[(P - I)u]_{ij} = \frac{1}{4}[u_{i-1, j} + u_{i+1, j} + u_{i, j-1} + u_{i, j+1}] - u_{ij}

is called the discrete Laplacian on the grid.

Note that the averaging operator P also arises as the transition function of the simple random walk on the grid. Suppose \{X_n\} moves around the grid randomly and stops when it hits the boundary. If X_n is at an interior grid point (x_i, y_j), then in the next step it jumps to one of the neighboring points with equal probability. Then

{\mathbb{E}}[u(X_1) | X_0 = (x_i, y_j)] = (Pu)_{ij}

We shall see that this is no coincidence. In fact, we shall interpret the solution in terms of the random walk.

General case

Now we generalize the above situation. Let X be a finite set, called the state space.

Definition. A transition function on X is a matrix P = (p(x, y))_{x, y \in X} such that p(x, y) \geq 0 for all x, y and \sum_{y \in X} p(x, y) = 1 for all x.

We may also say that P is a stochastic matrix, but we emphasize that it is an operator of functions (column vectors) on X:

If f: X \rightarrow {\mathbb{R}} then Pu(x) = \sum_{y \in X} p(x, y)u(y).

(Note: It is also an operator of measures (row vectors) on X:

If \mu: X \rightarrow {\mathbb{R}} then \mu P(y) = \sum_{x \in X} \mu(x) p(x, y).

But we shall not need this here.)

Let I be the identity operator (or matrix). We think of P - I as the discrete Laplacian. This motivates:

Definition. Let u: X \rightarrow {\mathbb{R}} and A \subset X. We say that u is superharmonic on A if Pu(x) \leq u(x) for all x \in A. If equality holds everywhere on A, we say that u is harmonic on A.

Now we may formulate the Dirichlet problem. Let \emptyset \neq D \subset X and D \neq X. Let g be a given function on X \setminus D. The Dirichlet problem is to find u: X \rightarrow {\mathbb{R}} such that

Pu(x) = u(x) for x \in D

u(x) = g(x) for x \in X \setminus D

The first condition says that u is harmonic on D.

We shall formulate conditions such that the problem can be uniquely solved. To see that such conditions are necessary, suppose that X = \{a, b\}, D = \{a\} and P = I. Then any function on X is harmonic and we are free to choose u(a). The problem here is that P does not connect a to b.

Definition. We say that the pair (X, P) is irreducible if for any x, y \in X, there exists a path x_0 = x, x_1, ..., x_n = y such that p(x_i, x_{i+1}) > 0 for all i.

Proposition (uniqueness). Assume that (X, P) is irreducible. Then the solution of the Dirichlet problem is unique.

Proof: Suppose u_1 and u_2 are solutions to the Dirichlet problem. We show that u = u_1 - u_2 = 0. Suppose that u attains its maximum at x \in D. Then from

u(x) = \sum_{y \in X} p(x, y)u(y)

we see that u(y) = u(x) whenever p(x, y) > 0. If one of such y lies in X \setminus D, then u(x) = 0 and we are done. If not, we iterate until we hit a point in X \setminus D. Similarly, the minimum is also 0. Hence u = 0. \blacksquare

(Note: The method of proof is the discrete analogue of the classical maximum principle.)

From now on we assume that (X, P) is irreducible. How about existence?

In matrix form, the Dirichlet problem can be written as

\begin{pmatrix} Q & R \\ 0 & I \end{pmatrix} \begin{pmatrix} u|_D \\ u|_{X \setminus D} \end{pmatrix} = \begin{pmatrix} u|_D \\ g \end{pmatrix}

where Q = P|_{D \times D} and R = P|_{D \times (X \setminus D)}. Hence, if the matrix I - Q is invertible, then

u|_D = (I - Q)^{-1}Rg.

(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 P.

Let \Omega be the space of all paths \omega from {\mathbb{N}} to X. For each n, let X_n be the n-th projection map, i.e.

X_n(\omega) = \omega(n).

Finally, let {\mathcal{F}} be the sigma-field on \Omega generated by sets of the form \{\omega: X_n(\omega) \in B\}, where B \subset X. We need the following existence theorem.

Theorem (Kolmogorov). For any probability measure \mu on X, there exists a unique probability measure {\mathbb{P}}_{\mu} on (\Omega, {\mathcal{F}}) such that for x_0, x_1, ..., x_n \in X,

{\mathbb{P}}_{\mu}(X_0 = x_0, X_1 = x_1, ..., X_n = x_n) = \mu(x_0) p(x_0, x_1) ... p(x_{n-1}, x_n).

For \mu = \epsilon_x, we write {\mathbb{P}}_{\epsilon_x} = {\mathbb{P}}_x.

The stochastic process (\{X_n\}_{n \geq 0}, \{{\mathbb{P}}_x\}_{x \in X}) is called the Markov chain on X with transition function P. We think of X_n as the position of a random particle at time n, and {\mathbb{P}}_x as the probability under the condition that X_0 = x.

Recall that we have chosen D \subset X. Let T \geq 0 be the stopping time

T = \inf\{n \geq 0: X_n \in X \setminus D\}.

In words, T is the first time that the particle leaves D. Obviously, if X_0(\omega) \in X \setminus D, then T(\omega) = 0. The following lemma shows that the particle eventually hits X \setminus D.

Lemma. For all x \in X, {\mathbb{P}}_x(T < \infty) = 1\}.

Sketch of proof: By irreducibility, there exists n_0 and \epsilon > 0 such that {\mathbb{P}}_x(T > n_0) \leq 1 - \epsilon for all x \in D. By strong Markov property, {\mathbb{P}}_x(T > kn_0) \leq (1 - \epsilon)^k. If we sum this over k, it is finite. We finish by Borel-Cantelli lemma. \blacksquare

Now, consider the expectation

u(x) = {\mathbb{E}}_x[g(X_T)]

as a function of the starting position x. By the lemma, X_T and u are well-defined. Also, it is clear that u(x) = g(x) for all x \in X \setminus D.

Proposition. The function u(x) defined above is harmonic on D.

Proof: Let x \in D. Then T \geq 1. We condition on the first step:

u(x) = {\mathbb{E}}_x[g(X_T)] = {\mathbb{E}}_x({\mathbb{E}}_x[g(X_T) | X_1]] = \sum_{x \in y} p(x, y) {\mathbb{E}}_x[g(X_T) | X_1 = y]

By Markov property,

{\mathbb{E}}_x[g(X_T) | X_1 = y] = {\mathbb{E}}_y[g(X_T)] = u(y).

Hence we get

u(x) = \sum_{y \in X} p(x, y) u(y) = Pu(x).

for x \in D. \blacksquare

Hence, we have proved

Theorem. The solution u of the Dirichlet problem exists and can be expressed as

u(x) = {\mathbb{E}}_x[g(X_T)].

A consequence of this result is that we may estimate the solution by Markov chain simulations.

Finally, note that we may write

{\mathbb{E}}_x[g(X_T)] = \sum_{y \in X \setminus D} {\mathbb{P}}_x(X_T = y) g(y).

Comparing this with the formula u|_D = (I - Q)^{-1}Rg, we see that (I - Q)^{-1}R is nothing but the matrix

({\mathbb{P}}_x(X_T = y))_{x \in D, y \in X \setminus D}.

Another way to see this is to write

(I - Q)^{-1}R = R + QR + Q^2R + ...

Then the entries of Q^nR are the probabilities that X_n first hits a point in X \setminus D at exactly time n. 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.

This entry was posted in Potential theory, Probability. Bookmark the permalink.

Leave a comment