commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Phil Steitz <phil.ste...@gmail.com>
Subject Re: [Math] Uniqueness test expectation
Date Fri, 05 Feb 2016 16:43:28 GMT
On 2/5/16 8:29 AM, Gilles wrote:
> Hi.
>
> What can I expect from drawing N "int" values from a (supposedly)
> uniformly random number generator?
> In fact, I'm wondering about a valid test condition that all the
> samples are different.
> Alternatively, how many times one should have to draw a set of N
> samples so that at least one set contains samples that are all
> different?

If there are p values (i.e, the sampling is from  S = {0, ...,
p-1}), then the probability that n values in a sequence are all
distinct is p* = (p!/(p - n)!) / p^n.
Assuming independence, which the null hypothesis of homogeneity
supports, you can view successive n-sequence draws as Bernoulli
trials, so the probability you are asking for is the expected value
of a geometric distribution with probability of success = p*.  You
can use the quantiles of the Geometric distribution to select a
critical value to use in a test based on observing this.  I am not
sure how powerful or stable such a test would be, though.

See [1] for some standard PRNG tests.  There are a lot more.  NIST
has a test suite for crypto-grade PRNGs (which we do not claim to
have) [2]

Testing PRNGs is tricky business. I personally put a lot of stock in
the reference tests, since they validate (unless I am wrong about
their source) that we have a faithful implementation of the standard
algorithm, which itself has been validated by experts in PRNG
development and evaluation.  

Phil

[1] http://cacr.uwaterloo.ca/hac/about/chap5.pdf
[2]
http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html


>
> Thanks,
> Gilles
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message