# why the increment doesnt affect the randomness?

I'm doing some homework and I need to answer why the increment (b) doesn't affect randomness in the mixed congruential method.

The formula is

$$X_{n+1} \equiv (a X_n + b) \mod m$$

-
What have you thought of so far? How do you define and test randomness? –  mixedmath Jul 13 '11 at 20:52
If you want the sequence to pass a randomness test (distribution, correlation,...) please specify. I guess a precise answer depends what test you are interested in. If the bad guys know that you are using linear congruential generator - with or without the additive constant - it is easy to start predicting the next number to be generated after having seen a few. If you use the additive constant you just need one more number in order to start cracking it. See math.stackexchange.com/q/43948/11619 for a little more details. –  Jyrki Lahtonen Jul 13 '11 at 20:55
Thanks for your reply, I haven't thought much about it. It is the first question I have to answer about pseudo-random generators. The professor gave me this formula and he wanted me to explain him why b doesn't affect the randomness of the generator. So far, I found that the increment is used to reduce the change of repetition and there's also the multiplicative congruential method, in which I can see clearly that b doesn't take part in randomness. However, I haven't found the reason of it. –  Matias Waterloo Jul 13 '11 at 21:23
Assuming $\text{gcd}(a-1,m) = 1$, there is some $d$ such that $Y_n = X_n + d \text{ mod } m$ satisfies $Y_{n+1} = a Y_n \text{ mod } m$, so all the increment accomplishes is a constant shift in the sequence. –  Robert Israel Jul 13 '11 at 21:37
@Robert's comment is the answer, I believe... :) –  Ｊ. Ｍ. Jul 14 '11 at 10:58

Assuming $\mathrm{gcd}\,(a−1,m)=1$, there is some $d$ such that $Y_n=X_n+d \mod m$ satisfies $Y_{n+1}=aY_n \mod m$, so all the increment accomplishes is a constant shift in the sequence.

-