Question

4. You have an algorithm A for testing whether a Boolean formula f is satisfiable or not, but it is only correct with probability 2/3. More precisely, you can repeatedly run A on the same formula f, and each time it outputs the correct answer with probability 2/3. To reduce the probability of error, you run A(f)n times, and return the majority answer. What should n be if you want the probability of error to be less than 0.05 ? Hint: Use Hoeffding's inequality: If X1​,…,Xn​ are independent random variables which have mean μ and take values in [0,1], then for any ϵ>0 : Pr(∣∣​nX1​+⋯+Xn​​−μ∣∣​≥ϵ)≤2e−2ϵ2n

Answer 1

To reduce the probability of error to less than 0.05, we can use Hoeffding's inequality. Setting ϵ = 0.05, we find that running algorithm A(f) 1584 times and returning the majority answer will achieve this.

Step-by-step explanation:

To reduce the probability of error to be less than 0.05, we can use Hoeffding's inequality which states that for any ϵ > 0, the probability of the sum of n independent random variables deviating from its mean by at least ϵ is less than 2e^(-2ϵ^2n).

In this case, the sum of the independent random variables is the number of correct answers obtained by running algorithm A on the same formula f multiple times. We want the probability of error to be less than 0.05, so we can set ϵ = 0.05.

Plugging the values into the inequality, we have:

Pr(|nX1 + X2 + ... + Xn - μ| ≥ ϵ) ≤ 2e^(-2ϵ^2n)

Pr(|nX1 + X2 + ... + Xn - nμ| ≥ ϵ) ≤ 2e^(-2ϵ^2n)

Pr(|X1 + X2 + ... + Xn - μ| ≥ ϵ/n) ≤ 2e^(-2ϵ^2n)

Here, μ is the expected number of correct answers, which is n * (2/3).

Now, we can solve the inequality to find the value of n:

Pr(|X1 + X2 + ... + Xn - μ| ≥ ϵ/n) ≤ 2e^(-2ϵ^2n)

Pr(|X1 + X2 + ... + Xn - n(2/3)| ≥ ϵ/n) ≤ 2e^(-2ϵ^2n)

Pr(|X1 + X2 + ... + Xn - (2/3)n| ≥ ϵ/n) ≤ 2e^(-2ϵ^2n)

We want the probability of error to be less than 0.05, so we can set it as an upper bound:

2e^(-2ϵ^2n) ≤ 0.05

e^(-2ϵ^2n) ≤ 0.025

-2ϵ^2n ≤ ln(0.025)

2ϵ^2n ≥ -ln(0.025)

n ≥ (-ln(0.025))/(2ϵ^2)

Substituting ϵ = 0.05, we get:

n ≥ (-ln(0.025))/(2(0.05)^2)

n ≥ 1584

Therefore, to reduce the probability of error to be less than 0.05, we should run algorithm A(f) 1584 times and return the majority answer.

Answer 2

To reduce the probability of error when using algorithm A, we can run it multiple times and return the majority answer. Using Hoeffding's inequality, the required number of repetitions, n, can be calculated to achieve a desired probability of error.

Step-by-step explanation:

To reduce the probability of error, we can run algorithm A(f) multiple times and return the majority answer. By using Hoeffding's inequality, we can calculate the value of n required to achieve a desired probability of error. Let's assume the probability of error is less than 0.05, which means we want the probability of the majority answer being incorrect to be less than 0.05. From Hoeffding's inequality, we have:

Pr(|n(X1 + ... + Xn) / n - μ| >= ϵ) <= 2e^(-2ϵ^2n)

Here, μ is the probability of the correct answer (2/3) and ϵ is the desired probability of error (0.05).

By substituting the values and solving for n, we can find the required number of repetitions:

Pr(|n(X1 + ... + Xn) / n - (2/3)| >= 0.05) <= 2e^(-2 * 0.05^2 * n)

0.05 <= 2e^(-2 * 0.05^2 * n)

ln(0.05/2) <= -2 * 0.05^2 * n

n >= ln(0.05/2) / (-2 * 0.05^2)

n >= ln(0.05/2) / (-2 * 0.05^2)

n >= ln(0.025) / (-2 * 0.05^2)

n >= 8.039

Therefore, the value of n should be 9 or greater in order to achieve a probability of error less than 0.05.