Selecting a random 'bad' element from an array of $n$ values in $O(n)$ time and $O(1)$ space without knowing how many bad elements or where they are

Question

I have an array of elements $A = [x_0, x_1, \ldots, x_n]$, such that for some $0 \leq k \leq \frac{n}{2}$, there are $k$ 'bad' elements in $A$, but I don't know what indices they are at, or indeed, how many there are aside from the given bounds. I have a function which can, in $O(1)$ time, check if something is 'bad' or 'good'. As $A$ is an array, I have the ability to access any element of $A$ in $O(1)$ time if I know the index.

My goal is to devise a procedure which, in $O(n)$ time and $O(1)$ space, returns the index of a randomly-selected 'bad' element in $A$, or $-1$ if no such element exists. Any 'bad' element should have an equal chance of being selected. My current approach was something like this, assuming coin is a procedure that returns 0 or 1 with equal probability:

function randombad(A):
    result := -1
    for (i from 0 to (length(A) -1))
        if (A[i] is bad and result = -1)
            result := i
        else if (A[i] is bad)
            flip = coin()
            if (coin = 1)
                result := i
    return result

However, if $k > 2$, this obviously gives later 'bad' elements a higher chance of being chosen, which is not what I want. Is there a way to do what I want without having to store every 'bad' element as I find them (which violates the $O(1)$ space constraint)?

Answer 1

You can do better than $O(n)$ time: indeed $O(n/k)$ time and $O(1)$ space is achievable, with a perfectly uniform distribution on bad elements. Let me explain how, by starting with a simple strategy and building up to a solution that meets all of your requirements.

If we didn't have to deal with the possibility that no bad element exists, then a simple (but sub-optimal) method is to apply rejection sampling: repeatedly pick a random element, test if it is bad, and if it is bad, return it. In other words, you return the first bad element found.

If there is at least one bad element, this method is within a constant factor of optimal; the average running time is $O(n/k)$, and it uses only $O(1)$ space.

The big flaw with this simple approach is that if there are no bad elements, this algorithm runs forever. Fortunately, we can repair that with a simple fix, and at the same time improve running time to optimal.

Here's how. Pick a random permutation $\pi$ on $\{1,\dots,n\}$. Then, sequentially test $A[\pi(1)]$, $A[\pi(2)]$, ..., and return the first bad element you find. If you have tested all $n$ array elements and found no bad element, terminate and return -1.

This algorithm requires (on average) $\min(n/k,n)$ queries to the oracle, which is optimal -- you can't do better than that. The space requirement, apart from the time to store $\pi$, is $O(1)$. This also provides a perfectly uniform distribution on the set of bad points: because it is essentially a rejection sampling strategy, it is correct for the same reason that rejection sampling is.

At this point you might object that storing the permutation $\pi$ explicitly requires $O(n)$ space. You would be correct, but fortunately there is a fix to that: you can construct a pseudorandom permutation on $\{1,\dots,n\}$ with $O(1)$ space to store it, and $O(1)$ time to evaluate the permutation. See Lazily computing a random permutation of the positive integers and https://crypto.stackexchange.com/q/20035/351 and links there. Technically speaking, the space and time to evaluate the oracle is probably more like $O(\log n)$ than $O(1)$, but given that $n\le 2^{64}$ in practice, the difference might or might not be critical.

Caveat: This is an engineering-oriented answer. From a theoretical perspective, it's probably not fully satisfying. The use of a pseudorandom permutation means that the distribution on bad instances is not perfectly uniformly random; it is close to random (indistinguishable from random). Also, I haven't been fully-rigorous about the running time or space requirements for the pseudorandom permutation. Finally, the use of pseudorandom permutations relies on unproven assumptions (that certain crypto primitives are security). See the comments for more discussion of caveats.