periodicity in LCGs

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

>-)
Posts: 512
Joined: Tue Apr 24, 2012 1:10 am UTC

periodicity in LCGs

Postby >-) » Tue Nov 21, 2017 5:02 pm UTC

An LCG is a random generator in the form:

X_{x+1} = (aX_t + c) mod m

where X_t was the last number to be output. All variables in this expression are integers.

For performance reasons, m is frequently a power of 2, say 2^k.

Wikipedia claims that this LCG (with power of 2 m) causes low-order bits to have very short periods. This is supported by the fact that implementations usually discard the lower-order bits of the RNG -- for java's random nextInt function, the lower 17 bits are discarded.

However, I'm having a lot of trouble finding mathematical justification for this lower-order periodicity.

Here are some examples. For a = 3, c = 2, k = 4, and a starting value of 1, the output is 1, 5, 1, 5, 1.... obviously very periodic.

For a = 3, c = 3, k = 4, the output is 1, 6, 5, 2, 9, 14, 13, 10, 1, ....
in binary this is
0001
0110
0101
0011
1001
1110
1101

both the lowest order and the second lowest order bits have a period of 2, the third lowest order bit has a period of 4. so it seems we have some empirical evidence for the phenomenon.

Now my attempt at a proof. the idea is that if the lower-order bits have short periods, that is equivalent to saying that for small values of k, the entire output has a short period. so i'll just attempt to solve for the periodicity of the entire system.

A rewriting of X_{t+p}
Image

Now we want to find the period p
Image
Now here is where i'm stuck. I'm not sure how to manipulate this further to get something useful out of it.

User avatar
jaap
Posts: 2073
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: periodicity in LCGs

Postby jaap » Tue Nov 21, 2017 7:11 pm UTC

You have
X_{t+1} = (aX_t + c) mod 2^k

You can simply look at it mod 2^1:
X_{t+1} = (aX_t + c) mod 2
The resulting lowest bit of X_{t+1} does not depend on any of the higher bits of X_t, only on the lowest bit. Therefore, this reduced PRNG essentially has an internal state consists only of a single bit, so there is no way for it to have a period of more than 2 (and it has period 2 if both a and c are 1 mod 2).

If you look at that equation mod 2^2, you'll find that the only lowest 2 bits of X_t go into determining the lowest 2 bits of X_{t+1}. This has 4 possible states, so the lowest two bits (or the second bit in particular) have a period of no more than 4.

Similarly the lowest 3 bits (or the third bit in particular) have a period of at most 8. etc.

>-)
Posts: 512
Joined: Tue Apr 24, 2012 1:10 am UTC

Re: periodicity in LCGs

Postby >-) » Wed Nov 22, 2017 4:16 am UTC

Yes, i see now. It's almost like you can break the equation up as

X_{t+1} = aX_hi + aX_lo + c
where X_lo consists of the k' lowest bits and X_hi consists of the rest. Then X_{t+1} mod 2^k' is just aX_lo + c. So it's as if you had a smaller LCG inside the bigger one.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 13 guests