9
$\begingroup$

Consider the torus graph, or the toroidal grid, which looks like

enter image description here

(The graph's vertices are the bold dots).

I will discuss only square torus graphs, where there is an equal number of vertices in a "vertical" circle and a "horizontal" circle. Such a graph can be represented by a cyclic square matrix, where every entry is a vertex.

Take every vertex and assign it a random value - 0 or 1 with equal probability. The matrix then looks like

enter image description here

Similar to other questions I asked, start the following process: at each step, pick a random vertex, and update its value to the value of most of its neighbors (in case of draw the value remains unchanged). It is known, that the process always converges, i.e. each vertex changes value only a finite amount of times.

Take a look:

http://www.nissan-music.co.il/Download/Torus/TorusDynamics.gif

Another example, slower one:

http://www.nissan-music.co.il/Download/Torus/TorusDynamicsSlow.gif

I found that the distibution of the final amount of 1's, as well as the distribution of the ratio between the final amount of 1's and the initial amount of 1's, both look like normal, when the torus dimensions are constant, and each iteration is a new random choice of initial conditions.

Final amount of 1's (matrix size is 30x30):

enter image description here

Ratio distribution:

enter image description here

I'm looking for a way to prove that these distributions converge to normal when the torus size (which is the size of the matrix) goes to infinity, and if they really do, find how the standard deviation depends on the torus size.

Thank you!

Edit: A possible direction could be Stein's method, although I don't know how to implement it here.

Edit 2: Let $X$ be the final proportion of 1's. $E[X] = \frac{1}{2}$, because if $Y$ is the final proportion of 0's, then $E[X] = E[Y]$ and $X + Y = 1$. If you manage to calculate $Var[X]$, this will be a good start!

Edit 3: Perhaps a variant of the central limit theorem for dependent variables is needed.

$\endgroup$
  • 3
    $\begingroup$ This feels to me like a difficult question (the closest thing I have ever heard of being the abelian sandpile model). The typical ending position has some randomness but is much more organized than a purely random position, and should be fun to study at least experimentally. $\endgroup$ – Benoît Kloeckner May 26 '17 at 15:39
  • 1
    $\begingroup$ Shouldn't the ratio between the final amount of 1s and the initial amount of 1s be close to 1 on average, not close to $1/2$, as you have graphed? $\endgroup$ – Will Sawin May 26 '17 at 16:20
  • 1
    $\begingroup$ Something would have to happen at the ultra rare extremes of 0 and 2. You might want to change variables to take that into account. $\endgroup$ – AHusain May 26 '17 at 18:14
  • 3
    $\begingroup$ Just a remark: at least in topological graph theory, rather than calling this the "torus graph", one would refer to this as the "toroidal grid". $\endgroup$ – Gelasio Salazar May 26 '17 at 21:24
  • 1
    $\begingroup$ Just a pointer: I believe this model is called "majority dynamics" in various places, e.g., papers like this: arxiv.org/abs/1307.4035. (Maybe it is slightly different because you are not updating all neighbors at once but I think it should still get you looking at the right references.) $\endgroup$ – Sam Hopkins Jun 10 '17 at 14:14

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.