Random versus deterministic: random walks and rotor walks

The goal of this project is to work in an interdisciplinary field at the confluent of different branches of Mathematics and to obtain synergy effects. The plan is to deepen the understanding of the interplay between properties of graphs and the behavior of two processes (a random process and its deterministic counterpart) on these graphs. The processes we consider are random walks and rotor walks (called also rotor-router walks), which are derandomized versions of random walks. In a variety of respects, the rotor-router walk captures the mean behavior of the random walk. On the other hand, these processes can also have very striking differences. The mathematics involved in this research is a mixture between probability theory, structure theory (algebra, geometry), graph theory, combinatorics, and has also connections with statistical physics. An outline of the most important problems we want to study is given below. Branching rotor-router walks (BRRW). This is a new process we introduce in this research, and it is a half-derandomized version of a branching random walk. The latter is a system of particles which produces offsprings according to some given distribution, and then the offsprings move randomly on a graph. In the proposed model BRRW, after producing offsprings, particles perform rotor-router walks, instead of random walks. For a BRRW, we want to elaborate criteria for local and global survival of the population. Moreover, we also want to study how the state space on which particles move and the initial configuration of rotors influence the behavior of the process. In addition, we want to develop the basic theory of stochastic abelian networks (in parallel to the deterministic ones introduced by Bond and Levine). The proposed model BRRW is an example of a stochastic abelian network. Internal aggregation models on fractal graphs. We consider the following cluster growth models: internal diffusion limited aggregation (IDLA) and its deterministic counterpart rotor- router aggregation. In IDLA particles move randomly on a graph until reaching an unoccupied site where they stop. In rotor-router aggregation particles perform rotor-router walks instead of random walks, until visiting a new site, where they stop. One is interested in how the set of occupied sites behaves (for example, if it has a limiting shape, when properly rescaled). Within the proposed research, we want to study these cluster growth models on fractal graphs, where according to simulations, they exhibit an atypical behavior which has not been observed on other state spaces.

The current project with the title Random versus deterministic: random walks and rotor walks deals with the interplay between the behavior of random walks and of rotor walks on infinite state spaces (such as graphs or groups). A rotor walk on a graph is a deterministic process, in which each vertex is endowed with a rotor that points to one of the neighbors. A particle located at some vertex first rotates the rotor in a prescribed order, and then it is routed to the neighbor the rotor is now pointing at. A random walk on a graph is a random process, in which a particle initially sitting at some vertex, moves randomly in the graph, according to some given probability distribution. Even though we are considering one deterministic process and one random process, it turns out that these two processes share many properties, and this is the essence of the current project. As proposed, I have used probabilistic methods in order to prove results about rotor walks, and vice versa, combinatorial methods were used in order to prove properties of random walks. The connection between the two processes became more evident, and the dependence on the infinite spaces the processes evolve on is another important feature investigated in this project.A first relevant problem, I have been working on at Cornell University, was to introduce a new process on the integer line, which I call p-rotor walks. Such walks depend on a parameter p, and they interpolate between random walks and rotor walks. For the processes under consideration we prove a scaling limit (invariance principle) and other properties such as: law of large numbers, recurrence/transience. For specific values of p we recover known results about random walks and classical rotor-router walks. This model allows several generalizations, and it is very challenging to study it on higher dimensional integer lattices.Another important project were we have achieved interesting results, in collaboration with Joe Chen (Colgate University), Wilfried Huss (Graz University of Technology) and Alexander Teplyaev (University of Connecticut), is the investigation of internal aggregation models (such as internal diffusion limited aggregation or IDLA and divisible sandpile) on fractals. IDLA is an random cluster growth model on a graph in which particles are launched from a fixed site, and evolve randomly until finding sites unvisited previously, where they stop. In this manner, a random cluster (called IDLA cluster) of occupied sites is formed. In the divisible sandpile model on a graph, a distribution of mass is moving around; at each timestep one vertex distributes mass to all its neighbors and keeps only a fixed amount of mass for itself. This process never terminates and one looks at its limit. The set of sites where the limit mass distribution is nonzero is called divisible sandpile cluster. For both IDLA and divisible sandpile on Sierpinski gasket graphs, we prove limit shape theorems, that is, we describe explicitly the shape of the IDLA cluster and of the divisible sandpile cluster. The limit shape is the same for both models, even if the divisible sandpile is purely deterministic and IDLA is a random process. It is natural to continue the investigation of these growth models on other fractal graphs, and to prove shape theorems and to understand the fluctuations on the boundary of the cluster. This is currently ongoing work.