1
$\begingroup$

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)?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is it really reasonable to say that we can pick a random permutation in linear time? There are $n!$ of them, I would be inclined to think that the cost is at least $\Omega(\log n!) = \Omega(n \log n)$ $\endgroup$ – quicksort Feb 2 '17 at 22:16
  • $\begingroup$ @quicksort, right, but I'm talking about picking a pseudorandom permutation, selected by (say) a 256-bit seed. There might be only $2^{256}$ possible permutations, so you don't get a uniform distribution on all $n!$ possible permutations -- but you get something that is indistinguishable from a uniform distribution, for computationally bounded algorithms (say, for any algorithm that will terminate within the predicted lifetime of the solar system). (continued) $\endgroup$ – D.W. Feb 2 '17 at 22:18
  • $\begingroup$ In other words, information-theoretically the PRP is not truly random... but no computationally-bounded algorithm can ever tell the difference, except with exponentially small advantage (success probability), so it's "as good as uniform" for all engineering purposes. I'm using crypto to "cheat" the lower bounds: instead of achieving perfection, this solution achieves something that is in some sense not perfect but "exponentially close to perfect". $\endgroup$ – D.W. Feb 2 '17 at 22:18
  • $\begingroup$ Apparently you strongly believe that $P \neq NP$ :-) Joking aside, I was talking from a theoretical perspective. I love the crypto approach and agree that the algorithm you suggest is perfectly fine for any practical purpose. $\endgroup$ – quicksort Feb 2 '17 at 22:32
  • $\begingroup$ @quicksort, got it. Yup, I'm 100% with you. Think I should edit the answer to mention this caveat? $\endgroup$ – D.W. Feb 2 '17 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.