2

An agency is holding a poll, where each participant can either support or not support some upcoming motion. We model the answers with i.i.d. Bernoulli variables for which $X = 1$ means to support the motion with probability $P(X = 1) = p$. We'd like that results of a poll are within $a$ percentage points of the true fraction with $b$ probability and we are trying to determine what number of people we need to interview in order for this poll to be reliable.

We know that we are dealing with a binomial distribution and thus $E(X) = pn$. With Chernoff bounds we get $P(X \geq (1 - d)E(X)) \leq e^{-(E(X)d^2)/2}$ and $P(X \geq (1 + d)E(X)) \leq e^{-(E(X)d^2)/(2 + d)}$

So if we set $p = \frac{m}{n}$, where $n$ denotes the total number of participants and $m$ denotes the number of participants who support the motion, we have that $E(X) = pn = m$. Therefore to me this question sounds like finding $m$ for which $P((1-d)E(X) \leq X \leq (1+d)E(X)) = 0.99$. This ends up being equivalent of $0.01 = P(X \geq (1+d)E(X)) + P(X \geq (1-d)E(X))$. However if I use the Chernoff bounds and expand this equation I end up in a situation where $0.01 = e^{-(E(X)d^2)/2} + e^{-(E(X)d^2)/(2 + d)}$ and I have no idea how to factor out the $E(X)$.

So is my reasoning correct and/or is there a less painful way of solving for $E(X)$?

Epsilon Away
  • 954

1 Answers1

0

The standard way of thinking about this is to make the simplifying assumption that you are taking iid samples from a Bernoulli distribution $X_i \sim B(\theta)$.

If you are willing to go with this assumption, then we have that the sum of your samples is distributed as a binomial, as you point out.

We can then use a Bayesian update to compute a credence interval $[a, b]$ that is for example 90% likely to contain the true value of $\theta$.

For this, we will first compute the posterior distribution for the mean:

$$ p(\theta | x_1,...,x_n) = p(\theta) \frac{p(x_1,...,x_n | \theta)}{p(x_1,...,x_n)} $$

We need to select a prior probability - there are many reasonable choices but for sake of simplicity we will pick a uniform prior $p(\theta) = 1$.

The likelihood $p(x_1,...,x_n | \theta)$ is just the pdf of a binomial.

The factor $p(x_1,...,x_n)$ is just a normalization constant that we can compute as $p(x_1,...,x_n) = \int_0^1 p(\theta) p(x_1,...,x_n | \theta) d\theta$.

If we were to do the calculations, we would find that the posterior is distributed as a beta distribution $\beta (1 + \sum x_i, 1 + n - \sum x_i)$. We can use the quantiles 5% and 95% of this distribution as our 90% credence interval for $\theta$. Let us denote this posterior quantiles as $Q_{5\%}$ and $Q_{95\%}$.

The question is now: What should be the sample size so that the length of the credence interval $L = Q_{95\%} - Q_{5\%}$ is within a threshold $l_T$?

To simplify the calculation, the variance of the beta distribution is $Var(\theta | X_1,...,X_n) = \frac{(1 + \sum x_i) (1 + n - \sum x_i)}{(n+2)^2 (n+3)}$ which is maximized when $\sum x_i = n - \sum x_i$.

Hence for a fixed $n$ the 90% credence interval $l_T$ will be maximal when $\sum x_i = n/2$.

We can now use this to compute the $n$ that is guaranteed to bound the credence interval below whatever threshold we choose, eg

from scipy.stats import beta
import math
n = 0
L = math.inf
L_T = 0.05
alpha = 0.9
while L > L_T:
  n += 1
  I = beta(1 + n/2, 1 + n/2).interval(alpha)
  L = I[1] - I[0]

print(f"The sample size {n} guarantees a {alpha} credence interval smaller than {L_T}")

The program above outputs

The sample size 1080 guarantees a 0.9 credence interval smaller than 0.05
Jsevillamol
  • 4,668