# colltestsparse: the Collision test In randtoolbox: Toolbox for Pseudo and Quasi Random Number Generation and RNG Tests

## Description

The Collision test for testing random number generators.

## Usage

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

## 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

## 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) = ∏_{i=0}^{n-c-1} (k-i)/k *1/(k^c) 2S_n^{n-c},

where 2S_n^{n-c} denotes the Stirling number of the second kind and c=0,..., 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 n/k < 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.

## Value

A data frame with `nbSample` rows and the following columns.

`observed` the observed counts.

`p.value` the p-value of the test.

## Author(s)

Christophe Dutang, Petr Savicky.

## 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.

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

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.
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16``` ```# (1) poisson approximation # coll.test.sparse(runif) # (2) exact distribution # coll.test.sparse(SFMT, lenSample=2^7, segments=2^5, tdim=2, nbSample=10) #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) ```