Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof would certainly be more than a few lines. I have seen a paper that proves this, but cannot find it. Does anyone know of such a paper? I need this in my paper (I am doing a reduction from this problem) and would prefer not to repeat the argument if someone has written it up in detail already. Any result which would imply this in a few lines would be useful, too.
After some more searching, I managed to find a proof in these lecture notes . The proof goes via Yao's principle and the lower bound is n/3. If someone knows of a published paper or a book that I may cite for this fact, I am still interested.