Explicit Sufficient Invariants for an Interacting Particle System

We introduce a new class of interacting particle systems on a graph $G$. Suppose there are initially $N_i (0)$ particles at each vertex $i$ of $G$, and that the particles interact to form a Markov chain: at each instant two particles are chosen at random, and if these are at {\em adjacent} vertices of $G$, one particle jumps to the other particle's vertex, each with probability 1/2. The process enters a death state after a finite time when all the particles are in some {\em independent} subset of the vertices of $G$, i.e., a set of vertices with no edge between any two of them. The problem is to find the distribution of the death state $\eta _i= N_i ( \infty )$ as a function of the numbers $N_i (0)$. We are able to obtain, for some special graphs, the {\em limiting} distribution of each $N_i$ if the total number of particles $N \to \infty$ in such a way that the fraction $N_i (0) /N = \xi_i$ at each vertex is held fixed as $N \to \infty$. In particular we can obtain the limit law for the graph $S_2: \cdot$---$\cdot$---$\cdot$ having 3 vertices and 2 edges. This talk is from a joint paper with Colin Mallows (AT\&T Laboratories, Florham Park) and Larry~Shepp (Rutgers University) ({\em J.~Appl.~Prob.} (1998) Vol. 35, p.~633-641).