Leader election using random walks

Alsmeyer G., Kabluchko Z., Marynych A.

Research article (journal) | Peer reviewed

Abstract

In the classical leader election procedure all players toss coins independently and those who get tails leave the game, while those who get heads move to the next round where the procedure is repeated. We investigate a generalizion of this procedure in which the labels (positions) of the players who remain in the game are determined using an integer-valued random walk. We study the asymptotics of some relevant quantities for this model such as: the positions of the persons who remained after n rounds; the total number of rounds until all the persons among 1, 2, . . ., M leave the game; and the number of players among 1, 2, . . ., M who survived the first n rounds. Our results lead to some interesting connection with Galton-Watson branching processes and with the solutions of certain stochasticfixed point equations arising in the context of the stability of point processes under thinning. We describe the set of solutions to these equations and thus provide a characterization of one-dimensional point processes that are stable with respect to thinning by integer-valued random walks.

Details about the publication

JournalLatin American Journal of Probability and Mathematical Statistics (ALEA)
Volume13
Issue2
Page range1095-1122
StatusPublished
Release year2016
Language in which the publication is writtenEnglish
Link to the full texthttps://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85000799312&origin=inward
KeywordsGalton-Watson branching process; Leader-election procedure; Random sieve; Restricted self-similarity; Stable point process; Stochastic-fixed point equation

Authors from the University of Münster

Alsmeyer, Gerold
Professur für Mathematische Stochastik (Prof. Alsmeyer)
Kabluchko, Zakhar
Professorship for probability theory (Prof. Kabluchko)