Randomized algorithms for the majority problem

In the majority problem, we are given n balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries. The answer is known to be n−B(n), where B(n) is the number of 1's in the binary representation of n. In [G. De Marco and A. Pelc, Randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006), 823–834], De Marco and Pelc proved that even if we use a randomized algorith which is allowed to fail with probability at most ε, we still need linear expected time to determine a ball in majority colour. We prove that any such algorithm has expected running time at least , where δ(ε)→0 as ε→0. Moreover, we provide a randomized algorithm showing that this result is best possible.