Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-05T04:32:47.585Z Has data issue: false hasContentIssue false
  • English
  • Français

Reaching consensus on a connected graph

Part of: Special processes Stochastic 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: [email protected]
** Postal address: School of Mathematics,, University of Birmingham, BirminghamB15 2TT, UK.
Get access Rights & Permissions [Opens in a new window]

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 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
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 1 , March 2017 , pp. 181 - 198
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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