Given a bit string of length $n$, I should develop a probabilistic algorithm that answers one of the following questions:

  1. Does the bit string have more zeros than ones?
  2. Does the bit string have more ones than zeros?
  3. 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.

  • $\begingroup$ If you know about and are allowed to use the Bienaymé-Tchebychev inequality there is a fairly simple solution. In the third option I presume you mean the number of ,,, and not the ratio of ... $\endgroup$
    – H. H. Rugh
    May 3 at 11:49
  • $\begingroup$ @H.H.Rugh thanks, I edited it. I'm allowed to use the inequality you mentioned. $\endgroup$
    – Jacob
    May 3 at 12:17
  • $\begingroup$ Do you actually have to answer all three questions with the algorithm, or do you have to say one of the three statements "More 0s than 1s", "More 1s than 0s", "Between $0.4n$ and $0.6n$ 1s" as the output? $\endgroup$ May 3 at 12:20
  • $\begingroup$ @MishaLavrov I only have to answer one of them, and it does not always have to be the same question I answer $\endgroup$
    – Jacob
    May 3 at 12:23
  • $\begingroup$ So effectively, it's the second thing: you get to pick which of the three statements to say, based on the input. $\endgroup$ May 3 at 12:24

Taking $N$ random samples among the $n$ bits produces i.i.d. Bernoulli variables $X_1,...,X_N$ with values being the bit and parameter $p$ (the real frequency of ones). The sum $S=X_1+\cdots + X_N$ is then binomial with parameters $(N,p)$ and your estimated frequency is $R=S/N$.

A natural strategy is then to say that you are in case 1,2 or 3 when $R\in[0,0.45)$, $R\in (0,55,1]$ and $R\in [0.45, 0.55]$, respectively. Your conclusion is certainly right if $|R-p|<0.05$ so in order to be right with probability 0.99 it suffices to have $P(|R-p|\geq 0.05) \leq 0.01$

To turn this into a condition on $N$, note that $E(R)=p$ and ${\rm Var}(R) = p(1-p)/N$. Then by Bienaymé-Tchebychev: $$ P(|R-p|\geq 0.05) \leq \frac{p(1-p)/N}{0.05^2}\leq 0.01$$ which is satisfied for any $p$ provided $N\geq \frac14 \times 20^2 \times 100 = 10000$.

  • $\begingroup$ exactly the point with $|R-p| <0.05$ was what I didn't get, I tried to make the difference zero what is obviously impossible for this task and the given constraints. Thanks a lot! $\endgroup$
    – Jacob
    May 3 at 12:41

Looking at a signle uniform-randomly chosen bit of the string is a bernoulli distribution with (unknown) parameter $p=\frac{\text{# ones}}{n}$. You can sample this distribution as often as you want, completely independent of $n$ (dont worry about choosing the same bit multiple times, thats not a problem).

The the question then is: how many times do you have to sample a bernoulli distribution in order to determine wheather $p\in[0.4,0.6]$ with $99%%$ confidence?

This is answered for example in this qeustion. (for practical purposes, you probably want to approximate the binomial distribution by a normal one. Working directly with binomial gets somewhat complicated).

In any case it should be clear that nothing depends on $n$, so the runtime of the algorithm is $O(1)$.

(this of course assumes that generating a random number between $1$ and $n$ only takes $O(1)$ time)

  • $\begingroup$ Hm I still don't really know how to proceed since I'm not allowed to use the normal distribution. $\endgroup$
    – Jacob
    May 1 at 20:27
  • $\begingroup$ actually, reading your question again, with your precise wording it is impossible. In case the true value is exactly $0.5$ (i.e. same number of ones and zeros), no finite number of samples can tell you with any confidence if the true value is above or below (or equal to) $0.5$. Increasing $k$ will make the confidence interval arbitrarily small, but can never decide between the two possibilities. Therefore I think the wording of you problem has to be subtly different. $\endgroup$
    – Simon
    May 1 at 20:44
  • $\begingroup$ maybe it's possible because the algorithm has to make only one conclusion: either he makes a statement about whether there are more ones than zeros or he makes a statement about the confidence interval. $\endgroup$
    – Jacob
    May 1 at 21:02
  • $\begingroup$ In any case, accurate confidence intervals for binomial distributions without normal approximation are quite complicated (see wikipedia "binomial proportion confidence interval"). But those are only neccessary if you want your $k$ to be provably as small as possible. If you are fine with $k$ being a little more than absolutely neccessary to reach $99%%$, then some approximation should really be fine. $\endgroup$
    – Simon
    May 1 at 21:24
  • $\begingroup$ I still think that there must be some other method how one could arrive at the desired solution. If I find it, I will post it as an answer $\endgroup$
    – Jacob
    May 1 at 23:10

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.