Given a bit string of length $n$, I should develop a probabilistic algorithm that answers one of the following questions:
- Does the bit string have more zeros than ones?
- Does the bit string have more ones than zeros?
- Does the number of zeros (/ones respectively) lies between $0.4n$ and $0.6n$?
The probability that the answer is correct should be at least $0.99$. Notice that the algorithm has to answer only one of the three questions for a given bit string, and it does not always have to be the same question it answers. The algorithm should run in $O(1)$.
Generally, my method would be to choose some sample set of $k$ bits of the bit string at random and then approximate the ratio with this sample set, which yields the desired probability when choosing the size accordingly. But since the runtime constraint is that tight, I don't really think that I could proceed with this method. If I could somehow get a bound for the ratio that doesn't depend on $n$, I could get a constant runtime, but I don't really know how to do this. I thought about letting the ratio be $0.5$ which would be the expected ratio for a randomly chosen bit string, but I don't think that this approach would be valid. Any ideas how one could tackle this problem?
Edit: I am not allowed to use the normal distribution, the problem is solvable without using it.