Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
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. –  Robert Israel Jul 13 '11 at 21:37
    
@Robert's comment is the answer, I believe... :) –  J. M. Jul 14 '11 at 10:58

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.