Am Sun, 22 Dec 2013 09:19:48 +0000
schrieb "Chris Cain" <clc...@uncg.edu>:
> On Sunday, 22 December 2013 at 08:06:30 UTC, Marco Leise wrote:
> > Can you elaborate a bit? How do you know that the Java LCG
> > can produce every 32-bit integer once? 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. (Expectations can do strange things to
> > your perception.)
> If I may,
> Definition of an LCG:
> Xnext = (a * Xprev + c) % m
> An LCG is said to have a "full period" if the length of the
> period is m. If the period is m, we know the LCG must produce
> every number between 0 and m because if there was even one
> repeated number then the generator as defined above would repeat
> the entire sequence up to that point and, thus, the period would
> not be m, which is a contradiction.
> According to the Hull-Dobell Theorem, an LCG will have a full
> period iff:
> 1. `c` and `m` are relatively prime.
> For Java, c = 11 and m = 2^48
> This condition applies.
> 2. `(a - 1)` is divisible by all prime factors of m`
> For Java, a = 25214903917 and thus a-1 is even which means the
> prime factors of m (just 2) do divide it.
> This condition applies.
> 3. `a - 1` is a multiple of 4 if `m` is a multiple of 4.
> For Java, m is a multiple of 4.
> `(a - 1)/4` is 6303725979, so it's also a multiple of 4.
> This condition applies as well.
> Since Java's LCG has a full period over 2^48, we know that taking
> the top 32 bits (which is what Java does to get "better"
> randomness) would also all be represented.
Am Sun, 22 Dec 2013 13:09:51 +0100
schrieb Timon Gehr <timon.g...@gmx.ch>:
> 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)^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.
Thank you two for explaining LCGs to me. That's good
information for reasoning about code. Every good (full period)
LCG is a specific permutation of the numbers [0..m). The next
time I wonder how I can iterate in random order over a list of
length n^2, I know what I'll use ;)