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

$\endgroup$
5
  • 1
    $\begingroup$ What have you thought of so far? How do you define and test randomness? $\endgroup$
    – davidlowryduda
    Commented Jul 13, 2011 at 20:52
  • $\begingroup$ 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. $\endgroup$ Commented Jul 13, 2011 at 20:55
  • $\begingroup$ 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. $\endgroup$ Commented Jul 13, 2011 at 21:23
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Jul 13, 2011 at 21:37
  • $\begingroup$ @Robert's comment is the answer, I believe... :) $\endgroup$ Commented Jul 14, 2011 at 10:58

1 Answer 1

1
$\begingroup$

Answer given by Robert Israel in the comments:

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .