Edge flipping in graphs

AbstractIn this paper we investigate certain random processes on graphs which are related to the so-called Tsetlin library random walk as well as to some variants of a classical voter model. A specific example of what we study is the following. Suppose we begin with some finite graph G in which each vertex of G is initially arbitrarily colored red or blue. At each step in our process, we select a random edge of G and (re-)color both its endpoints blue with probability p, or red with probability q=1−p. This “edge flipping” process generates a random walk on the set of all possible color patterns on G. We show that the eigenvalues for this random walk can be naturally indexed by subsets of the vertices of G. For example, in the uniform case (where p=12), for each subset T of vertices of G there is an eigenvalue λT (with multiplicity 1) which is equal to the number of edges in the subgraph induced by T divided by the number of edges of G.We also carry out a fairly detailed analysis of the stationary distribution of this process for several simple classes graphs, such as paths and cycles. Even for these graphs, the asymptotic behavior can be rather complex