Mark Ward (Purdue University):
Analysis of a Randomized Selection Algorithm
We consider a randomized selection algorithm in which Mn of n participants are selected. In each round, a moderator flips a biased coin, and each
partipant does the same. Participants whose result does not agree with the moderator's are dropped. We define Mn to be the number of participants in
the final round. For the random variable Mn, we give precise asymptotic characteristics of its fractional moments, exhibit periodic fluctuations in its
distribution, and show it has no limiting distribution. The results we develop are proved by probabilistic and analytical techniques of the analysis of
algorithms. In particular, we utilize recurrence relations, analytical poissonization and depoissonization, the Mellin transform, and complex analysis.