1
$\begingroup$

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?

  • 0
    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$? – 2011-12-19
  • 0
    That is not given but I assume $x_n = a x_{nāˆ’1}$mod$c$, with $a=2^n$ and $c=2^m$. – 2011-12-19
  • 0
    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. – 2011-12-19

1 Answers 1