Number of survivors in the presence of a demon
Date
2012
Authors
Louchard G.
Prodinger H.
Ward M.D.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper complements the analysis of Louchard and Prodinger [LP08] on the number of rounds in a coin-flipping selection algorithm that occurs in the presence of a demon. We precisely analyze a very different aspect of the selection algorithm, using different methods of analysis. Specifically, we obtain precise descriptions of the distribution and all moments of the number of participants ultimately selected during the execution of the algorithm. The selection algorithm is robust in at least two significant ways. The presence of a demon allows for the precise analysis even when errors may occur between the rounds of the selection process. (The analysis also handles the more traditional case, in which no demon is involved.) The selection algorithm can also use either biased or unbiased coins. © 2012 Akadémiai Kiadó, Budapest, Hungary.
Description
Keywords
analysis of algorithms, approximation, asymptotic, coin flip, demon, distribution, factorial moment, generating function, leader election, poissonization, q-Pochhammer symbol, recurrence, survivor, trie
Citation
Periodica Mathematica Hungarica
64
1
101
117
64
1
101
117