0
$\begingroup$

I wrote a test case that tests if the javascript pseudo-random number generation algorithm of a given implementation has a given number of significant bits.

You can see and test my code here: https://jsfiddle.net/b93ev14g/1/

Now my question remaining is what statistical significance my test has.

My test does the following: It generates a given (e.g. 1000) number of pseudo random numbers with the built in algorithmn (e.g. xorshift128+).

  • If it finds any broken (floating) number, e.g. 10.5 it knows that the bits used by the algorithm are more than the number of bits the test was run for.
  • If it doesn't find any odd number after the given amount of iterations it is likely that the algorithm uses less bits than the test was run with.

So my question are

  1. how big is the probability that the test will find a floating number (if the algorithm generates any) after n iterations?
  2. how big is the probability that the test will find a broken number (if the algorithm generates any)?

Do the probabilities depend on the actual number of bits that the prng generates and the number of bits that the test runs for?

How can I calculate the significance that the test has to pass valid if the pseudo random number generated generates statistically uniform distributed numbers with given number of iterations and a given number of bits against which the test is run?

Thank you!

$\endgroup$
0
$\begingroup$

ok, so I just realized it's not that hard, actually quite easy:

It's a classical case of hypothesis testing. You actually want to calculate the probability of a type II error to occur.

I expect the probability of any significant bit to be set or unset to be $\frac {1} {2}$.

So for $n$ iterations this means if the actual number of bits of the prng-function is k bits away from the tested number of bits and all tests pass valid, then the probabilty for this to happen on coincident is:

$p(x) = \binom {n} {n} {\frac {1} {2}}^{k \cdot n} = {\frac {1} {2}} ^ {k \cdot n} $

That's true for point (1) and for point (2).

Since the number of tested bits can only either be too low or too high of course if (1) happend to pass valid on accident then the probability that (2) would pass on accident is $0$ and the other way around.

So the probability for the test to pass on accident actually decreases exponentially in regard to the distance of bits and exponentially in regards to the number of iterations.

Apart from that it is of course possible to decrease the probability of the test to pass on accident to $0\%$ by finding a single example of the test to fail with with number of $bits$ the function is tested against chosen to result in $k = 1$ on either side of the range.

$\endgroup$
  • $\begingroup$ This is basically the full story, except for the fact that the "random" numbers are not actually random. Depending on the RNG used, there might be some more-or-less visible patterns that could be observed. The non-random patterns I'm aware of, however, actually improve your test by reducing the probability to have $n$ consecutive "valid" tests. (Some of the older RNGs, for example, repeated the last few bits periodically, so as long as $n$ was reasonably large you were guaranteed to observe at least one number with the "last" bit set to $1$.) $\endgroup$ – David K Mar 5 '16 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.