legacy code retreat's triva game : the D version

[Timon Gehr]

On 12/22/2013 09:06 AM, Marco Leise wrote:
> Am Sun, 22 Dec 2013 02:12:51 +0100
> schrieb Timon Gehr <timon.gehr at gmx.ch>:
>
>> On 12/22/2013 02:09 AM, Timon Gehr wrote:
>>>>
>>>> The morale is that "uniform" random numbers doesn't imply that
>>>> every value in the range will eventually be generated once!
>>>>
>>>
>>> Yes it does. (The probability that some value is never generated is 0.)
>>> The actual morale is that random number generators do not generate true
>>> randomness, and poor random number generators may generate sequences
>>> that do not look remotely random.
>>
>> 'pseudo random number generators' would be a more accurate term.
>
> Can you elaborate a bit?

The probability that a certain number does not occur in one round is 
(n-1)/n.

((n-1)/n)^k goes to 0 rather fast as k goes to infinity.

In fact, the expected number of trials until all numbers are covered is 
~ n log n, and the probability that the process runs significantly 
longer is very small.

See also: http://en.wikipedia.org/wiki/Coupon_collector%27s_problem


> How do you know that the Java LCG can produce every 32-bit integer once?

Typically constants are chosen such that this holds, but your code would 
require something stronger to fail, namely, that a certain congruence 
class does not occur. Typically pseudo random number generators are 
chosen such that the generated sequences look close to true randomness. 
If such a simple process can be used to reliably distinguish true 
randomness and the pseudo random number generator, then the pseudo 
random number generator is not very good.

> If that's true then
> the problem with the Java code was something different and I
> was just biased, because I was already expecting the code to
> fail before the fact.

Maybe. There is a vast number of ways that this could have failed.

> (Expectations can do strange things to your perception.)
>

Indeed. :)