Bounds on the voting time in terms of the conductance

In the voting model each node has an opinion and in every time step each node adopts the opinion of a random neighbour. We show that the consensus time, i.e., expected time required until one opinion prevails, is bounded by O(n / phi) for regular graphs, where phi is the conductance of the graph. This bound is tight for regular expanders. For non-regular graphs we obtain a bound of O( (davg / dmin)(n / phi) ), where davg is the average degree and dmin is the minimum degree. Additionally, we consider a generalization of the model where every opinion has a popularity. Here, every node chooses a neighbour and adopts its opinion with some probability which depends on the popularity of the neighbour's opinion. We show that the expected consensus time for a regular graph having initially two distinct opinions is bounded by O( logn / phi).