Inspired by the recent thread about pseudorandom number generators on python-ideas (where I also mistakenly first wrote this message), I began
to wonder: suppose that I had a pseudorandom number generator that
attempted to generate a nonuniform distribution. Suppose for instance
that it was to generate a 0 bit 2/3 of the time, and a 1 bit 1/3 of the
time.

How would one go about testing this PRNG against an idealized (similarly biased) PRNG?

- DLD

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

David Lowry-Duda <david@lowryduda.com> writes:

to wonder: suppose that I had a pseudorandom number generator that
attempted to generate a nonuniform distribution. Suppose for instance
that it was to generate a 0 bit 2/3 of the time, and a 1 bit 1/3 of the
time.
How would one go about testing this PRNG

Probability bears probability.

When you test a probabilistic system, you might only get
a probabilistic result, like "The system passes the test
with a probability of .95.".

For example, you want to test a real die with a limitation
of 100 throws. The die is expected to choose between 1, 2,
3, 4, 5, and 6 with equal probability (= hypothesis). When
it yields 100 1's, this does not refute the hypothesis because
a real die /can/ yield a sequence of 100 1's and still have
equal probabilities for all of the number 1, 2, 3, 4, 5, and 6.

So, in this case, careful code reviews might be better than
tests. For example, assuming, random.intrange( 0, 2 ) works
as advertised, we can be pretty sure that

0 if random.randint( 0, 2 ) else 1

fulfills the requirement.

|One of the oldest interpretations is the /limit frequency/
|interpretation. If the conditioning event /C/ can lead
|to either A or "not A", and if in /n/ repetitions of such
|a situation the event A occurs /m/ times, then it is asserted
|that P(A|C) = lim n-->oo (m/n). This provides not only
|an interpretation of probability, but also a definition
|of probability in terms of a numerical frequency ratio.
|Hence the axioms of abstract probability theory can
|be derived as theorems of the frequency theory.
|
|In spite of its superficial appeal, the limit frequency
|interpretation has been widely discarded, primarily because
|there is no assurance that the above limit really exists for
|the actual sequences of events to which one wishes to apply
|probability theory.
|
"Quantum Mechanics" (1998) - Leslie E. Ballentine

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

ram@zedat.fu-berlin.de (Stefan Ram) writes:

So, in this case, careful code reviews might be better than
tests. For example, assuming, random.intrange( 0, 2 ) works
as advertised, we can be pretty sure that
0 if random.randint( 0, 2 ) else 1
fulfills the requirement.

In practice, tests should still be done. When such a function
returns the same result a hundred times, it does make sense
to become suspicious and investigate it.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 07/12/2022 13:05, David Lowry-Duda wrote:

Inspired by the recent thread about pseudorandom number generators on python-ideas (where I also mistakenly first wrote this message), I began
to wonder: suppose that I had a pseudorandom number generator that
attempted to generate a nonuniform distribution. Suppose for instance
that it was to generate a 0 bit 2/3 of the time, and a 1 bit 1/3 of the
time.

How would one go about testing this PRNG against an idealized (similarly biased) PRNG?

I believe things go like this. If you have a uniform PRNG, you test it
against the state-of-the-art in statistical tests then build from it
your nonuniform one. Now you have a nonuniform one that's tested. But
you want things the other way around. Having a nonuniform one to start,
you build a uniform one from the nonuniform one and then test it against
the state-of-the-art in statistical tests.

I believe you might be wondering how to build one from the other, but
I'll let you check that.

By the way, there's no such thing as an idealized PRNG. All PRNG fail
all statistical tests. The question is when. A bad PRNG fails quickly
and obviously. A good one requires large samples or a nontrivial test.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 07/12/2022 13:45, Stefan Ram wrote:

[...]

|One of the oldest interpretations is the /limit frequency/
|interpretation. If the conditioning event /C/ can lead
|to either A or "not A", and if in /n/ repetitions of such
|a situation the event A occurs /m/ times, then it is asserted
|that P(A|C) = lim n-->oo (m/n). This provides not only
|an interpretation of probability, but also a definition
|of probability in terms of a numerical frequency ratio.
|Hence the axioms of abstract probability theory can
|be derived as theorems of the frequency theory.
|
|In spite of its superficial appeal, the limit frequency
|interpretation has been widely discarded, primarily because
|there is no assurance that the above limit really exists for
|the actual sequences of events to which one wishes to apply
|probability theory.
|
"Quantum Mechanics" (1998) - Leslie E. Ballentine

