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

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

Coalescing Random Walks and Models of Voting on Graphs

Wednesday 4 February 2015
Colin Cooper 

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


Abstract

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.

Share:Facebook|Twitter|LinkedIn|
Colin Cooper