Leader election : A Markov chain approach

• Autorzy: Grübel R. , Hagemann K.

Identyfikatory

DOI

10.14708/ma.v44i1.1141

Warianty tytułu

PL

Model Markowski wyboru przywódcy

• Języki publikacji: EN

Abstrakty

EN

A well-studied randomized election algorithm proceeds as follows: In each round the remaining candidates each toss a coin and leave the competition if they obtain heads. Of interest is the number of rounds required and the number of winners, both related to maxima of geometric random samples, as well as the number of remaining participants as a function of the number of rounds. We introduce two related Markov chains and use ideas and methods from discrete potential theory to analyse the respective asymptotic behaviour as the initial number of participants grows. One of the tools used is the approach via the Rényi-Sukhatme representation of exponential order statistics, which was first used in the leader election context by Bruss and Grübel in [BG03].

PL

W artykule przywołany jest dobrze znany i szczegółowo zbadany następujący algorytm losowego wyboru lidera. W kolejnych krokach każdy kandydat rzuca monetą. Jeśli wyrzuci orła, to kończy eliminację (nie przechodzi do następnej tury). Interesuje nas liczba rund do wyłonienia lidera bądź liczba pozostałych kandydatów w powiązaniu z maksimum ciągu zmiennych losowych o rozkładzie geometrycznym. Również wyznaczamy rozkład liczby pozostałych kandydatów jako funkcji liczby tur. W celu odpowiedzi na postawione pytania konstruowane są dwa powiązane ze sobą łańcuchy Markowa. Wykorzystując metody teorii potencjału badana jest asymptotyka przy rosnącej początkowej liczbie kandydatów. Jednym z wykorzystywanych narzędzi jest reprezentacja Rényi-Sukhatme dla statystyk porządkowych rozkładu wykładniczego, która została po raz pierwszy użyta do zagadnienia wyborów lidera przez Brussa i Grübela w [BG03].

Słowa kluczowe

EN

boundary theory; election algorithms; geometric distribution; Markov chain; maxima; periodicity; tail σ-field

PL

algorytm selekcji; rozkład geometryczny; łańcuch Markowa; maxima; okresowość; ogonowe σ-ciała

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2016
• Tom: Vol. 44, No. 1
• Strony: 113--134
• Opis fizyczny: Bibliogr. 26 poz., fot.

Twórcy

autor

Grübel R.

• Leibniz Universität Hannover, Institut für Mathematische Stochastik, Postfach 6009, D–30060 Hannover, Germany

autor

Hagemann K.

• Leibniz Universität Hannover, Institut für Mathematische Stochastik, Postfach 6009, D–30060 Hannover, Germany

Bibliografia

