×

zbMATH — the first resource for mathematics

How to select a loser. (English) Zbl 0795.90103
The author considers the following problem: A party of \(N\) people selects one of its members. Everybody is flipping a coin with outputs 0 and 1, each with probability 1/2. Then, recursively, the 0-party continues until the loser is found. It is shown that this procedure stops on the average after about \(\log_ 2 N\) steps. The average size (number of nodes) of such an incomplete tree is about \(2\log_ 2 N\), the average number of coin-flippings being exactly \(2N\). Some modifications of the selection problem are also discussed.

MSC:
91A60 Probabilistic games; gambling
11B68 Bernoulli and Euler numbers and polynomials
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Flajolet, P.; Sedgewick, R., Digital search trees revisited, SIAM J. comput., 15, 748-767, (1986) · Zbl 0611.68041
[2] Flajolet, P.; Vitter, J.S., Average-case analysis of algorithms and data structures, () · Zbl 0900.68251
[3] Knuth, D.E., The art of computer programming, Vol. 1, (1968), Addison-Wesley Reading, MA · Zbl 0191.17903
[4] Knuth, D.E., The art of computer programming, Vol. 3, (1973), Addison-Wesley Reading, MA · Zbl 0191.17903
[5] Mathys, P.; Flajolet, P., Q-ary collision resolution algorithms in random-access systems with free or blocked channel access, IEEE trans. inform. theory, 31, 217-243, (1985) · Zbl 0566.94001
[6] Szpankowski, W., Solution of a linear recurrence equation arising in the analysis of some algorithms, SIAM J. algebraic discrete methods, 8, 233-250, (1987) · Zbl 0648.68059
[7] Szpankowski, W., The evaluation of an alternative sum with applications to the analysis of some data structures, Inform. process. lett., 28, 13-19, (1988) · Zbl 0657.68071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.