periodicity in LCGs

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 522
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

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}

Now we want to find the period p
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
Posts: 2075
Joined: Fri Jul 06, 2007 7:06 am UTC

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: 522
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 19 guests