The SPRT without draw model, elo model or whatever...

[nionita]

Hi Michel,

I don't understand much from those statistic methods, but just looking at your last code there is something strange, maybe there is a typo or maybe you must really explain for some novice like me.

I'm looking at your function TrivialLLR below, and specifically at the comment and conditions that none of L,D,W can be zero:

Code: Select all

from __future__ import division

...
def TrivialLLR(W,D,L,elo0,elo1):
    """ 
This function computes the log likelihood ratio of H0:elo=elo1 versus
H1:elo=elo1 under the trinomial (w/d/l) logistic model. W/D/L are
respectively the Win/Draw/Loss count.

For details see

http://hardy.uhasselt.be/Toga/GSPRT_approximation.pdf
"""
# to avoid division by zero
    if W==0 or D==0 or  L==0:
        return 0.0
    N=W+D+L
    w,d,l=W/N,D/N,L/N
    s=w+d/2
    m2=w+d/4
    var=m2-s**2
    var_s=var/N
    s0=LL(elo0)
    s1=LL(elo1)
    return (s1-s0)*(2*s-s0-s1)/var_s/2.0

You say: "to avoid division by zero", but the condition seems too strong to me, as this would not happen when for example W=1, D=1 and L=0, in which case we get var_s=-1.

On the other side, and this is more important to me, if we have W=0, D=1 and L=1 then we get var_s=0 and then a division by 0 (in the return of the function).

But for my intuition, the 2 cases are symmetric. For an ELO difference model I would not expect to see this different behaviour of the formula with respect to a division by 0.

[Michel]

You say: "to avoid division by zero", but the condition seems too strong to me, as this would not happen when for example W=1, D=1 and L=0, in which case we get var_s=-1.

You are right of course . The "correct" condition is that at least two among three of W,D,L are non-zero. However I did not immediately see a compact way to write this in Python so for simplicity I required all three of W,D,L are non-zero.

In practice this makes no difference whatsoever as after a few games the stronger condition will become true. (Recall that the SPRT is made for small elo differences).

One compact way to write the correct condition is W*D+W*L+D*L!=0. This is mathematically pleasing but perhaps not so good from a programmer's standpoint as it involves 3 multiplications.

[Ajedrecista]

Hello Michel:

One compact way to write the correct condition is W*D+W*L+D*L!=0. This is mathematically pleasing but perhaps not so good from a programmer's standpoint as it involves 3 multiplications.

Karnaugh map gives exactly the same function of W*D + W*L + D*L. I suggest other option without multiplications (at least obvious multiplications) but it can be computionally expensive: what about the condition sign(W) + sign(D) + sign(L) < 2?

In any case: w + d/4 - (w + d/2)² =/= 0.

Code: Select all

This function computes the log likelihood ratio of H0:elo=elo1 versus H1:elo=elo1 under the trinomial (w/d/l) logistic model.

Shouldn't H0 and H1 be different? I guess it is a minor typo that does not blur your good work.

Regards from Spain.

Ajedrecista.

[Ajedrecista]

Hello again:

I want to add something. From Michel's code:

Code: Select all

# to avoid division by zero 
    if W==0 or D==0 or  L==0: 
        return 0.0 
    N=W+D+L 
    w,d,l=W/N,D/N,L/N 
    s=w+d/2 
    m2=w+d/4 
    var=m2-s**2 
    var_s=var/N 
    s0=LL(elo0) 
    s1=LL(elo1) 
    return (s1-s0)*(2*s-s0-s1)/var_s/2.0

Code: Select all

Let's suppose that the initial 'if' statement is not satisfied:
&#40;0 < w < 1&#41; AND &#40;0 < d < 1&#41; AND &#40;0 < l < 1&#41;

m2 = s - d/4
var = m2 - s² = s - d/4 - s² = var&#40;s&#41; = N*var_s

Singular points of var = var&#40;s&#41; = 0
s² - s + d/4 = 0
s = &#91;1 ± sqrt&#40;1 - d&#41;&#93;/2

