Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# DM-Probability -Q19

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

A certain randomized algorithm A is intended to determine whether a given positive-integer input n is prime by generating a random bit string r and, based on the values of n and r, by outputting either Yes (indicating that n is prime) or No (indicating that n is composite). Execution of algorithm A guarantees the following.

(i) If n is prime, then the output of A is always Yes.

(ii) If n is composite, then there is a probability $\dpi{100} p > 0$ such that the output of A is No with probability p and is Yes with probability 1 - p.

On an input m, algorithm A is executed k times $\dpi{100} (k > 0)$ and generates a random string $\dpi{100} r_i$ on the $\dpi{100} i^{th}$ execution, $\dpi{100} 1 \leq i \leq k$ , where $\dpi{100} r_1, r_2, . . . , r_k$ are mutually independent.

Consider the following statements :

1. If m is composite, $\dpi{100} 1-p^k$  is the probability that in each of the k different executions the output of A is Yes.

2. If m is composite, $\dpi{100} (1-p)^k$  is the probability that in each of the k different executions the output of A is Yes.

3.  Suppose that in each of the k different executions the output of A is No. then  the probability that m is composite is $\dpi{100} p^k$.

4. Suppose that in each of the k different executions the output of A is No. then  the probability that m is composite is $\dpi{100} 1-(1-p)^k$.

Which of the above statements is/are correct ?

(A). Only 1 and 3

(B). Only 1 and 4

(C). Only  2 and 4

(D). Only 2

asked Jul 7, 2020
reshown Jul 10, 2020

NOTE this :

Execution of algorithm A guarantees the following.

(i) If n is prime, then the output of A is always Yes.

(ii) If n is composite, then there is a probability $\dpi{100} p > 0$ such that the output of A is No with probability p and is Yes with probability 1 - p.

So, If n is prime, then you will DEFINITELY get a YES in the first attempt itself. And that means that if You are getting NO in first attempt then it means n is NOT prime and hence n is composite.

So, now we can answer that "Suppose that in each of the k different executions the output of A is No. then what is  the probability that m is composite"..  Answer will be 1 because  if You are getting NO in first attempt then it means n is NOT prime and hence n is composite. So, by seeing NO in the first attempt you can guarrantee that n is Composite with full certaintly i.e. probability 1. So statement 3,4 are False.

If m is composite, what  is the probability that in each of the k different executions the output of A is Yes ??

This is just simple because we are given that "If n is composite, then there is a probability $\dpi{100} p > 0$ such that the output of A is No with probability p and is Yes with probability 1 - p. "

So,  If m is composite, $\dpi{100} (1-p)^k$  is the probability that in each of the k different executions the output of A is Yes.

So, statement 2 is Correct. Statement 1 is false.