Voting and Anti-Voting

While at NZIMA, I listened to Dominic Welsh's talks on Markov chains. It was a general talk, with a large chunk devoted to rapid mixing and applications. At some point he brought up the voter and anti-voter model, problems that I heard about a long time ago in the distant past, and that raised some questions in my mind.

The voter model can be expressed as follows. We have an undirected graph G, where each vertex has a label. For convenience, let's assume the labels are in {0,1}, although larger alphabets are possible. At each time step, a vertex x is chosen uniformly at random, and x chooses a neighbor y uniformly at random. Then x changes its label to match y's label. This is a Markov chain with absorbing states with all vertices having the same label. It's natural to ask things like what is the probability that you end up in the all 0/all 1 state from a given configuration.

If the graph is d-regular, and you start in a state with k 0's and n-k 1's, a simple argument gives that the probability of eventually being absorbed into the all 0 case is k/n. (Exercise Left To Reader.) Things seem to get more complicated for more general graphs. Here are some interesting questions that come to mind. Note: I don't know which are open and which aren't...

1. Given a graph G and a starting configuration of labels, is there a polynomial time algorithm for computing the probability of being absorbed into the all 0 state? Or could a hardness result be proved? [My guess is there's a hardness result in there somewhere.]
   
2. Given a star graph (one node in the center, connected to n-1 other vertices) and a starting configuration, what is the probability of being absorbed into the all 0 state (preferably in some natural closed form)? In particular, if you start with a 1 in the middle and a 0 everywhere else, what is this probability as a function of n? Notice that by symmetry here one can easily compute these values in polynomial time; the question is whether there are pleasant equations. [On some reflection, it's clear there will be nice equations; this is almost a birth-death chain with an added "phase" needed to track the center vertex. Exercise left to reader...]
   
3. Similar questions to 1/2, but ask about the expected time/distribution of time until absorption.

Perhaps more interesting is the anti-voter model, which works just like the voter model, except that x changes its label to disagree with y's label. (Here the {0,1} alphabet is the most sensible.) Now we do not have absorbing states; we have a stationary distribution. But again one can ask similar questions:

1. Given a graph G and a configuration of labels, is there a polynomial time algorithm for compute the stationary probability for that state?
2. Are there natural families of graphs for which the stationary distribution for the anti-voting model has an easily expressible form? [d-regularity no longer seems to be enough...]
   

Obviously, one can argue about the importance of these questions, but I would just take the point of view that such easily expressible and seemingly natural questions about basic Markov chains are always interesting in their own right.