日時：4/11(木)10:00-11:30

Coalescing Random Walks and Voting on Graphs

Colin Cooper (Department of Informatics, King's College London)

The standard model of voting on connected graphs is as follows:
Initially each neighbour has a distinct opinion. The voting proceeds
in rounds. In each round each vertex contacts a randomly chosen
neighbour and adopts their opinion. We refer to this model as
single-sample voting. In voting, the quantities of interest are the
time for voting to complete, and the probability a particular opinion
wins.

The talk focuses on the following topics:

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.

Other models of voting. 
In the standard voting model, each vertex  checks the opinion of one
neighbour at each step. We consider models of voting where more than
one opinion is sampled at each step. The simplest such  model is
two-sample voting where each vertex randomly samples the opinions of
two neighbours at each step. For this model we discuss min-voting and
two-party voting.

Min-voting.
In min-voting,  each vertex initially has a distinct numeric opinion
between 1 and n  (the graph size). At each step each vertex randomly
samples the opinion of two neighbours, and adopts the minimum opinion.
This process completes in O(log n) expected time on certain classes
of expanders.

Two-party voting.
In two-party voting, each vertex initially holds one of two opinions
(e.g. 0 or 1). We are interested in the time taken for all vertices
to have the same opinion, and the probability that a given opinion
wins. We review the results for two-party voting in the standard
(single-sample) model of voting. We discuss the  performance  of
two-party voting when more than one opinion is sampled at each step.
We give some results for the outcome of  two-party voting  on r
regular expanders when we use two-sample voting. Compared to
single-sample voting, the performance of this process is more
consistent and obtained more rapidly.

問合せ先：来嶋（B01）