• Register
    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 580

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
  • Questions
    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 580
  • Unanswered
    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 580
  • Tags
    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 580
  • Categories
    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 580
  • Users
    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 580
  • Exams Taken
    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 580
  • Exam List
    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 580

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

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

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

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

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

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
+2 votes

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 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 (k > 0) and generates a random string r_i on the i^{th} execution, 1 \leq i \leq k , where r_1, r_2, . . . , r_k are mutually independent. 

Consider the following statements :

1. If m is composite, 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, (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 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 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 by gbeditor-2 (72,840 points)
reshown Jul 10, 2020 by gbeditor-2

1 Answer

0 votes
 
Best answer

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 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 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, (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.

Answer D.

answered Aug 22, 2020 by deepak-gatebook (226,240 points)
Answer:

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

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

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
...