Suppose you have a finite, planar Graph $G = (V,E)$ and a function $f_0:V \rightarrow \mathbb{Q}$.
Now you define the function $f_{i \in \mathbb{N}}$ like this:
$$f_i(v) := \frac{f_{i-1}(v) + \sum_{(v,w) \in E} f_{i-1}(w)}{1 + \text{number of vertices that are adjacent to } v}$$
In words: In each step, you go through each vertex and build the average of all vertices that are adjacent and the vertex itself and you assign this value to the vertex.
Examples
Example 1
You have two vertices that are connected:
Step 0: 14 - 42 Step 1: 28 - 28
Ready, it converged in a finite number of steps
Example 2
You have 10 vertices that are always only connected to the vertex before:
- Step 0: [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0]
- Step 1: [1.5, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 9.5]
- Step 2: [1.75, 2.1666666666666665, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 8.833333333333334, 9.25]
- Step 3: [1.9583333333333333, 2.3055555555555554, 3.0555555555555554, 4.0, 5.0, 6.0, 7.0, 7.9444444444444455, 8.694444444444445, 9.041666666666668]
- Step 4: [2.131944444444444, 2.4398148148148144, 3.1203703703703702, 4.018518518518518, 5.0, 6.0, 6.981481481481482, 7.879629629629631, 8.560185185185185, 8.868055555555557]
(I let this run with a python script. According to this, it converges after 861 steps. But I guess it only converges because of finite precision)
Example 3
I wanted to show you a triangle, but I've just realized that any complete graph will converge in only one step.
Example 4
The numbers get really ugly now. I am not even sure if this one converges at all. Before I wrote this example, I thought that all vertices would converge to $$\frac{\sum_{v \in V} f_0(v)}{|V|}$$, but now I'm not even sure if this is correct.
Example 5
Now I am sure that the value of the vertices doesn't always converge to the average as the sum of all vertices should not change in that case.
Question
If you have any Graph like I described above, can you determine an upper bound as a function of $n = |V|$ how fast the Graph will converge? Does it always converge? If not, can you give a counterexample?
Let $A$ be the adjacency matrix of your graph and let $D$ be the diagonal matrix of the same order with $D_{i,i}$ equal to 1 plus the degree of the $i$-vertex. Then your update rule is to replace $f$ by $D^{-1}(I+A)f$.
Note that $D^{-1}(I+A)$ is row stochastic and nonnegative and so describes a Markov chain on the vertices of the graph. If your graph is connected and all entries of $f$ are non-negative, it follows that $(D^{-1}(I+A))^nf)$ will converge to a limit, which will be an eigenvector for $D^{-1}(I+A)$, associated to the largest eigenvalue.
These are all standard facts, and will be treated in many introductory books on Markov chains. (They are also consequences of the Perron-Frobenius theory, in linear algebra.)
Edit: I'm using convergence above in the usual sense, but now I see this is not what you asked for. My mistake, but consider the following.
Set $M=D^{-1}(A+I)$ and let $x$ be the all-ones vector. Then $Mx=x$. Assume $M^{k+1}f=M^kf$. Then $M^kf$ is an eigenvector for $M$ with eigenvalue 1. From the theory referred to above, it follows that $M^kf=cx$ for some $c$. Hence $M^k(f-cx)=0$.
Suppose $E$ is the non-negative diagonal matrix such that $E^2=D$. Then $$ M = D^{-1}(A+I) = E^{-1} (E^{-1}(A+I)E^{-1}) E. $$ Thus $M$ is similar to a symmetric matrix, therefore it is diagonalizable, and therefore if $M^k(f-cx)=0$, then $M(f-cx)=0$. (So $Mf=cMx =cx$ and $M^2f=cMx=cx=Mf$. Hence $M^2f=Mf$ and we have shown that if $M^{k+1}f=M^kf$, then $k=1$.)
If $M(f-cx)=0$, then $D^{-1}(A+I)(f-cx)=0$. So choose a vector $y$ such that its entries sum to zero and $(A+I)y=0$. Then $D^{-1}(A+I)(ax+y) = ax$ (for any $a$) and $M^2(ax+y)=M(ax+y)$.
As an example, take the path on five vertices with $y=(1,-1,0,1,-1)$ and $a=1$, giving $f=(2,0,1,2,0)$.