[R] Wichmann-Hill Random Number Generator and the Birthday Problem

[Shengqiao Li]

> Prof Brian Ripley wrote:
>> Your coincidence calculations may be correct for _independent_ draws from a 
>> discrete distribution on M values, but independence is not satisfied.
>> Yet again, you are trying to do things that any good text on simulation 
>> would warn you against, and which (in a thread on R-devel) you have already 
>> been told a good way to do.
>> 
> A good example are the "good" old linear congruential random generators. 
> These will start repeating at the first coincidence, for the pretty obvious 
> reason that the next random number is a function only of the previous one. So 
> the number of distinct values in N draws is min(N, cycle_length). In 
> particular, the number of coincidences is 0 when N is less than cycle_length.

So, we can conclude that the programming implementation for Wichmann-Hill 
does not reduce the number of possible values but it does for other 
generators. Moreover, the cycle_lenght for other generators in R are quite 
long and these generators are more random than those old, like the W-H 
genrator. When wrapped to 32-bit or 30-bit integers, ties are easily and 
randomly produced for these generators of long cycles. Since they are 
more random, the Poisson appxoimation for the number of ties is appliable and quite accurate.

This sugguest that W-H is not good as others in the terms of randomness?

The following  paragraph in RNG help is misleading since it does not apply 
Wichman-Hill generator. It should be updated.

"All the supplied uniform generators return 32-bit integer values
      that are converted to doubles, so they take at most 2^32 distinct
      values and long runs will return duplicated values."


Shengqiao Li

>
> -- 
>  O__  ---- Peter Dalgaard             Øster Farimagsgade 5, Entr.B
> c/ /'_ --- Dept. of Biostatistics     PO Box 2099, 1014 Cph. K
> (*) \(*) -- University of Copenhagen   Denmark      Ph:  (+45) 35327918
> ~~~~~~~~~~ - (p.dalgaard at biostat.ku.dk)              FAX: (+45) 35327907
>
>