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.

On a practice exam for a course on stochastic simulations I encountered the following question:

Show that the least significant $n$ bits must repeat with a period $2^n$ for a congruential random generator with a period $2^m$ where $m > n$.

I couldn't find an answer on how to do this anywhere. How can I shows this? Is it just that the $n$ bits can only generate $2^n$ numbers?

share|improve this question
    
What is the definition of congruential random number generator? $x_n = ax_{n-1} + b \mod c$ or $x_n = ax_{n-1} \mod c$? and what are the values of $a$, $b$, and $c$? –  Dilip Sarwate Dec 19 '11 at 19:16
    
That is not given but I assume $x_n = a x_{n−1}$mod$c$, with $a=2^n$ and $c=2^m$. –  Zagga Dec 19 '11 at 19:53
    
Try your generator with, say, $x_0 = 1023$, $n=5$, $m = 32$. What are the values of $x_1$, $x_2, \ldots$? Hint: computation by hand is easy, especially if you represent the $x_i$ as $32$-bit words. –  Dilip Sarwate Dec 19 '11 at 20:21

1 Answer 1

In Chapter 3 of D. E. Knuth's The Art of Computer Programming, vol. 2, (1st edition), it is shown that the low-order $n$ bits repeat with a period of $2^n$ or less for any choice of the multiplier $a$. If you want to prove that the period is exactly $2^n$, then you may need to place restrictions on $a$. You may also need to place restrictions on the modulus $c$ because Knuth also says that if the modulus $c$ is $2^m$ (as in your comment), then the low-order bits are not quite as random as is possible with other choices of $c$.

share|improve this answer
    
In short: using the least significant bits for generating "new" random numbers isn't that good an idea. :) –  J. M. Dec 20 '11 at 3:00

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.