Potential theory on finite sets

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.