That's pretty interesting. Indeed, we really must discard this
frequency interpretation, even though it is what's in my mind when I
think of estimating the probability of a certain event, which I think
would be called the empirical distribution of probability?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 07/12/2022 14:04, Stefan Ram wrote:

ram@zedat.fu-berlin.de (Stefan Ram) writes:

So, in this case, careful code reviews might be better than
tests. For example, assuming, random.intrange( 0, 2 ) works
as advertised, we can be pretty sure that
0 if random.randint( 0, 2 ) else 1
fulfills the requirement.

In practice, tests should still be done. When such a function
returns the same result a hundred times, it does make sense
to become suspicious and investigate it.

Whatever it does a hundred times is not enough. Code review is
definitely not enough. The design of PRNGs should be good in theory --- designed with good mathematical foundations --- and in practice by
passing all tests in the best-designed batteries. As far as I know, the state-of-the-art in statistical tests against PRNGs is the TestU01
library, available at

http://simul.iro.umontreal.ca/testu01/tu01.html

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wed, Dec 07, 2022 at 03:28:47PM -0300, Sabrina Almodóvar wrote:

As far as I know, the state-of-the-art in statistical tests against
PRNGs is the TestU01 library, available at

http://simul.iro.umontreal.ca/testu01/tu01.html

I'm familiar with this type of test. But as far as I can tell and have
seen, these tests only tst against *uniform* PRNGs. I am not aware of
any written tests against nonuniform PRNGs.

I suspect it would be possible to mirror a lot of the ideas. For
example, one common PRNG statistical test is to make many of matrices of various sizes and to study the ranks of these matrices. Presumably one
could do a similar statistical analysis against what would be expected
for any particular probability distribution. Running a candidate PRNG
through this test will produce some sort of distribution, after all.

But it would be much nicer if work on statistical tests against
nonuniform PRNGs had already been done somewhere.

--
David Lowry-Duda <david@lowryduda.com> <davidlowryduda.com>

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 12/7/22 2:37 PM, David Lowry-Duda wrote:

On Wed, Dec 07, 2022 at 03:28:47PM -0300, Sabrina Almodóvar wrote:

As far as I know, the state-of-the-art in statistical tests against
PRNGs is the TestU01 library, available at

 http://simul.iro.umontreal.ca/testu01/tu01.html

I'm familiar with this type of test. But as far as I can tell and have
seen, these tests only tst against *uniform* PRNGs. I am not aware of
any written tests against nonuniform PRNGs.

I suspect it would be possible to mirror a lot of the ideas. For
example, one common PRNG statistical test is to make many of matrices
of various sizes and to study the ranks of these matrices. Presumably
one could do a similar statistical analysis against what would be
expected for any particular probability distribution. Running a
candidate PRNG through this test will produce some sort of
distribution, after all.

But it would be much nicer if work on statistical tests against
nonuniform PRNGs had already been done somewhere.

The big problem is there are MANY variations of nonuniform random
numbers, and all the variations lead to different statistics to test
against.

Most of the test can probably apply, but the new test criteria would
need to be computed based on computing the exected results and expected variation in that result, largely based on various cross correlations of
the numbers.

--
Richard Damon

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

One thing you could do is to apply von Neumann de-biasing to convert a
string of output bits from your biased PRNG to an unbiased string, and
test the de-biased output. If such tests pass I don't know that you
can be satisfied thaty your biased PRNG is close to a theorieical
biased random bit stream, but if they fail that should indicate a
problem.

Robert E. Beaudoin


On Wed, 7 Dec 2022 11:05:53 -0500
David Lowry-Duda <david@lowryduda.com> wrote:

Inspired by the recent thread about pseudorandom number generators on python-ideas (where I also mistakenly first wrote this message), I
began to wonder: suppose that I had a pseudorandom number generator
that attempted to generate a nonuniform distribution. Suppose for
instance that it was to generate a 0 bit 2/3 of the time, and a 1 bit
1/3 of the time.

How would one go about testing this PRNG against an idealized
(similarly biased) PRNG?

- DLD

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

"Robert E. Beaudoin" <rbeaudoin@acm.org> writes:

One thing you could do is to apply von Neumann de-biasing to convert a
string of output bits from your biased PRNG to an unbiased string, and
test the de-biased output.

Some non-uniform generators are based on uniform generators
whose output then is warped by the application of some function.

If one has access to the underlying uniform generator used,
one can test this with the algorithms for uniform generators.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)