Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.