Number of survivors in the presence of a demon

Simple item page
dc.contributor.authorLouchard G.
dc.contributor.authorProdinger H.
dc.contributor.authorWard M.D.
dc.date.accessioned2012-04-12T08:13:00Z
dc.date.available2012-04-12T08:13:00Z
dc.date.issued2012
dc.description.abstractThis 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.
dc.identifier.citationPeriodica Mathematica Hungarica
dc.identifier.citation64
dc.identifier.citation1
dc.identifier.citation101
dc.identifier.citation117
dc.identifier.issn315303
dc.identifier.other10.1007/s10998-012-9101-9
dc.identifier.urihttp://hdl.handle.net/10019.1/20475
dc.subjectanalysis of algorithms
dc.subjectapproximation
dc.subjectasymptotic
dc.subjectcoin flip
dc.subjectdemon
dc.subjectdistribution
dc.subjectfactorial moment
dc.subjectgenerating function
dc.subjectleader election
dc.subjectpoissonization
dc.subjectq-Pochhammer symbol
dc.subjectrecurrence
dc.subjectsurvivor
dc.subjecttrie
dc.titleNumber of survivors in the presence of a demon
dc.typeArticle
Files
Collections
Stellenbosch University - Scopus Publications