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