  Given $n$ colored balls, we want to detect if more than $\lfloor n/2\rfloor$
of them have the same color, and if so find one ball with such majority color.
We are only allowed to choose two balls and compare their colors, and the goal
is to minimize the total number of such operations. A well-known exercise is to
show how to find such a ball with only $2n$ comparisons while using only a
logarithmic number of bits for bookkeeping. The resulting algorithm is called
the Boyer--Moore majority vote algorithm. It is known that any deterministic
method needs $\lceil 3n/2\rceil-2$ comparisons in the worst case, and this is
tight. However, it is not clear what is the required number of comparisons if
we allow randomization. We construct a randomized algorithm which always
correctly finds a ball of the majority color (or detects that there is none)
using, with high probability, only $7n/6+o(n)$ comparisons. We also prove that
the expected number of comparisons used by any such randomized method is at
least $1.019n$.
