2
$\begingroup$

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 rate is not close to 50% but 60±5%, would that change the answer?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – BruceET
    Commented Nov 10, 2018 at 23:01
  • $\begingroup$ 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? $\endgroup$
    – Cohensius
    Commented Nov 10, 2018 at 23:20
  • 1
    $\begingroup$ That sounds right. $\endgroup$
    – BruceET
    Commented Nov 10, 2018 at 23:30

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.