Leader election: a Markov chain approach

Rudolf Grübel, and Klass Hagemann. "Leader election: a Markov chain approach." Mathematica Applicanda 44.1 (2016): null. <http://eudml.org/doc/293232>.

@article{RudolfGrübel2016,
abstract = {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).},
author = {Rudolf Grübel, Klass Hagemann},
journal = {Mathematica Applicanda},
keywords = {Boundary theory; Election algorithms; Geometric distribution; Markov chain; maxima; periodicity; tail σ-field},
language = {eng},
number = {1},
pages = {null},
title = {Leader election: a Markov chain approach},
url = {http://eudml.org/doc/293232},
volume = {44},
year = {2016},
}

TY - JOUR
AU - Rudolf Grübel
AU - Klass Hagemann
TI - Leader election: a Markov chain approach
JO - Mathematica Applicanda
PY - 2016
VL - 44
IS - 1
SP - null
AB - 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).
LA - eng
KW - Boundary theory; Election algorithms; Geometric distribution; Markov chain; maxima; periodicity; tail σ-field
UR - http://eudml.org/doc/293232
ER -