Haslegrave, John and Puljiz, Mate (2017) Reaching consensus on a connected graph. Journal of Applied Probability, 54 (1). pp. 181-198. doi:https://doi.org/10.1017/jpr.2016.94

Preview

PDF WRAP-Haslegrave-Reaching-Consensus-Accepted.pdf - Accepted Version - Requires a PDF viewer. Download (749Kb) | Preview

Request Changes to record.

Abstract

We study a simple random process in which vertices of a connected graph reach consensus through pairwise interactions. We compute outcome probabilities, which do not depend on the graph structure, and consider the expected time until a consensus is reached. In some cases we are able to show that this is minimised by Kn. We prove an upper bound for the case p = 0 and give a family of graphs which asymptotically achieve this bound. In order to obtain the mean of the waiting time we also study a gambler’s ruin process with delays. We give the mean absorption time and prove that it monotonically increases with p ∈ [0, 1/2] for symmetric delays.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Random walks (Mathematics), Stochastic processes, Charts, diagrams, etc., Graph theory.
Journal or Publication Title:	Journal of Applied Probability
Publisher:	Applied Probability Trust
ISSN:	0021-9002
Official Date:	March 2017
Dates:	Date Event March 2017 Published 4 April 2017 Available 18 July 2016 Accepted
Date of first compliant deposit:	21 July 2016
Volume:	54
Number:	1
Page Range:	pp. 181-198
DOI:	https://doi.org/10.1017/jpr.2016.94
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access
Funder:	Seventh Framework Programme (European Commission) (FP7)
Grant number:	HIERATIC (316705)
Related URLs:	Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads