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?

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?

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> 18,444 $

This means that in order to estimate the win proportion with error smaller than 1%, 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?

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?