Let S be a set and P be a property of the elements of the set,...

 

Transcribed Image Text:

Let S be a set and P be a property of the elements of the set, such that each element either has property P or not. For example, maybe S is the set of your classmates, and P is "likes Japanese food." Then if s E S is a classmate, he/she either likes Japanese food (so s has property P) or does not (so s does not have property P). Suppose Pr(s has property P) = p for a uniformly chosen s ES. Suppose Ofer the Oracle has magic powers that allow him to check property P for any s, but it doesn't always work since each time he relies on some (independently) generated random numbers to help him. If he says "Yes," then s has the property. If s has the property, then he says "Yes" with probability at least q. Suppose we let Offer check property P on an element s a total of N times, and he responded “No" each time. Find a lower bound (i.e. a smaller number, but a useful one) for Pr(s does not have property P). Suppose p = 99/100 and q = 1/2, how many times should you let Offer check probability P before you are 99% confident that s does not have property P? Let S be a set and P be a property of the elements of the set, such that each element either has property P or not. For example, maybe S is the set of your classmates, and P is "likes Japanese food." Then if s E S is a classmate, he/she either likes Japanese food (so s has property P) or does not (so s does not have property P). Suppose Pr(s has property P) = p for a uniformly chosen s ES. Suppose Ofer the Oracle has magic powers that allow him to check property P for any s, but it doesn't always work since each time he relies on some (independently) generated random numbers to help him. If he says "Yes," then s has the property. If s has the property, then he says "Yes" with probability at least q. Suppose we let Offer check property P on an element s a total of N times, and he responded “No" each time. Find a lower bound (i.e. a smaller number, but a useful one) for Pr(s does not have property P). Suppose p = 99/100 and q = 1/2, how many times should you let Offer check probability P before you are 99% confident that s does not have property P?

Answer rating: 100% (QA)

Ansuer let s e a sat p ba property ob the elements and of set Such that sach sleme... View the full answer