TalkChess.com

Here is a simple plain python script for computing passing probabilities and average running times for SPRT tests

http://hardy.uhasselt.be/Toga/sprta.py

This is of course much faster than simulation and moreover no compilation is necessary.

The script is based on well known easy analytical formulas which can for example be found in this book

http://www.amazon.com/Sequential-Analys ... l+analysis

Example:

$ python sprta.py
Usage: sprta.py elo0 elo1 draw_elo elo
elo0,elo1 are expressed in BayesElo
elo is expressed in LogisticElo

$ python sprta.py 0 4 250 -2
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= -2.0
pass probability: 0.05%
avg running time: 16951

$ python sprta.py 0 4 250 0
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 0.0
pass probability: 5.00%
avg running time: 39909

$ python sprta.py 0 4 250 2
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 2.0
pass probability: 85.89%
avg running time: 51884

$ python sprta.py 0 4 250 4
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 4.0
pass probability: 99.86%
avg running time: 19854

$ python sprta.py 0 4 250 6
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 6.0
pass probability: 100.00%
avg running time: 11545

Michel wrote:The question of computing passing probabilities for SPRT tests often comes up and people then resort to simulation. Alternatively one could use my script

http://hardy.uhasselt.be/Toga/wald.py

However this script does much more and is therefore rather complicated. Moreover it depends on scipy which is a very large and heavy python package.

Therefore I extracted from wald.py a simple plain python script

http://hardy.uhasselt.be/Toga/sprta.py

that computes passing probabilities and average running times. It has no external dependencies. For instructions on how to use sprta.py I include a copy of the post I made on the SF forum.

Here is a simple plain python script for computing passing probabilities and average running times for SPRT tests

http://hardy.uhasselt.be/Toga/sprta.py

This is of course much faster than simulation and moreover no compilation is necessary.

The script is based on well known easy analytical formulas which can for example be found in this book

http://www.amazon.com/Sequential-Analys ... l+analysis

Example:

$ python sprta.py
Usage: sprta.py elo0 elo1 draw_elo elo
elo0,elo1 are expressed in BayesElo
elo is expressed in LogisticElo

$ python sprta.py 0 4 250 -2
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= -2.0
pass probability: 0.05%
avg running time: 16951

$ python sprta.py 0 4 250 0
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 0.0
pass probability: 5.00%
avg running time: 39909

$ python sprta.py 0 4 250 2
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 2.0
pass probability: 85.89%
avg running time: 51884

$ python sprta.py 0 4 250 4
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 4.0
pass probability: 99.86%
avg running time: 19854

$ python sprta.py 0 4 250 6
elo0= 0.0
elo1= 4.0
draw_elo= 250.0
elo= 6.0
pass probability: 100.00%
avg running time: 11545

Laskos wrote: Can you make the script also output the LOS value for results of the matches at SPRT stop? The asymptotic value of LOS is (1 + erf[{wins - losses}/sqrt{2*(wins+losses)}] ) / 2, and is O(1) computation. The exact LOS is a sum over binomials, a O(N^2) computation, but asymptotically (N->infinity) they are the same. The reason I would like to see LOS is that I observed the typical LOS values for alpha, beta = 0.05, usually the SPRT stop occurs at LOS of 0.990-0.995. Although Type I error is theoretically unbounded for LOS or p-value as stopping rule, practically, say in the range N=100 games to 100,000 games, Type I error can be kept to 2-5% for LOS=0.999 or such.

lucasart wrote:

Laskos wrote: Can you make the script also output the LOS value for results of the matches at SPRT stop? The asymptotic value of LOS is (1 + erf[{wins - losses}/sqrt{2*(wins+losses)}] ) / 2, and is O(1) computation. The exact LOS is a sum over binomials, a O(N^2) computation, but asymptotically (N->infinity) they are the same. The reason I would like to see LOS is that I observed the typical LOS values for alpha, beta = 0.05, usually the SPRT stop occurs at LOS of 0.990-0.995. Although Type I error is theoretically unbounded for LOS or p-value as stopping rule, practically, say in the range N=100 games to 100,000 games, Type I error can be kept to 2-5% for LOS=0.999 or such.

You need to understand the hypothesis that lie behind the formula you're using. The "LOS" (actually p-value) is biaised at the SPRT stopping point. The only way your formula is correct, is when you run a fixed number of games decided in advance: (X1...Xn) need to be n random variable, independant and identically distributed, where n is not random (and especially not a function of the X(t) process).

Of course, the biais converges to zero as the stopping time goes to infinity. But still, it's biaised, especially when stopping happens early. That's why we don't print the p-value of an SPRT test.

Laskos wrote:

lucasart wrote:

Laskos wrote: Can you make the script also output the LOS value for results of the matches at SPRT stop? The asymptotic value of LOS is (1 + erf[{wins - losses}/sqrt{2*(wins+losses)}] ) / 2, and is O(1) computation. The exact LOS is a sum over binomials, a O(N^2) computation, but asymptotically (N->infinity) they are the same. The reason I would like to see LOS is that I observed the typical LOS values for alpha, beta = 0.05, usually the SPRT stop occurs at LOS of 0.990-0.995. Although Type I error is theoretically unbounded for LOS or p-value as stopping rule, practically, say in the range N=100 games to 100,000 games, Type I error can be kept to 2-5% for LOS=0.999 or such.

You need to understand the hypothesis that lie behind the formula you're using. The "LOS" (actually p-value) is biaised at the SPRT stopping point. The only way your formula is correct, is when you run a fixed number of games decided in advance: (X1...Xn) need to be n random variable, independant and identically distributed, where n is not random (and especially not a function of the X(t) process).

Of course, the biais converges to zero as the stopping time goes to infinity. But still, it's biaised, especially when stopping happens early. That's why we don't print the p-value of an SPRT test.

If LOS stop rule is "I stop as soon as I get LOS 0.999 for the first time", then the bias is included in the Type I error derived by simulations. As for p-value given by above formula, it converges to LOS for large number of games for fixed number of games.

D = (wins - losses) / sqrt(2 * (wins + losses))

LOS(frequentist) = (1 + erf(D)) / 2

p-value = 1 - erf(abs(D))

LOS(Bayesian) = (1/2 * binomial(wins+losses, wins) + sum[i, 0, wins-1] binomial(wins+losses, i)) / 2^(wins+losses)