> > I see only SEE there

>

> For binary contexts p(SSE)=1-p(SEE)

I know, but my texteditors search function doesn't .

> > And what I am interested in, is "stateless" counters, ie, ideally,

> > a way to dynamically compute a good enough estimation directly from

> > the context history. Alas, its not as simple as it seems, because

> > with short histories (eg 16 bits is short) the prediction of normal

> > counter is usually much better, and non-lookup implementations are damn slow.

>

> Formula must be tabulated, of course.

Well, not that is "must be", actually... its all just the matter

of speed impact on the optimizer.

But still I'd like to find some counter decomposition/approximation

which would be precise enough and much faster than recurrent update.

> > Well, there's a working coder without much redundancy, so I don't

> > care if you think its incorrent.

>

> Redundancy can be reduced with proper formula. I heard, You are concerned for

> precise models, are not You?

Certainly not "You"

Also that's not a proper formula for nonstationary data, so I wouldn't

really use it even if it was ideal for stationary data, what it isn't.

> > Btw, its also only good for large numbers, so I don't think there's

> > actually any difference... but thanks anyway, as I haven't heard about

> > this particular implementation. Guess I'd appreciate any links or articles

> > if you have any.

>

> AFAIR, it is by Shtarkov and it is not approximation, but precise formula.

Why don't you just look at that wikipedia page?

Also afair Shtarkov really liked the Stirling formula even back then, when

I'd seen some articles of his. It allows to turn a simple binomial formula

into a scary half-page monster, so I kinda understand why, though

Code:

n! ~= Sqrt(2*Pi*n)*n^n/Exp(n)
C(x+y,x) = (x+y)!/x!/y!
= Sqrt(2*Pi*(x+y))*(x+y)^(x+y)/Exp(x+y) / ( Sqrt(2*Pi*x)*x^x/Exp(x) * Sqrt(2*Pi*y)*y^y/Exp(y) )
= (x+y)^(x+y+,5) / x^(x+.5) / y^(y+.5) / Sqrt(2*Pi)

Also about that formula for probability:

Code:

C(x+y,x) - number of bit strings with x zeros and y ones.
p1 = C(x+1+y,x+1) / (C(x+1+y,x) + C(x+1+y,x+1))
= (x+1+y)^(x+1+y+,5) / (x+1)^(x+1.5) / y^(y+.5) /
( (x+1+y)^(x+1+y+,5) / (x+1)^(x+1.5) / y^(y+.5) +
(x+1+y)^(x+1+y+,5) / x^(x+.5) / (y+1)^(y+1.5) )
= x^(x+.5) * (y+1)^(y+1.5) / ( x^(x+.5) * (y+1)^(y+1.5) + (x+1)^(x+1.5) * y^(y+.5) )

Doesn't that look similar now? Guess that .5 was removed for ugliness, though

And finally:

Code:

p1 = C(x+1+y,x+1) / (C(x+1+y,x) + C(x+1+y,x+1))
= (x+1+y)!/(x+1)!/y! / ( (x+1+y)!/x!/(y+1)! + (x+1+y)!/(x+1)!/y! )
= x!*(y+1)! / ( (x+1)!*y! + x!*(y+1)! ) =
= x!*y!*(y+1) / ( x!*y!*(x+1) + x!*y!*(y+1) ) =
= y+1 / (x+y+2)