Re: Nonuniform PRNG?
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 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 -- https://mail.python.org/mailman/listinfo/python-list
Re: Nonuniform PRNG?
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: Nonuniform PRNG?
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 -- https://mail.python.org/mailman/listinfo/python-list
Re: Nonuniform PRNG?
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? -- https://mail.python.org/mailman/listinfo/python-list
Re: Nonuniform PRNG?
On 07/12/2022 14:04, Stefan Ram wrote: > r...@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 -- https://mail.python.org/mailman/listinfo/python-list
Re: Nonuniform PRNG?
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. -- https://mail.python.org/mailman/listinfo/python-list
Nonuniform PRNG?
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 -- https://mail.python.org/mailman/listinfo/python-list
