What are congruent linear pairs


Next page:Tests of quality properties Upwards:Generation of pseudo random numbers Previous page:Simple application examples; Monte Carlo Estimator & nbsp content


Linear congruence generators

  • Form the starting point for most simulation algorithms Standard random number generators,
  • A widely used method for generating standard pseudorandom numbers is as follows linear congruence method,


We now solve the recursion equation (1), i.e., we show how the number recursively defined in (1) can be directly by the start value as well as through the parameters , or. expresses.

proof
 
Notice
 
  • It is clear that with the linear congruence generator defined in (1) at most different numbers can be generated.
  • In the case of an unfavorable choice of parameters , , or. can be the length of the period be very small.


We now mention (sufficient and necessary) conditions for the parameters , , or. that in particular ensure that the maximum possible period is achieved.

Theorem 3.2    
1.
If , the in defined linear congruence generator exactly then for each starting value a sequence of numbers with the maximum possible period if the following conditions are met:
(a)
The parameters and are coprime.
(a)
For every prime number , the shares is a multiple of .
(a)
If a multiple of is, then is too a multiple of .
2.
If , then applies for each exactly when
(b)
is a prime number,
(b)
for every prime number , the divides that number not through is divisible.
3.
If and if there is one With there is exactly when is an odd number and if or applies.
  • One proof of Theorem 3.2, in which the results of number theory (including Fermat's Little Theorem) are used, one can for example
    • in section 2.7 of the book by B.D. Ripley (1987) Stochastic simulation, J. Wiley & Sons, New York or
    • in Section 3.2 of D.E. Knuth (1997) The Art of Computer ProgrammingFind, Vol. II, Addison-Wesley, Reading MA.
  • In addition, we also refer to these two books for discussion
  • One such quality characteristic is
  • Further details can be found, for example, in the aforementioned book by Ripley (1987) or in the lecture script by H. K√ľnsch at ftp://stat.ethz.ch/U/Kuensch/skript-sim.ps, where the the following figures are included.


Next page:Tests of quality properties Upwards:Generation of pseudo random numbers Previous page:Simple application examples; Monte Carlo Estimator & nbsp content Ursa Pantle 2003-09-29