randtoolbox (version 2.0.5)

coll.test.sparse: the Collision test

Description

The Collision test for testing random number generators.

Usage

coll.test.sparse(rand, lenSample = 2^14, segments = 2^10, tdim = 2, 
nbSample = 10, ...)

Value

A data frame with nbSample rows and the following columns.

observed the observed counts.

p.value the p-value of the test.

Arguments

rand

a function generating random numbers. its first argument must be the 'number of observation' argument as in runif.

lenSample

numeric for the length of generated samples.

segments

numeric for the number of segments to which the interval [0, 1] is split.

tdim

numeric for the length of the disjoint t-tuples.

nbSample

numeric for the number of repetitions of the test.

...

further arguments to pass to function rand

Author

Christophe Dutang, Petr Savicky.

Details

We consider outputs of multiple calls to a random number generator rand. Let us denote by \(n\) the length of samples (i.e. lenSample argument), \(k\) the number of cells (i.e. nbCell argument).

A collision is defined as when a random number falls in a cell where there are already random numbers. Let us note \(C\) the number of collisions

The distribution of collision number \(C\) is given by $$ P(C = c) = \prod_{i=0}^{n-c-1}\frac{k-i}{k} \frac{1}{k^c} {}_2S_n^{n-c}, $$ where \({}_2S_n^k\) denotes the Stirling number of the second kind and \(c=0,\dots,n-1\).

This formula cannot be used for large \(n\) since the Stirling number need \(O(n\log(n))\) time to be computed. We use a Poisson approximation if \(\frac{n}{k} < \frac{1}{32}\) and the exact formula otherwise.

The test is repeated nbSample times and the result of each repetition forms a row in the output table.

References

P. L'Ecuyer, R. Simard, S. Wegenkittl, Sparse serial tests of uniformity for random number generators. SIAM Journal on Scientific Computing, 24, 2 (2002), 652-668. tools:::Rd_expr_doi("10.1137/S1064827598349033")

L'Ecuyer P. (2007), Test U01: a C library for empirical testing of random number generators. ACM Trans. on Mathematical Software 33(4), 22. tools:::Rd_expr_doi("10.1145/1268776.1268777")

See Also

other tests of this package coll.test, freq.test, serial.test, poker.test, order.test and gap.test

ks.test for the Kolmogorov Smirnov test and acf for the autocorrelation function.

Examples

# (1) poisson approximation
#
coll.test.sparse(runif)

# (2) exact distribution
#
coll.test.sparse(SFMT, lenSample=2^7, segments=2^5, tdim=2, nbSample=10)

if (FALSE) {
#A generator with too uniform distribution (too small number of collisions)
#produces p-values close to 1
set.generator(name="congruRand", mod="2147483647", mult="742938285", incr="0", seed=1)
coll.test.sparse(runif, lenSample=300000, segments=50000, tdim=2)

#Park-Miller generator has too many collisions and produces small p-values
set.generator(name="congruRand", mod="2147483647", mult="16807", incr="0", seed=1)
coll.test.sparse(runif, lenSample=300000, segments=50000, tdim=2)
}