How to select a loser (Q687117): Difference between revisions

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.