# Choosing a random bit from a bitmap

Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so.

I have quite a large bitmap (~100 Million bits) (e.g. 100100101001010001001...010010). The bitmap is just an example, it doesn't have to start with 1 or end with 0.

Now, I need to choose randomly any 0-bit from the bitmap and retrieve it's position. Memory is not an issue in my case, I can maintain a few copies of the bitmap, if necessary. But the acceptable complexity of the algorithm would be linear or O(n lnn) in the worst case. Couldn't you advice a direction to move to? I'll appreciate any advices or refernces to some related resources.

• Practically speaking, bitmaps usually contain a decent fraction of zeroes, and so the trivial randomized algorithm works in $O(1)$ random accesses. Should your algorithm work in the worst case? Is random access for free? Do you care about time, space or both? Please state your exercise in full. – Yuval Filmus Oct 29 '15 at 12:32
• @YuvalFilmus Should your algorithm work in the worst case? Yes. Is random access for free? Yes. almost for free, it's very inexpensive in my case. Do you care about time, space or both? About time. – St.Antario Oct 29 '15 at 12:41
• @YuvalFilmus bitmaps usually contain a decent fraction of zeroes, and so the trivial randomized algorithm works in O(1) random accesses. What do you mean trivial randomizer? Couldn't you expland a bit or give a refernce? – St.Antario Oct 29 '15 at 12:42
• Buzzword: rejection sampling. – Raphael Oct 29 '15 at 17:40

There is a simple $O(n)$ algorithm using the technique of reservoir sampling. Keep a currently selected element $x$ (initially, none). Go over all bits in the file in order. When seeing the $m$th zero, put it in $x$ with probability $1/m$. You can show (exercise) that the final contents of $x$ is a uniformly random zero from the file.

If you are allowed preprocessing, you can store the locations of all zeroes in a new file, and then choose a uniformly random zero in $O(1)$ by choosing a uniformly random position in the list.

Practically speaking, we expect bitmaps to contain a decent fraction of zeroes – say at least 1%. This suggests querying uniformly random locations in the file until you reach a zero. The expected runtime of this algorithm is at most 100 random queries.

• The question may sound dumbly, but there's no constant time algorith for such bitmaps even if the random has a constant-time complexity, isn't? – St.Antario Oct 30 '15 at 6:29
• @St.Antario It depends on the model and the assumptions. – Yuval Filmus Oct 30 '15 at 8:00