# Sample size for estimating success probability of a Bernoulli process

Suppose an AI player in a game can either win or lose. I wish to estimate the win ratio of this player. My question is, how many samples (games) needed in order to get an error smaller than 1%?

A friend explained me that Hoeffding inequality is the right approach, however in a similar question Sample size needed to estimate probability of “success” in Bernoulli trial the answer didn't mentioned Hoeffding inequality. I also found this Sample Size Calculator which might be the right tool for this problem however I could not understand how to use it.

Hoeffding inequality: Assume I want to know in 95% certainty that the win proportion is X ±1% than,

$$P(H(n) \leq k) = \sum_{i=0}^k {n\choose i} p^iq^{n-i}$$ For $$k=(p-\epsilon)n$$, $$P(H(n) \leq (p-\epsilon)n) \leq e^{-2\epsilon^2n}$$ $$P(H(n) \geq (p+\epsilon)n) \leq e^{-2\epsilon^2n}$$ Thus, $$(p-\epsilon)n \leq P(H(n) \leq (p+\epsilon)n) \geq 1-2e^{-2\epsilon^2n}$$ For $$\epsilon = 0.01$$ and $$95\%$$ certainty $$95\% \geq 1-2e^{-0.0002n}$$ which gives $$n\geq 18,444$$

This means that in order to estimate the win proportion with error smaller than 1%, in 95% of the times, 18444 samples are needed.

Is that right? Is Hoeffding inequality the best approach here? is it tight? Can some other bound / inequality give this certainty with less samples? If I know that the win ratio is 60±5% would that help?

• One approach is to note that a 95% CI for $p$ is of the form $\hat p \pm 1.96\sqrt{\frac{\hat p(1 - \hat p)}{n}},$ where $\hat p = X/n$ and $X$ is the number of wins in $n$ games. You want the margin of error $M = 1.96\sqrt{\frac{\hat p(1 - \hat p)}{n}} = 0.01.$ If you have a rough idea of the value of $p,$ then plug that value as $\hat p$ into the formula for $M$ and solve for $n.$ If you have no idea, then use $\hat p = 1/2,$ because that gives the largest size $n$, This formula is based on a normal approx, but if you want $M = .01,$ then your $n$ will be large enough to use norm aprx. – BruceET Nov 10 '18 at 23:01
• Let me see if I get it right, solving $1.96\sqrt{ \hat{p} (1-\hat{p}) /n } = 0.01$ gives $n = 9,604$ It means that in order to get 95% certainty that the win ratio is $\hat{p} \pm 1\%$ its enough to sample ~10000 games, not ~18500, as suggested by Hoeffding inequality? – Cohensius Nov 10 '18 at 23:20
• That sounds right. – BruceET Nov 10 '18 at 23:30

Let's simulate the experiment a million times in R. Suppose $$p = .4.$$ If we look at $$n = 10,000$$ games at each iteration, then what results do we get for $$\hat p?$$

n = 10^4; p = .4
p.hat = rbinom(10^6, 10^4, .4)/n
quantile(p.hat, c(.025, .975))
2.5%  97.5%
0.3904 0.4096
summary(p.hat)
Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
0.3742  0.3967  0.4000  0.4000  0.4033  0.4245


In 95% of cases, $$\hat p$$ was between 0.39 and 0.41, as required. The worst results in a million iterations were a minimum of 0.374 and a maximum of 0.425. Looking at the quartiles, we see that half of the $$\hat p$$'s were considerably closer than required --- between 0.397 and 0.403.