Search code examples
algorithmprobability

Probabilistic algorithm

We are given a binary array that has either n zeros or floor(n/2) zeros and ceiling(n/2) ones.

We want to decide whether the array includes ones.

Q. Suggest a random algorithm that has time complexity O(1) and gives the correct answer with a probability of at least 3/4. The algorithm can give a wrong answer but not for more than 1/4 possible inputs.

I would like to get some direction on how to solve this question.

Solution

  • Check random item in the array:

    1. If item == 0 return first possibility (n zeroes)
    2. If item == 1 return second possibility (n/2 zeroes and n/2 ones)

    Let's have a look what's going on: the only possibility to give incorrect answer is when we have second possibility, but we get item == 0 and answer is first possibility. The conditional (second possibility) probability is

    p = 1/2

    If we check two random items

    p = 1/4 (two items are zeroes)

    If we check three random items

    p = 1/8 (three items are zeroes)

    Now, let's compute bayesian probability of incorrect answer, let

    P0 - probability of the 1st (all zeroes) outcome
P1 - probability of the 2nd (half zeroes, half ones) outcome

Perror = P1 * p / (P0 + P1) <= 1/4

    Or

    P1 * p / (P0 + P1) <= 1/4

p <= (P0 + P1) / 4 / P1

p <= P0 / (4 * P1) + 1/4

    From the worst case, P0 = 0 (P1 = 1) we get condition for p:

    p <= 1/4

    So far so good, we should check two random array's items and then

    • If both items are 0, we answer "All zeroes case"
    • If any item is 1, we answer "Half zeroes, half ones case"