## 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.

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