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

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 ∈ 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 ∈ S. 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 Ofer 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 Ofer check probability P before you are 99% confident that s does not have property P?

Solutions

Expert Solution

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 ∈ 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 ∈ S.
Suppose Offer 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,
let Offer check probability P before you are 99% confident that s does not have property P
sample size is number of times n

Compute Sample Size ( n ) = n=(Z/E)^2*p*(1-p)
Z a/2 at 0.01 is = 2.576
Sample Proportion = 0.5
ME = 0.99
n = ( 2.576 / 0.99 )^2 * 0.5*0.5
= 1.693 ~ 2

milcah answered 8 months ago

Next > < Previous

Related Solutions

Let A be a set with m elements and B a set of n elements, where...

Let A be a set with m elements and B a set of n elements, where m; n are positive integers. Find the number of one-to-one functions from A to B.

Let S = {a, b, c}. Draw a graph whose vertex set is P(S) and for...

Let S = {a, b, c}. Draw a graph whose vertex set is P(S) and for which the subsets A and B of S are adjacent if and only if A ⊂ B and |A| = |B| − 1. (a) How many vertices and edges does this graph have? (b) Can you name this graph? (c) Is this graph connected? (d) Does it have a perfect matching? If yes, draw a sketch of the matching. (e) Does it have a...

Let S ⊆ R be a nonempty compact set and p ∈ R. Prove that there...

Let S ⊆ R be a nonempty compact set and p ∈ R. Prove that there exists a point x_0 ∈ S which is “closest” to p. That is, prove that there exists x0 ∈ S such that |x_0 − p| is minimal.

Let S = {a, b, c, d} and P(S) its power set. Define the minus binary...

Let S = {a, b, c, d} and P(S) its power set. Define the minus binary operation by A − B = {x ∈ S | x ∈ A but x /∈ B}. Show that (by counter-examples) this binary operation is not associative, and it does not have identity

2. (a) Let p be a prime. Determine the number of elements of order p in...

2. (a) Let p be a prime. Determine the number of elements of order p in Zp^2 ⊕ Zp^2 . (b) Determine the number of subgroups of of Zp^2 ⊕ Zp^2 which are isomorphic to Zp^2 .

11.4 Let p be a prime. Let S = ℤ/p - {0} = {[1]p, [2]p, ....

11.4 Let p be a prime. Let S = ℤ/p - {0} = {[1]p, [2]p, . . . , [p-1]p}. Prove that for y ≠ 0, Ly restricts to a bijective map Ly|s : S → S. 11.5 Prove Fermat's Little Theorem

Let S be a set of n numbers. Let X be the set of all subsets...

Let S be a set of n numbers. Let X be the set of all subsets of S of size k, and let Y be the set of all ordered k-tuples (s1, s2, , sk) such that s1 < s2 < < sk. That is, X = {{s1, s2, , sk} | si S and all si's are distinct}, and Y = {(s1, s2, , sk) | si S and s1 < s2 < < sk}. (a) Define a one-to-one correspondence f : X → Y. Explain...

Let X be a set containing infinitely many elements, and let d be a metrio on...

Let X be a set containing infinitely many elements, and let d be a metrio on X. Prove that X contains an open set U such that U and its complement Uc = X\U are both infinite

7. Let n ∈ N with n > 1 and let P be the set of...

7. Let n ∈ N with n > 1 and let P be the set of polynomials with coefficients in R. (a) We define a relation, T, on P as follows: Let f, g ∈ P. Then we say f T g if f −g = c for some c ∈ R. Show that T is an equivalence relation on P. (b) Let R be the set of equivalence classes of P and let F : R → P be...

1. Let A be the set whose elements are the months of the year that begin...

1. Let A be the set whose elements are the months of the year that begin with the letter J. A = { } 2. Define a set that is empty. Let B be the set: _________________________________________________________________________ _________________________________________________________________________ 3. The following data was collected from a survey of 350 San Antonio residents Are you a Spurs fan? YES NO Male 204 19 Female 113 14 a. How many males were surveyed? b. How many spurs fans were surveyed? c. How...

Subjects