Number of survivors in the presence of a demon
- PDF / 205,104 Bytes
- 17 Pages / 595 x 842 pts (A4) Page_size
- 37 Downloads / 193 Views
NUMBER OF SURVIVORS IN THE PRESENCE OF A DEMON Guy Louchard1 , Helmut Prodinger2 and Mark Daniel Ward3 1
D´epartement d’Informatique, Universit´e Libre de Bruxelles CP 212, Boulevard du Triomphe, B-1050, Bruxelles, Belgium E-mail: [email protected] 2
Department of Mathematics, University of Stellenbosch 7602 Stellenbosch, South Africa E-mail: [email protected] 3
Department of Statistics, Purdue University 150 North University St., West Lafayette, IN 47907–2067, USA E-mail: [email protected] (Received May 3, 2010; Accepted June 10, 2010) [Communicated by B´ alint T´ oth]
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.
1. Introduction We precisely analyze the number of survivors in a selection process that occurs in the presence of a demon. Louchard and Prodinger [LP08] recently utilized a different methodology (for extreme value distributions, often referred to as “Gumbel Mathematics subject classification numbers: 05A16, 05A30, 60C05, 68W20, 68W40. Key words and phrases: analysis of algorithms, leader election, coin flip, survivor, demon, asymptotic, approximation, trie, q-Pochhammer symbol, factorial moment, distribution, generating function, recurrence, poissonization. 0031-5303/2012/$20.00 c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
102
G. LOUCHARD, H. PRODINGER and M. D. WARD
distributions”) to analyze the number of rounds required to perform the selection algorithm. The inclusion of a “demon” can be viewed as a generalization of traditional selection algorithms. The demon represents errors which might occur between rounds of the process. Another interpretation is that participants might be likely to drop out of the selection process for reasons unrelated to the coin flips in the selection process itself. In each round, exactly one participant is removed by the “demon” with probability ν; otherwise, the demon does not affect any participants in that round. Thus, a traditional selection algorithm (with no demon involved) is just a special case (using ν = 0) of our very general analysis. The special case ν = 0 (i.e., with no demon involved) is a selection process using a traversal of binary retrieval trees (tries), where a coin flip of “heads” is analogous to descending one direction in the trie, and a flip of “tails” corresponds
Data Loading...
