Script for computing SPRT probabilities

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Michel
Posts: 2038
Joined: Sun Sep 28, 2008 11:50 pm

Script for computing SPRT probabilities

Post by Michel » Sun Apr 05, 2015 7:47 am

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
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Michel
Posts: 2038
Joined: Sun Sep 28, 2008 11:50 pm

Re: Script for computing SPRT probabilities

Post by Michel » Sun Apr 05, 2015 7:20 pm

For those that do not use python I did a quick line by line C-translation. The zip file

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

contains the python script, the C translation, a (static) Linux binary and a Windows binary.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

User avatar
Laskos
Posts: 9323
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Script for computing SPRT probabilities

Post by Laskos » Mon Apr 06, 2015 5:57 am

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
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.

User avatar
lucasart
Posts: 3036
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Script for computing SPRT probabilities

Post by lucasart » Mon Apr 06, 2015 11:06 am

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.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
Laskos
Posts: 9323
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Script for computing SPRT probabilities

Post by Laskos » Mon Apr 06, 2015 1:31 pm

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.

User avatar
Laskos
Posts: 9323
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Script for computing SPRT probabilities

Post by Laskos » Tue Apr 07, 2015 6:12 am

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.
By the way, your statement that frequentist inference LOS is actually p-value is not correct. Just computed the p-value for our problem, and it's only related to frequentist inference LOS.

If

Code: Select all

D = (wins - losses) / sqrt(2 * (wins + losses))
Then the asymptotic LOS is

Code: Select all

LOS(frequentist) = (1 + erf(D)) / 2
p-value is

Code: Select all

p-value = 1 - erf(abs(D))
And the exact Bayesian LOS is

Code: Select all

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

Post Reply