How to select a loser
type: Item
instance of: scholarly article
title: How to select a loser
zbMATH Open document ID: 0795.90103
DOI: 10.1016/0012-365X(93)90572-B
published in: Discrete Mathematics
publication date: 1994-09-22T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 91A60
Mathematics Subject Classification ID: 11B68
zbMATH DE Number: 429142
zbMATH Keywords: coin-flippings
zbMATH Keywords: selection problem
author: Helmut Prodinger
reviewed by: Ivan Křivý
MaRDI profile type: Publication
cites work: Digital Search Trees Revisited
cites work: Q4385514
cites work: Q5585020
cites work: &lt;tex&gt;Q&lt;/tex&gt;-ary collision resolution algorithms in random-access systems with free or blocked channel access
cites work: Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms
cites work: The evaluation of an alternative sum with applications to the analysis of some data structures
description: scientific article; zbMATH DE number 429142