Problem 1 Chernoff bound – application 1

Consider a biased coin with probability p = 1∕3 of landing heads and probability 2∕3 of landing tails. Suppose the coin is flipped some number n of times, and let X_i be a random variable denoting the i^th flip, where X_i = 1 means heads, and X_i = 0 means tails. Use the Chernoff bound to determine a value for n so that the probability that more than half of the coin flips come out heads is less that 0.001.

Problem 2 Chernoff bound – application 2

At the Yale-Harvard hockey game on February 6, Yale made 50 shots on the Harvard goal and scored 5 times, whereas Harvard made 15 shots on the Yale goal and scored only once. Assume that both teams had equally good goalies and that for each team, the probability is p = 0.1 of a shot scoring a goal. Clearly, the expected number of goals is np, where n is the number of shots. For Yale, the actual number of goals g exactly matched the expectation, but for Harvard with 15 shots, the actual number of goals (1) fell considerably short of the expected number (1.5).

The purpose of this problem is to assess how unusual it is that Harvard scored fewer than the expected number of goals given the number of shots on the goal and the assumed success probability of each shot. In the following, let n = 15, g = 1, p = 0.1, and q = Pr[# goals after n shots ≤ g]. We wish to find a “good” upper bound on q.

1. Happy Hacker remembered about the Chernoff bound presented in lecture 1, so he decided to use it to bound q. What values should he use for the parameters ε, n, and p that appear in the formula on the right hand side of the bound? Using these values, compute the value b of the right hand side. What does b tell Happy about q that he didn’t already know?
2. Clever Clara knew right away that it was a waste of time to compute the Chernoff bound in this case and didn’t bother. How did Clara know that?
3. Stolid Sean didn’t see the need to think hard about this problem and instead just plunged in and computed q to 4 decimal places using standard probability theory. How could he do this, and what is the answer?

Problem 3 Derandomization

Let M be a ppTM that accepts a language L and runs in time p(n) for some polynomial p(⋅). Let x be an input string of length n and r a random choice string of length p(n) ≫ n. Let δ(x,r) = 1 if M(x,r), the output of M with coin toss sequence r, gives the correct answer about x’s membership in L, and let δ(x,r) = 0 otherwise. Suppose Pr[M(U_n,U_p(n)) is correct] = 1 - 2∕2ⁿ.

How large can we make the success probability of M(U_n,r) by setting the second input of M to a fixed string r? That is, what is the best lower bound on

that is implied by the given information, where max_r is taken over all binary strings of length p(n)?

[Note: This problem generalizes a fact used in the proof of Theorem 4, section 11, lecture notes 3.]

Problem 4 One-way functions and the -versus- question

[Textbook, Chapter 2, Exercise 3.]