• 1. [AKM15] G. Alsmeyer, Z. Kabluchko, and A. Marynych, A leader-election procedure using records, ArXiv e-prints (2015).
• 2. [AN72] Krishna B. Athreya and Peter E. Ney, Branching processes, Springer-Verlag, New York-Heidelberg, 1972, Die Grundlehren der mathematischen Wissenschaften, Band 196. MR 0373040 (51#9242)
• 3. [AR06] Gerold Alsmeyer and Uwe Rösler, The Martin entrance boundary of the Galton-Watson process, Ann. Inst. H. Poincaré Probab. Statist. 42 (2006), no. 5, 591–606. MR 2259977 (2007g:60097).
• 4. [BES95] Yuliy Baryshnikov, Bennett Eisenberg, and Gilbert Stengle, A necessary and sufficient condition for the existence of the limiting probability of a tie for first place, Statist. Probab. Lett. 23 (1995), no. 3, 203–209. MR 1340152 (96d:60015).
• 5. [BG03] F. Thomas Bruss and Rudolf Grübel, On the multiplicity of the maximum in a discrete random sample, Ann. Appl. Probab. 13 (2003), no. 4, 1252–1263. MR 2023876 (2005f:60024).
• 6. [BO90] F. Thomas Bruss and Colm Art O’Cinneide, On the maximum and its uniqueness for geometric random samples, J. Appl. Probab. 27 (1990), no. 3, 598–610. MR 1067025 (92a:60096).
• 7. [Bre68] Leo Breiman, Probability, Addison-Wesley Publishing Company, Reading, Mass.-London-Don Mills, Ont., 1968. MR 0229267 (37#4841).
• 8. [Doo59] J. L. Doob, Discrete potential theory and boundaries, J. Math. Mech. 8 (1959), 433–458; erratum 993. MR 0107098 (21 #5825).
• 9. [Dyn78] E. B. Dynkin, Sufficient statistics and extreme points, Ann. Probab. 6 (1978), no. 5, 705–730. MR 0518321 (58 #24575).
• 10. [EGW16] S. N. Evans, R. Grübel, and A. Wakolbinger, Doob–Martin boundary of Rémy’s tree growth chain, Ann. Probab. (2016+), to appear.
• 11. [ESS93] Bennett Eisenberg, Gilbert Stengle, and Gilbert Strang, The asymptotic probability of a tie for first place, Ann. Appl. Probab. 3 (1993), no. 3, 731–745. MR 1233622 (95d:60044).
• 12. [FMS96] James Allen Fill, Hosam M. Mahmoud, and Wojciech Szpankowski, On the distribution for the duration of a randomized leader election algorithm, Ann. Appl. Probab. 6 (1996), no. 4, 1260–1283. MR 1422986 (97k:05053).
• 13. [GIM10] Alexander Gnedin, Alexander Iksanov, and Alexander Marynych, Limit theorems for the number of occupied boxes in the Bernoulli sieve, Theory Stoch. Process. 16 (2010), no. 2, 44–57. MR 2777900.
• 14. [GINR09] Alexander V. Gnedin, Alexander M. Iksanov, Pavlo Negadajlov, and Uwe Rösler, The Bernoulli sieve revisited, Ann. Appl. Probab. 19 (2009), no. 4, 1634–1655. MR 2538083.
• 15. [Gne04] Alexander V. Gnedin, The Bernoulli sieve, Bernoulli 10 (2004), no. 1, 79–96. MR 2044594.
• 16. [Grü13] Rudolf Grübel, Kombinatorische Markov-Ketten, Math. Semesterber. 60 (2013), no. 2, 185–215. MR 3106672.
• 17. [Grü14] Search trees: metric aspects and strong limit theorems, Ann. Appl. Probab. 24 (2014), no. 3, 1269–1297. MR 3199986.
• 18. [Hag16] Klaas Hagemann, Doob-Martin-Theorie diskreter Markov-Ketten: Struktur und Anwendungen, Ph.D. thesis, Leibniz Universität Hannover, 2016.
• 19. [KM14] Ravi Kalpathy and Hosam Mahmoud, Perpetuities in fair leader election algorithms, Adv. in Appl. Probab. 46 (2014), no. 1, 203–216. MR 3189055.
• 20. [KP96] Peter Kirschenhofer and Helmut Prodinger, The number of winners in a discrete geometrically distributed sample, Ann. Appl. Probab. 6 (1996), no. 2, 687–694. MR 1398064 (97g:60016).
• 21. [KSK76] John G. Kemeny, J. Laurie Snell, and Anthony W. Knapp, Denumerable Markov chains, second ed., Springer-Verlag, New York, 1976, With a chapter on Markov random fields, by David Griffeath, Graduate Texts in Mathematics, No. 40. MR 0407981 (53#11748).
• 22. [Lau88] Steffen L. Lauritzen, Extremal families and systems of sufficient statistics, Lecture Notes in Statistics, vol. 49, Springer-Verlag, New York, 1988. MR 971253 (90g:62010).
• 23. [LP09] Guy Louchard and Helmut Prodinger, The asymmetric leader election algorithm: another approach, Ann. Comb. 12 (2009), no. 4, 449–478. MR 2496127 (2010e:60016).
• 24. [SW86] Galen R. Shorack and Jon A. Wellner, Empirical processes with applications to statistics, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1986. MR 838963 (88e:60002).
• 25. [Woe00] Wolfgang Woess, Random walks on infinite graphs and groups, Cambridge University Press, Cambridge, 2000. MR 1743100 (2001k:60006).
• 26. [Woe09] Denumerable Markov chains, EMS Textbooks in Mathematics, European Mathematical Society (EMS), Zürich, 2009, Generating functions, boundary theory, random walks on trees. MR 2548569 (2011f:60142).

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.