Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-10T05:56:56.097Z Has data issue: false hasContentIssue false
  • English
  • Français

Reaching consensus on a connected graph

Part of: Stochastic processes Special processes

Published online by Cambridge University Press:  04 April 2017

John Haslegrave  and
Mate Puljiz
John Haslegrave*
Affiliation:
University of Sheffield
Mate Puljiz*
Affiliation:
University of Birmingham
*
* Current address: Mathematics Institute, Zeeman Building, University of Warwick, CoventryCV4 7AL, UK. Email address: j.haslegrave@warwick.ac.uk
** Postal address: School of Mathematics,, University of Birmingham, BirminghamB15 2TT, UK.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 K n . We prove an upper bound for the p=0 case 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.

Keywords

Stabilisation timerandom walkcoupon collectorvoter model

MSC classification

Primary: 60G40: Stopping times; optimal stopping problems; gambling theory
Secondary: 60G50: Sums of independent random variables; random walks 60K35: Interacting random processes; statistical mechanics type models; percolation theory

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 1 , March 2017 , pp. 181 - 198
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Bruss, F. T., Louchard, G. and Turner, J. W. (2003).On the N-tower problem and related problems.Adv. Appl. Prob. 35,278–294.Google Scholar
[2] Clifford, P. and Sudbury, A. (1973).A model for spatial conflict.Biometrika 60,581–588.Google Scholar
[3] Cooper, C., Elsässer, R., Ono, H. and Radzik, T. (2013).Coalescing random walks and voting on connected graphs.SIAM J. Discrete Math. 27,1748–1758.CrossRefGoogle Scholar
[4] Donnelly, P. and Welsh, D. (1983).Finite particle systems and infection models.Math. Proc. Camb. Phil. Soc. 94,167–182.Google Scholar
[5] El-Shehawey, M. A. (2009).On the gambler’s ruin problem for a finite Markov chain.Statist. Prob. Lett. 79,1590–1595.CrossRefGoogle Scholar
[6] Engel, A. (1993).The computer solves the three tower problem.Amer. Math. Monthly 100,62–64.CrossRefGoogle Scholar
[7] Erdős, P. and Rényi, A. (1961).On a classical problem of probability theory.Magyar Tud. Akad. Mat. Kutató Int. Közl. 6,215–220.Google Scholar
[8] Feller, W. (1968).On the gambler’s ruin problem for a finite Markov chain. In An Introduction to Probability Theory and Its Applications Vol. I, 3rd edn.John Wiley,New York.Google Scholar
[9] Gut, A. (2013).The gambler’s ruin problem with delays.Statist. Prob. Lett. 83,2549–2552.Google Scholar
[10] Hassin, Y. and Pelag, D. (2001).Distributed probabilistic polling and applications to proportionate agreement.Inform. Comput. 171,248–268.Google Scholar
[11] Katriel, G. (2013).Gambler’s ruin probability—a general formula.Statist. Prob. Lett. 83,2205–2210.Google Scholar
[12] Katriel, G. (2014).Gambler’s ruin: the duration of play.Stoch. Models 30,251–271.Google Scholar
[13] Kmet, A. and Petkovšek, M. (2002).Gambler’s ruin problem in several dimensions..Adv. Appl. Math. 28,107–118.Google Scholar
[14] Kwiatkowska, M., Norman, G. and Parker, D. (2011).PRISM 4.0: verification of probabilistic real-time systems. In Computer Aided Verification (Lecture Notes Comput. Sci. 6806)Springer,Heidelberg, pp.585–591.Google Scholar
[15] Lengyel, T. (2009).The conditional gambler’s ruin problem with ties allowed.Appl. Math. Lett. 22,351–355.Google Scholar
[16] Myers, A. N. and Wilf, H. S. (2006).Some new aspects of the coupon collector’s problem.SIAM J. Discrete Math. 17,1–17.Google Scholar
[17] Newman, D. J. and Shepp, L. (1960).The double dixie cup problem.Amer. Math. Monthly 67,58–61.Google Scholar
[18] Rowe, J. E., Vose, M. D. and Wright, A. H. (2005).Coarse graining selection and mutation. In Foundations of Genetic Algorithms (Lecture Notes Comput. Sci. 3469).Springer,Berlin, pp.176–191.Google Scholar
[19] Rowe, J. E., Vose, M. D. and Wright, A. H. (2006).Differentiable coarse graining.Theoret. Comput. Sci. 361,111–129.CrossRefGoogle Scholar
[20] Stirzaker, D. (1994).Tower problems and martingales.Math. Scientist 19,52–59.Google Scholar
[21] Stirzaker, D. (2006).Three-handed gambler’s ruin.Adv. Appl. Prob. 38,284–286.Google Scholar
[22] Swan, Y. C. and Bruss, F. T. (2006).A matrix-analytic approach to the N-player ruin problem.J. Appl. Prob. 43,755–766.Google Scholar
[23] Vose, M. D. (1999).The Simple Genetic Algorithm.MIT Press,Cambridge.Google Scholar
[24] Williams, D. (1991).Probability with Martingales.Cambridge University Press.Google Scholar