Leader election using random walks

MaRDI QIDQ2954460zbMATH OpenFDO

Authors Gerold Alsmeyer, Zakhar Kabluchko, Alexander Marynych

Publication date 13 January 2017

Full work available at URL https://arxiv.org/abs/1607.08731, http://alea.impa.br/articles/v13/13-39.pdf

zbMATH Keywords

Galton-Watson branching processleader electionrandom sieverandom walksrestricted self-similaritystable point processstochastic fixed-point equation

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Self-similar stochastic processes (60G18) Sums of independent random variables; random walks (60G50) Stable stochastic processes (60G52) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

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,ldots,M$ leave the game; and the number of players among $1,2,ldots,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 stochastic-fixed 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.

Recommendations

• A leader-election procedure using records
• Convergence of some leader election algorithms
• Leader election: a Markov chain approach
• The asymmetric leader election algorithm: number of survivors near the end of the game
• Survivors in leader election algorithms

Cites work

• A leader-election procedure using records
• Almost sure convergence in Markov branching processes with infinite mean
• Analysis of an asymmetric leader election algorithm
• Coalescence in the recent past in rapidly growing populations
• Distances in random graphs with finite mean and infinite variance degrees
• How to select a loser
• scientific article; zbMATH DE number 43570 (Why is no real title available?)
• scientific article; zbMATH DE number 3349105 (Why is no real title available?)
• Inequalities for the $r$th Absolute Moment of a Sum of Random Variables, $1 \leqq r \leqq 2$
• Leader election: a Markov chain approach
• Moment Convergence of Sample Extremes
• On the asymptotic behaviour of branching processes with infinite mean
• On the distribution for the duration of a randomized leader election algorithm
• On the multiplicity of the maximum in a discrete random sample
• Semi-selfsimilar processes
• Stability for random measures, point processes and discrete semigroups
• Strictly stable distributions on convex cones
• The Galton-Watson process with infinite mean
• The simple branching process with infinite mean. I
• The simple branching process: a note on convergence when the mean is infinite

Cited in

(6)

• Sieving random iterative function systems
• scientific article; zbMATH DE number 1305532 (Why is no real title available?)
• Simple and Efficient Leader Election
• Leader election: a Markov chain approach
• Infinite system of random walkers: winners and losers
• A leader-election procedure using records

This page was built for publication: Leader election using random walks

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