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$$
Asked
Active
Viewed 118 times
0
-
1What have you thought of so far? How do you define and test randomness? – davidlowryduda 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 http://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
-
5Assuming $\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... :) – J. M. ain't a mathematician Jul 14 '11 at 10:58
1 Answers
1
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.
75064
- 3,410