On 12/22/2013 09:06 AM, Marco Leise wrote:

Am Sun, 22 Dec 2013 02:12:51 +0100 schrieb Timon Gehr <timon.g...@gmx.ch>:## Advertising

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. :)