Randomized Algorithm

Question

I'm having trouble with a randomized problem. :)

A, a randomized algorithm, determines whether an input x is a prime number.

This algorithm works the following way:

1- If x is prime, then A outputs YES

2- If x is not prime, then A outputs NO with the probability 3/4.

At least how many times should we run A, if we want to have the algorithm A output NO with the probability at least 1- (1/k)?

Note: One NO answer implies that a given input x is not prime.

Any idea?

Answer 1

If a number x is not a prime, the probability to yield 'yes' in n repeats of the algorithm is (1/4)^n = 4^(-n) = 2^(-2n).

So, if you want to achieve 1-(1/k), you are actually looking for False Positive with probability of at most 1/k, and from the above we want:

2^(-2n) <= 1/k   //log_2 on both sides:
-2n <= log(1/k) = log(1)-log(k) = 0 - log(k)
2n >= log(k)
n >= log(k)/2

So you want to chose the smallest integer n possible such that n >= log(k)/2, to guarantee True Negative with probability of 1-1/k.

(Note: All log() are with base 2).

Example:
If you want to be correct 99% of the time, you actually are looking for 1-1/k=0.99, so 1/k=1/100 and k=100.

Now, according to the above formula, note that log_2(100) ~= 6.64, and thus the smallest n such that n >= log_2(100)/2 is n==4.
Meaning, you need to repeat the algorithm 4 times to achieve 99%.

Let's check this is correct:

1. First check that the probability is indeed greater than 99%: 1-(1/4)^4 = 1-(1/256) ~= 0.996 >= 0.99, so the probability is fine.
2. Check that for a smaller integer (n==3), we would have got worse than 99% correct answer: 1-(1/4)^3 = 1-1/64 ~= 0.984 < 0.99 - so we would have failed for n==3.