# discrete version of Laplacian

Suppose $P(x,y)$ gives transition probabilities of a random walk. I've seen $Pf=f$ being called the discrete version of Laplace's equation. In what sense are they analogous?

-

Some analogies between discrete and continuous Laplacians were discussed in MO:

http://mathoverflow.net/questions/33602/what-is-a-reasonable-finitary-analogue-of-the-statement-that-harmonic-functions-a/

If you search for "discrete harmonic" or "discrete Laplacian" there may be more there.

(added: the analogy is not as simple as the fact that the lattice Laplace operator converges to the continuous Laplacian as the spacing shrinks to zero. There is a rotational symmetry of the continuous Laplacian which is an essential part of the geometric theory. For the analogies to be meaningful, at least some of the geometry of the continuum story should be be visible in the lattice or graph Laplacians, and for this eigenvalue inequalities, Hodge theory, vector bundles, zeta functions and other constructs are considered for graphs, in addition to the more easily perceived analogies with harmonic theory and Brownian motion.)

-

Here is a low-brow answer. If you accept that the discrete version of the second derivative of a function $f$ is $f(x+1) - 2f(x) + f(x-1)$, then the discrete Laplacian, say in two dimensions, is $\Delta f(x, y) = \frac{f(x+1, y) + f(x-1, y) + f(x,y+1) + f(x,y-1)}{4} - f(x,y)$. But the first term is just the transition probabilities of a random walk on $\mathbb{Z}^2$ where one moves to each of the four horizontally or vertically adjacent neighbors with equal probability. A similar statement is true in $n$ dimensions.

More generally one can define a discrete Laplacian on any graph which mimics the usual Laplacian. In fact there is an entire textbook by Doyle and Snell dedicated to working out potential theory on graphs.

-

The infinitesimal generator for Brownian motion in $\mathbb R^n$ (and, in general, in a Riemannian manifold) is $\tfrac12\Delta$. Your matrix $P$ plays exactly the same rôle in the discrete version.

As for the equation: the equation $\tfrac12\Delta f=0$ is, in the case of Brownian motion in $\mathbb R^n$, the equation for stationary states. Your equation is the same thing in the discrete version.

-