Re: Diehard's Overlapping Sum Test

From: Cristiano (cristiano.pi_at_NSquipo.it)
Date: 09/27/03 

Date: Sat, 27 Sep 2003 09:17:13 GMT

Ernst Lippe wrote:
> On Wed, 24 Sep 2003 11:28:30 +0000, George Marsaglia wrote:
>
>> Result: the final distribution, say F(u),
>> is not the uniform distribution on [0,1) (the line y=x).
>> It is close, but not close enough.
>> But if U is the result of converting
>> one of those X's to nearly uniform,
>> then F(U) will indeed be uniform.
>> Extensive simulation found F(u)
>> with precision adequate for including
>> the test in the Diehard battery.
>
> But this approach only works for one specific number of elements that
> are used in the sum (i.e. in the current implementation it is 100
> elements). So it is difficult to adapt the algorithm for a different
> number of elements.

It is not too difficult.
I seen that this test with 100 sums seems useless with any kind of generator
(it doesn't show any weakness). In other words, now the result is always
good with all the generators (even with a lcg which fails anything).
So I thought to try with 1000 or more sums, but the deviation from a normal
distribution is incredibly big (for the reason you said in the other post).
The only way I know to fix the distribution is to use several good
generators to calculate N 1000-number sums and then I calculate the
difference from the ideal distribution (a straight line from 0 to 1) and the
distribution gotten with the generator under test.

I'm still checking this method, but the "sensitivity" seems the same as 100
sums.

I also tried the non-overlapping sums, but I got nothing...

I have in mind that the difference between the overlapping sum and the
respective non-overlapping sum could leads to something. I'll check this
out.

> I believe that it is possible to find the exact analytical
> multi-variate distribution of the overlapping sums. So isn't it also
> possible to define exact tests that don't rely on simulations and
> that could also be used for other sizes?

I guess it is possible. Perhaps a good mathematician could helps us.

Cristiano

Relevant Pages

  • Re: Game Theory Nobel Prize Again and Beyond With PI
    ... mutations based on the Levy probability distribution," by Chang- ... the same distribution under sums goes to the "+" side of the ledger ... Readers who recall that the gamma distribution is ...
    (sci.stat.math)
  • Re: Distribution of measurements in Setterfields data
    ... follows a decay curve that he specifies. ... But does the distribution below match the one expected if the ... Distribution of sums and counts of c measurements and values, ...
    (talk.origins)
  • Distribution of measurements in Setterfields data
    ... follows a decay curve that he specifies. ... But does the distribution below match the one expected if the ... Distribution of sums and counts of c measurements and values, ...
    (talk.origins)
  • Re: Diehards Overlapping Sum Test
    ... I seen that this test with 100 sums seems useless with any kind of generator ... distribution is incredibly big. ... I have in mind that the difference between the overlapping sum and the ...
    (sci.crypt)
  • Re: Ramanujans Taxi, or a little torture test
    ... generate the sums that I don't understand. ... then a combination of your generator with a table like I used should ... whereas sorting n keys takes O ... M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html ...
    (comp.lang.forth)