0
$\begingroup$

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$$

  • 1
    What have you thought of so far? How do you define and test randomness?2011-07-13
  • 0
    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 http://math.stackexchange.com/q/43948/11619 for a little more details.2011-07-13
  • 0
    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.2011-07-13
  • 5
    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.2011-07-13
  • 0
    @Robert's comment is the answer, I believe... :)2011-07-14

1 Answers 1