Geodesic
Leader election: a Markov chain approach
Mathematica Applicanda, Tome 44 (2016) no. 1, pp. 113-134.

Voir la notice de l'article provenant de la source Annales Societatis Mathematicae Polonae Series

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).
DOI : 10.14708/ma.v44i1.1141
Classification : Primary 60J10, secondary 60J20, 60J50, 68W40.
Mots-clés : Boundary theory, Election algorithms, Geometric distribution, Markov chain, maxima, periodicity, tail σ-field 
@article{10_14708_ma_v44i1_1141,
     author = {Rudolf Gr\"ubel and Klass Hagemann},
     title = {Leader election: a {Markov} chain approach},
     journal = {Mathematica Applicanda},
     pages = { 113--134},
     publisher = {mathdoc},
     volume = {44},
     number = {1},
     year = {2016},
     doi = {10.14708/ma.v44i1.1141},
     language = {pl},
     url = {http://geodesic.mathdoc.fr/articles/10.14708/ma.v44i1.1141/}
}
TY  - JOUR
AU  - Rudolf Grübel
AU  - Klass Hagemann
TI  - Leader election: a Markov chain approach
JO  - Mathematica Applicanda
PY  - 2016
SP  -  113
EP  - 134
VL  - 44
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.14708/ma.v44i1.1141/
DO  - 10.14708/ma.v44i1.1141
LA  - pl
ID  - 10_14708_ma_v44i1_1141
ER  - 
%0 Journal Article
%A Rudolf Grübel
%A Klass Hagemann
%T Leader election: a Markov chain approach
%J Mathematica Applicanda
%D 2016
%P  113-134
%V 44
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.14708/ma.v44i1.1141/
%R 10.14708/ma.v44i1.1141
%G pl
%F 10_14708_ma_v44i1_1141
Rudolf Grübel; Klass Hagemann. Leader election: a Markov chain approach. Mathematica Applicanda, Tome 44 (2016) no. 1, pp.  113-134. doi : 10.14708/ma.v44i1.1141. http://geodesic.mathdoc.fr/articles/10.14708/ma.v44i1.1141/

Cité par Sources :