A leader-election procedure using records

DOI10.1214/16-AOP1167zbMATH Open1392.60025arXiv1512.04750OpenAlexW2962902550MaRDI QIDQ682267FDOQ682267

Authors: Gerold Alsmeyer, Zakhar Kabluchko, Alexander Marynych 

Publication date: 14 February 2018

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: The study of the number of collisions in a Poisson-Dirichlet coalescent leads to the analysis of the following version of a stochastic leader-elec-tion algorithm. Consider an infinite family of persons, labeled by $1,2,3,ldots$, who generate iid random numbers from an arbitrary continuous distribution. Those persons who have generated a record value, that is, a value larger than the values of all previous persons, stay in the game, all others must leave. The remaining persons are relabeled by $1,2,3,ldots$ maintaining their order in the first round, and the election procedure is repeated independently from the past and indefinitely. We prove limit theorems for a number of relevant functionals for this procedure, notably the number of rounds $T(M)$ until all persons among $1,ldots,M$, except the first one, have left (as $Moinfty$). For example, we show that the sequence $(T(M)-lo{g}^{\ast }M{)}_{MinmathbbN}$, where $lo{g}^{\ast }$ denotes the iterated logarithm, is tight, and study its weak subsequential limits. We further provide an appropriate and apparently new kind of normalization (based on tetrations) such that the original labels of persons who stay in the game until round $n$ converge (as $noinfty$) to some random non-Poissonian point process and study its properties. The results are applied to study subsequential distributional limits for the number of collisions in the Poisson-Dirichlet coalescent.

Full work available at URL: https://arxiv.org/abs/1512.04750

Recommendations

• Convergence of some leader election algorithms
• Leader election using random walks
• Leader election: a Markov chain approach
• The asymmetric leader election algorithm: number of survivors near the end of the game
• Asymptotic properties of a leader election algorithm

zbMATH Keywords

absorption timeiterated logarithmrandom recursionPoisson-Dirichlet coalescenttetration

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Central limit and other weak theorems (60F05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cited In (3)

• Sieving random iterative function systems
• Leader election using random walks
• Simple and Efficient Leader Election

This page was built for publication: A leader-election procedure using records

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q682267)