1
$\begingroup$

Given a contest between two opponents where it is unknown who is favored, how many games must be plays to reach a given level of confidence in who is favored?

For example, Player A and Player B can play a game and determine a winner. There is a certain probability of Player A winning, which we would have a pretty good idea of if they played 1,000,000 games. They start playing. Player A wins three games and Player B wins one. The actual win % of Player A is 75%, but the game could easily be a coin flip and we're just seeing variance. How many games would take to have 90% confident that the overall win % approaches a single number?

$\endgroup$
0
$\begingroup$

The answer to this is really not quite suited to math stack exchange. In a nutshell, it's "go look up confidence intervals." This is an introduction to the topic.

$\endgroup$
0
$\begingroup$

Depends on what the actual win probability $p$ is.

Since your question is simply binary, a game with two outcomes, you can use the approach below.

A version of the Chernoff bound gives a useful estimate, assume $p\geq 1/2,$ then let $X_i=1$ if game $i$ is a win. Let $X=X_1+\cdots+X_n$ the number of wins in $n$ games, and let $\hat{p}=X/n,$ be the empirical win percentage. Then we have,e.g., $$ Pr[X>np+x]=Pr[\hat{p}>p+(x/n)]\leq \exp\left(-\frac{x^2}{2 n p(1-p)}\right) $$ where $\epsilon=x/n$ can be chosen. See the Wikipedia on Chernoff bounds for more details/versions of these bounds given what you know and whether the bound you want is additive or multiplicative, or even two sided. As $p$ approaches zero or one, convergence is even quicker, since the product $p(1-p)$ is approaches zero. Thus you can put in $p=1/2$ for a conservative approach.

$\endgroup$
  • $\begingroup$ Thank you! I don't understand yet but I will do some reading to learn more about Chernoff bounds. $\endgroup$ – Raine Revere Apr 7 '16 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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