4
$\begingroup$

A harmonic function on a graph is a function on its vertices such that the value at every vertex is the average of the values at its neighbors.

Consider the following method for approximating a harmonic function on a graph, given some initial values on each vertex: at each step, pick a random vertex, and replace its value by the average value of its neighbors.

Does this dynamical system have a name? Perhaps something like "Voter Model"? I recall something like "Relaxation" but an internet search gave irrelevant results. Are there texts that deal with this dynamical system? How much is known about it?

I'm interested specifically in the approximation of the value at time $t$ of an arbitrary vertex in the infinite grid $\mathbb{Z}^2$, given some initial conditions. This is a continuous-time random variable, and one can ask whether its expected value at time $t$ is continuous / differentiable / differentiable twice etc.

Improve this question
$\endgroup$
8
  • $\begingroup$ In the context of numerically solving PDEs e.g. the Laplace equation, this is indeed known as the "relaxation method" en.wikipedia.org/wiki/Relaxation_(iterative_method) $\endgroup$
    – j.c.
    Apr 19, 2018 at 10:11
  • $\begingroup$ @j.c. you're right and there is also relaxation in the context of Dijkstra's algorithm. $\endgroup$
    – co.sine
    Apr 19, 2018 at 12:03
  • $\begingroup$ Actually, I wasn't quite right. The relaxation methods generally tend to relax every vertex at once. If you considered that problem instead, you would be using a "Foward Time Centered Space" finite difference method for solving the heat equation on $\mathbb{R}^2$, see e.g. en.wikipedia.org/wiki/FTCS_scheme or other introductory sources on finite difference schemes. $\endgroup$
    – j.c.
    Apr 19, 2018 at 13:10
  • $\begingroup$ What are "steps" if time $t$ is continuous, and how do you "pick a random vertex" in "the infinite grid $\mathbb Z^2$? $\endgroup$
    – R W
    Apr 19, 2018 at 13:21
  • $\begingroup$ @RW I suspect that they mean something like the Poisson clock setup in their previous question(s), e.g. mathoverflow.net/questions/266914/… $\endgroup$
    – j.c.
    Apr 19, 2018 at 14:10

1 Answer 1

Reset to default
1
$\begingroup$

I do not think that one can expect any general results in the case of ininite graphs. Take just the integer line $\mathbb Z$, for which all bounded harmonic functions are constants, so that the limit of your process should be a constant. Thus, you have a linear functional on the space of bounded function on $\mathbb Z$. This functional is obviously positive and preserves constants, so that in other words it is a Banach mean (or a finitely additive probability measure) on $\mathbb Z$, which is a highly non-constructive object.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Now that I look over the question I'd rather talk about the differentiability of the variance of the value at some vertex (because if for example we take every to be distributed as $\text{Bernoulli}(p)$ then $E[v(t)]$ will always be $p$). And in general, whether any non constant probabilistic property of the dynamics is differentiable. Isn't there even hope to prove continuity / differentiability here? $\endgroup$
    – co.sine
    Apr 20, 2018 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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