Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2014-15 > Coalescing Random Walks and Models of Voting on Graphs
How to contact us


LSE 10 logo master_6

Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE


Enquiries: dom.events@lse.ac.uk 


Follow us online



Coalescing Random Walks and Models of Voting on Graphs

Wednesday 4 February 2015
Colin Cooper 

4pm - 5pm, OLD 1.27, Old Building, Houghton Street 


A simple model of voting on connected graphs is as follows:

The voting proceeds in rounds. Initially each vertex has a distinct opinion. In each round each vertex contacts a randomly chosen neighbour and adopts their opinion. We call this model single-sample voting. The quantities of interest are the time for voting to complete, and the probability a particular opinion wins. Examples include:

Single-sample voting. The relationship between single-sample voting and coalescing random walks. These processes are dual and we can use random walks to analyze the performance of voting. Using this, we give an upper bound for the expected time for voting to complete on general connected graphs.

Two-party voting. In two-party voting, each vertex initially holds one of two opinions (e.g. 0 or 1). We discuss the speed-up in two-party voting when the opinion of one or more neighbour is sampled at each step. We give results for two-party voting on regular expanders when we sample two or more opinions. Compared to single-sample voting, this process is more consistent (democratic) and finishes much quicker.

Colin Cooper