We study two random processes on an n-vertex graph inspired by the internal diffusion limited aggregation (IDLA) model. These processes can also be regarded as protocols for allocating jobs in a distributed network of servers. In both processes n particles start from an arbitrary but fixed origin. Each particle performs a simple random walk until it first encounters an unoccupied vertex, at which point the vertex becomes occupied and the random walk terminates. In one of the processes, called Sequential-IDLA, a single particle moves until settling and only then does the next particle start whereas in the second process, called Parallel-IDLA, all unsettled particles move simultaneously. The second process is akin to running the first in parallel. Our main goal is to analyze the so-called dispersion time of these processes, which is the maximum number of steps performed by any of the n particles. In order to compare the two processes, we develop a coupling which shows the dispersion time of the Parallel-IDLA stochastically dominates that of the Sequential-IDLA; however, the total number of steps performed by all particles has the same distribution in both processes. This coupling also gives us that dispersion time of Parallel-IDLA is bounded in expectation by dispersion time of the Sequential-IDLA up to a multiplicative log n factor. Moreover, we derive asymptotic upper and lower bound on the dispersion time for several graph classes, such as cliques, cycles, binary trees, d-dimensional grids, hypercubes and expanders. Most of our bounds are tight up to a multiplicative constant.
One model where interaction between particles prevents settling at a cite is a two-type particle system called Oil and Water'' where particles of opposing types displace each other @cite_8 . There have been some papers on models related to the Parking function of a graph where cars drive randomly around a graph searching for vacant spots @cite_14 @cite_15 . More commonly, however, interaction is directly between particles and not with the host graph such as predator prey coalescing models @cite_20 . The problem of uniformly distributing @math non-communicating memoryless particles across @math unoccupied sites is also considered from a game theoretic perspective @cite_6 .
@cite_14 @cite_8 @cite_6 @cite_15 @cite_20
2765153990 2187227140 2142723001 2545825365 2039765418
Place a car independently with probability @math at each site of a graph. Each initially vacant site is a parking spot that can fit one car. Cars simultaneously perform independent random walks, and when a car encounters an available parking spot, it parks there and the spot becomes unavailable. For a large class of transitive and unimodular graphs, we show that the root is almost surely visited infinitely many times when @math , and only finitely many times otherwise. We introduce a two-type internal DLA model which is an example of a non-unary abelian network. Starting withn " andn " particles at the origin, the particles diuse in Z according to the following rule: whenever some site x2 Z has at least 1 oil and at least 1 water particle present, it res by sending 1 oil particle and 1 water particle each to an independent random neighbor x 1. Firing continues until every site has at most one type of particles. We establish the correct order for several statistics of this model and identify the scaling limit under assumption of existence. Following Schelling (1960), coordination problems have mainly been considered in a context where agents can achieve a common goal (e.g., rendezvous) only by taking common actions. Dynamic versions of this problem have been studied by Crawford and Haller (1990), Ponssard (1994), and Kramarz (1996). This paper considers an alternative dynamic formulation in which the common goal (dispersion) can only be achieved by agents taking distinct actions. The goal of spatial dispersion has been studied in static models of habitat selection, location or congestion games, and network analysis. Our results show how this goal can be achieved gradually, by indistinguishable non-communicating agents, in a dynamic setting. Consider a uniform random rooted tree on vertices labelled by @math , with edges directed towards the root. We imagine that each node of the tree has space for a single car to park. A number @math of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path oriented towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider @math and let @math denote the event that all @math cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if @math , we have @math , whereas if @math we have @math . We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we are led to consider the following variant of the problem: take the tree to be the family tree of a Galton-Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson( @math ) number of cars arrive at each vertex. Let @math be the number of cars which visit the root of the tree. Then for @math , we have @math , whereas for @math , we have @math . This discontinuous phase transition turns out to be a generic phenomenon in settings with an arbitrary offspring distribution of mean at least 1 for the tree and arbitrary arrival distribution. We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make the analysis for random regular graphs. The cover time of a random walk on a random @math -regular graph was studied in [C. Cooper and A. Frieze, SIAM J. Discrete Math., 18 (2005), pp. 728-740], where it was shown with high probability (whp) that for @math the cover time is asymptotic to @math , where @math . In this paper we prove the following (whp) results, arising from the study of multiple random walks on a random regular graph @math . For @math independent walks on @math , the cover time @math is asymptotic to @math , where @math is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is @math . If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for @math walks to broadcast a single piece of information to each other is asymptotic to @math as @math . We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing or by annihilating each other. For example, the expected extinction time of @math explosive particles ( @math even) tends to @math as @math . The case of @math coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. The expected time for a unique opinion to emerge is the same as the expected time for all the particles to coalesce, which is asymptotic to @math . Combining results from the predator-prey and multiple random walk models allows us to compare expected detection times of all prey in the following scenarios: Both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, and the predators move randomly and the prey stays fixed. In all cases, with @math predators and @math prey the expected detection time is @math , where @math is the @math th harmonic number.