Stationary distributions and convergence rates for the edge flipping process

Abstract

The edge flipping process is a random walk over the set of all possible color patterns of a graph. Each time the two endpoints of the selected edge are colored the same color. This color is blue with probability p and red with probability 1 − p. In the vertex flipping process, we choose vertices instead of edges. All the neighbors of the selected vertex and itself are colored in the same color. The eigenvalues of this random walk are indexed by all subsets of the vertices of the graph. Thanks to this indexing, we have obtained information about eigenvalues and, as a result, converge rates in the graph classes we are working on. In some simple graph classes such as complete bipartite graph and caterpillar tree, we have obtained results related to where this random walk converges after a while. In general, we are looking for answers to the two questions: where we converge and how fast it occurs.