|s - 1/2| = &#40;1/2&#41;*sqrt&#40;1 - d&#41;
|2s - 1|² = 1 - d

What about {w, d, l} combinations that fit in |s - 1/2| = (1/2)*sqrt(1 - d)? Is it possible? No!

Code: Select all

d(var = 0) = 1 - |2s - 1|²
(Always): d_max. = 2*min.(s, 1 - s) = d_max.(s)

Drawing both functions, they only share three (s, d) points: (0, 0); (1/2, 1); (1, 0)
These three points imply, respectively: W = D = 0; W = L = 0; D = L = 0
The initial 'if' statement is satisfied in those cases.
In the rest of cases of 0 < s < 1 &#40;except s = 1/2, as seen above&#41;&#58;
d&#40;var = 0&#41; > d_max., which is impossible.

Regards from Spain.

Ajedrecista.

[Michel]

sign(W) + sign(D) + sign(L) < 2?

Yes that's nice! I do not really understand your other comment. Are you confirming my (easy) claim that if W<>0 and D<>0 and L<>0 then (empiric) var <> 0 ?

Note that the results about the GSPRT are asymptotic so it does not really matter how the computation is regularized for small N.

This function computes the log likelihood ratio of H0:elo=elo1 versus H1:elo=elo1 under the trinomial (w/d/l) logistic model.

Ah yes sorry for the typo in this comment. I hope it was clear what I meant.

[Ajedrecista]

Hello Michel:

Are you confirming my (easy) claim that if W<>0 and D<>0 and L<>0 then (empiric) var <> 0 ?

That's it. In fact, I was trying to provide numeric examples of the opposite, negating your claim, but an unexpected problem arose: when I randomly chose a value for score = s and a (draw ratio) = d, then calculating the (win ratio) = w was easy, but I faced the unpleasant situation (lose ratio) = l = 1 - w - d < 0; after two or three trials, I realised that the problem could be an incompatible condition of (s, d), as it was.

The maximum draw ratio [d_max. = 2min.(s, 1 - s)] is a triangular function with three (s, d) vertex in the domain 0 < s < 1: (0, 0); (1/2, 1); (1, 0). OTOH, the condition d(var = 0) = 1 - |2s - 1|² is a parabolic function with its maximum at (s, d) = (1/2, 1) and therefore d(var = 0) > d_max., which is impossible.

Regards from Spain.

Ajedrecista.

[Michel]

That's it. In fact, I was trying to provide numeric examples of the opposite, negating your claim,

Ok I see.

Since Var(X)=E((X-EX)^2) it follows that if Var(X)=0 then X=EX with probability one. In other words X must take constant values (as events with probability zero do not occur).

So for a multionimal distribution to have variance zero all probabilities except one must be zero.

[Michel]

Bumping this old thread once again... I am just recording the following.

I have now verified that the following simple formula (discussed elsewhere)

Code: Select all

(1/2)*N*log(sum_i(xi-mu0)**2/sum_i(xi-mu1)**2)        (*)

gives a very accurate approximation of the LLR for mu=mu0 versus mu=mu1 where mu is the expectation value of a distribution. The sample is xi, i=1,.... The approximation seems to be much more generally valid than the one discussed in this thread (which requires fairly small elo differences).

The implementation is here

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

The theoretical basis for (*) is to replace the distribution by a normal one with parameters (mu,sigma). Then (*) computes the generalized LLR for mu0 versus mu1 for a normal distribution with sigma as a nuissance parameter. So rather than using Taylor series expansions, (*) is based on the central limit theorem which explains why it is more generally valid.

I have verified the properties of (*) by comparing it with the exact generalized LLR, which can only be computed numerically for the pentanomial model.

[Michel]

Here is a little document with the derivation of the approximation

http://hardy.uhasselt.be/Toga/computeLLR.pdf

The document also shows how to do the exact computation. It leads to an equation in one variable which can be trivially solved numerically.

[Isaac]

as events with probability zero do not occur

Can someone confirm or disprove this claim, please?