The Rotor-Router Model

What is it? 

The Rotor-Router Model, created by Jim Propp, is a four sided device that is meant to represent that of random walk. A Random Walk  for a particular particle (or object) is a path which begins at an initial point (lets just say the origin) and that object chooses its next path/direction with equal probability, no mater the previous movement.

Most of us, including myself, practices random walk    
at least 3 times a week. GOOD JOB TEAM!

So... What about it?

We can prove that in a finite region, Zd, the exit time of simple random walk converges to a Euclidean ball in Rd. 

With a finite region A in Zd, let A' be the region (that is random) by starting a random walk at the origin. The random walk will stop when it first exits the finite region A. 

The internal diffusion limited aggregation (DLA) is the growth model that starts from the origin. The region of An, if you were to rescale to n^(1/d), converges to a Euclidean ball in Rd with a probability of 1 as n goes to infinity. 

When an object is placed in the center after going through its random walk and rotation, the particle eventually leaves the region A, after the clockwise rotation of 90 degrees and a new step in a new direction. This serves as a simulation of first-order properties of random walk.  

When the object, after random walk, reaches a point that is not in A, that point is added next to the region and eventually, there is a sequence of regions that is created called An. 

For example: If all the rotors are initially pointing north, 

the sequence will begin A1 = {(0,0)}, A2 = {(0,0),(1,0)}, A3 = {(0,0),(1,0),(0,-1)}, etc. 

The converging Euclidean Ball 

Theorem: 

We want to prove the shape for the rotor-router model that is similar to a model with internal DLA properties. The symmetric difference of sets R and S is denoted by sym(R,S).  For a region A in  Zd, the union of closed cubes in Rd, that is centered at the points of A, can be written as A*, We write L for d-dimensional Lebesgue measure. 

(Definition: Lebesgue measure, in measure theory, is the standard way of assigning a measure to subsets of n-dimesional Euclidean space. For n = 1,2, or 3, it coincides with the standard measure of length, area, or volume.) 

Let (A_n)_{n > 1}  be rotor-router aggregation in Z^d, starting from any initial configuration of rotors. Then as n tends to infinity L( n^-1/d sym⁽A_n*, B) ) converges to zero, where B is the ball of unit volume centered at the origin in R^d.

Conclusion:

All-in-all, the Rotor-Router Model is a device made to demonstrate a random walk of an object along a graph. There are theories that try to solve how and in which direction this object or particle moves, but theres not much else to it. But it is very interesting to see how in-fact this particle moves along the graph. There is a cool website to actually see how this is represented 

here:

 http://www.cs.uml.edu/~jpropp/rotor-router-model/

References:
http://people.duke.edu/~rnau/411rand_files/image008.jpg
http://research.microsoft.com/en-us/um/people/peres/router/router.html
https://en.wikipedia.org/wiki/Lebesgue_measure
 http://www.cs.uml.edu/~jpropp/rotor-router-model/