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-unsubscr...@commons.apache.org
> For additional commands, e-mail: dev-h...@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
