CMP.11:5.1 - Determine whether any bit is one

An unknown n-bit input is accessed one bit at a time. Return whether it contains a one. For a deterministic always-correct algorithm, answer zero to every query. Before all n distinct positions have been read, both the all-zero input and an input with a one at an unread position remain possible. Their correct answers differ. Therefore some input requires n queries. A complete scan attains that bound.

Allow a randomized algorithm that uses at most q queries on every run and errs with probability at most δ<1/2 on every input. Couple its runs on the all-zero input and on the input with just position j set to one, using the same random choices. Unless the zero-input run queries j, both runs have the same transcript and output. Let p_j be the probability it queries j on the zero input. Consequently,

P(output 1 on singleton j) ≤ P(output 1 on zeros)+p_j ≤ δ+p_j.

Correctness on the singleton requires the left side to be at least 1-δ, so p_j≥1-2δ. Summing over j gives

q ≥ sum_j p_j ≥ n*(1-2δ).

For δ=1/3, this gives q≥n/3. It is a lower bound under the stated maximum-query convention, not a claim that every randomized algorithm uses exactly that many queries.

Now change the promise: either all bits are zero or at least half are one. Query k independently chosen uniform positions, returning one if any query finds it. On a nonzero promised input, the probability of missing every one is at most 2^-k; zero inputs always receive the correct answer. For 0<δ<1/2, choosing k=ceil(log2(1/δ)) therefore achieves the error requirement independently of n, subject to generating and accessing those positions. For n>2, the singleton inputs used in the earlier bound are excluded. This explains why the new algorithm escapes that growth in cost.