Meeting Time: January 27, 2011, 2:00-2:50pm, Oldfather 207
Abstract:
We study a certain random process on a graph \(G\) which is a variation of a classical voter model and is also a special case of the so-called Tsetlin library random walk. Initially each vertex of \(G\) is colored either blue or red. At each step an edge is chosen at random and both endpoints change their colors to blue with probability \(p\) and to red otherwise. This edge-flipping process corresponds to a random walk on the associated state graph in which each coloring configuration is a node. We show that the eigenvalues for the random walk on the state graph can be indexed by subsets of the vertex set of \(G\). For example, for the uniform case of \(p=1/2\), for each subset \(T\) of the vertex set \(V\) of \(G\), the eigenvalue \(\lambda_T\) (with multiplicity \(1\)) is the ratio of the number of edges in the induced subgraph of \(T\) divided by the total number of edges in \(G\). We analyze the stationary distribution of the state graph of colorings of \(G\) for several special families of graphs, such as paths, cycles and trees. We also mention related problems in connection with memoryless games.