- Tytuł:
- Leader election: a Markov chain approach
- Autorzy:
-
Grübel, Rudolf
Hagemann, Klass - Powiązania:
- https://bibliotekanauki.pl/articles/747970.pdf
- Data publikacji:
- 2016
- Wydawca:
- Polskie Towarzystwo Matematyczne
- Tematy:
-
Boundary theory
Election algorithms
Geometric distribution
Markov chain
maxima
periodicity
tail σ-field
algorytm selekcji, rozkład geometryczny, łańcuch Markowa, maxima, okresowość, ogonowe sigma--ciała - Opis:
-
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 eliminacje (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ńcuch 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 Renyi-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 Grubela(2003).
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(2003). - Źródło:
-
Mathematica Applicanda; 2016, 44, 1
1730-2668
2299-4009 - Pojawia się w:
- Mathematica Applicanda
- Dostawca treści:
- Biblioteka Nauki
Artykuł