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 Japanesefood." Then if s ? S is a classmate, he/she either likes Japanesefood (so s has property P) or does not (so s does not have propertyP). Suppose Pr(s has property P) = p for a uniformly chosen s ? S.Suppose Ofer the Oracle has magic powers that allow him to checkproperty P for any s, but it doesn’t always work since each time herelies on some (independently) generated random numbers to helphim. If he says “Yes,” then s has the property. If s has theproperty, then he says “Yes” with probability at least q.
Suppose we let Ofer check property P on an element s a total ofN 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 propertyP). Suppose p = 99/100 and q = 1/2, how many times should you letOfer check probability P before you are 99% confident that s doesnot have property P?
