On 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 this paper we study randomized algorithms for determining majority, which are allowed to err with probability at most epsilon. We show that any such algorithm must have expected running time at least (2/3 - o(1)) n. Moreover, we provide a randomized algorithm which shows that this result is best possible. These extend a result of De Marco and Pelc [G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006) 823-834]. (C) 2008 Elsevier B.V. All rights reserved.