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.

## periodicity in LCGs

**Moderators:** gmalivuk, Moderators General, Prelates

### Re: periodicity in LCGs

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.

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.

### Re: periodicity in LCGs

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.

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.

### Who is online

Users browsing this forum: mashnut and 19 guests