Give **Z**^{n} the "normal" grid-like graph structure (i.e. every point (a_{1},...,a_{n}) is adjacent to the 2n points (a_{1},...,a_{i±1},...,a_{n})). When n=2, we just get the square grid found on graph paper.

Now define a harmonic function on a graph to be a function f such that f(x) is the average value of f on the neighbours of x in the graph. For instance, f(x,y)=2x-3y is such a function (for n=2).

One immediate property of such a function is that it cannot have a strict local maximum, i.e. a point x such that f(x) > f(y) for all neighbours y of x. This is because f(x) is the average value of f on x's neighbours, and therefore cannot be larger than all of them.

It seems plausible, in light of theorems like Liouville's theorem from complex analysis, that no nonconstant bounded harmonic function can exist in **Z**^{n}. However, this is somewhat difficult to prove. It is also true that no nonconstant positive harmonic function exists on **Z**^{n}; this requires some serious machinery from mathematical analysis to prove.

#### Proof:

Let f be a harmonic function on

**Z**^{n}. Consider a

simple random walk X

_{0}, X

_{1}, ... on

**Z**^{n}, starting from 0 (this simply means that X

_{0}=0, and X

_{n+1} is one of X

_{n}'s neighbours, picked at

random). Then the

expected value of f(X

_{1}) is exactly f(X

_{0}), and a little thought shows that the expected value of f(X

_{t}) is always f(X

_{0}), for any constant t.

We'll show that f is constant on 2**Z**^{n} (i.e. only points with all coordinates even); it will immediately follow that f is constant, since a harmonic function cannot have a local maximum (or minimum). To prove this, it is sufficient to prove that f(x)=f(x+2*k*e_{i}) for all x, k and all standard basis vectors e_{i} (e_{i} is (0,...,0,1,0,...,0), with the 1 in the i'th place).

So start a simple random walk from x, and define another (dependent) simple random walk starting from x+2*k*e_{i} by reflecting the random walk in the plane through x+k*e_{i} which separates x and x+2*k*e_{i}. Then this X'_{t} is another simple random walk. We know from the preceding remarks that f(X_{0}) is the expected value of f(X_{t}), and f(x+2*k*e_{i}) is the expected value of f(X'_{t}).

The projection of X_{t} on the e_{i} axis is a random walk, the projection of X'_{t} on that axis is its mirror image, and it is easy to see that X_{t} must meet X'_{t} almost surely (this is why we require that x and x+2*k*e_{i} be an even distance apart). Now define X''_{t} to be X'_{t} until it meets X_{t}, and then X_{t}. Then X''_{t} is also a simple random walk, and f(x+2*k*e_{i}) is again the expected value of f(X''_{t}).

Now suppose f is bounded. Pick some positive ε. For large enough t, the probability that X'_{t} hasn't yet hit X_{t} is smaller than ε. So for such a t,

f(X_{t})-f(X''_{t}) < ε*(f(X_{t})-f(X'_{t})) + 0,

since if X

_{t} has already hit X'

_{t}, then X''

_{t}=X

_{t}, and the other case happens with probability <ε. So |f(X

_{t})-f(X''

_{t})| < 2*ε*

supremum(f), which is arbitrarily small. But |f(x)-f(x+2*k*e

_{i})| is bounded by the average value of |f(X

_{t})-f(X''

_{t})|, so it too is arbitrarily small. Hence it must be 0.

**QED**

#### Proving the positive case

To prove that f is constant when we are only given that it is

positive (i.e. bounded on one side), we can apply this reasoning regarding the values of f along a simple random walk: f(X

_{t}) turns out to be a

martingale, which we need to show must converge. But the limit cannot depend on the initial location, and by averaging this limit must be f itself - hence f is constant.