# the Collision test

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

`lenSample` |
numeric for the length of generated samples. |

`segments` |
numeric for the number of segments to which the interval |

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

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