Question

When doing polling, for instance to figure out how popular a given candidate is, a common trick is to just ask N many people whether they support that candidate, and take the support to be the faction of people who say yes: if 70 people support the candidate out of 100 asked, we estimate the support at 70% or 0.7. Suppose that the probability a person supports a candidate is p, which you do not know. Let pˆN be the fraction of N people polled who support the candidate: total supporters divided by N people polled.

1) What is the distribution of N * pN? (2 points)

2) Show that the expected value of pN is p, i.e., pN is a valid estimator for p. (3 points)

3) How many people N should you poll to guarantee the expected squared error on pN is less than epsilon? (5 points)

4) How many people N should you poll to guarantee the expected squared error on pN is less than epsilon, even if you don't know p? (5 points)

5) How many people N should you poll to guarantee the actual error on pN is less than  epsilon with 95% confidence, even if you don't know p? (5 points)

7) What is the relationship between q and p? (3 points)

8) Construct an estimator qN from pN (i.e., a formula for qN in terms of pN) so that the expected value E[qN] = q. What is the variance of qN? (4 points)

9) How many people N should you poll to guarantee the actual error between qN and q is less than , with 90% confidence? Note, q is unknown, so you cannot use it to determine N. (8 points)

10) Build a set of estimators qN1, qN2,..., qNM from pN1, pN2,..., pNM , so that E[qNi]=qi for each i. (7 points)

11) What is the total expected squared error of the q-estimators? i.e., what is E[i=1M(qNi-qi)2] ?(8 points)

Bonus (15 points MAX): Security researchers frequently would like to know the probability people pick things for their 4-digit PINs (how often do people lock their phones with just 1234?). If you just ask people what PIN they use, they either will not tell you or will lie. People may not even want to use something like the strategy in this problem, because there's some probability that they may be asked to just give their PIN honestly. How could you build a polling strategy that could successfully estimate the probabilities people use various PINs with, but wouldn't require the person to ever give up their PIN entirely and clearly?

(Please answer all questions)

Answer 1