Nonuniform PRNG?

[Sabrina Almodóvar]

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.