### periodicity in LCGs

Posted:

**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}

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.

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}

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.