1
$\begingroup$

I was reading the article of L'Ecuyer on random number generation. The title of this article is "Uniform Random Number Generation". One of the proposed PRNGs there, is multiple recursive random number generators added with a constant.

My question is Why the distribution of a multiple recursive random number generators added with a constant is uniform? I couldn't find a proper reference on the subject.

These random number generators are defined by equation: $$ x_{n}\equiv a_1x_{n-1}+a_2x_{n-2}+\ldots+a_kx_{n-k}+a\pmod{m}$$

I'm looking specially for the case of $m=2^r$, which a lower hardware complexity is required for its implementation on digital systems.

$\endgroup$
6
  • $\begingroup$ Are the $x_i$ real or integers? What is their support, such as $\{0,1\}$ or $[0,1)$ or $[0,m)$ or $\{0,1,2, \ldots,m-1\}$? $\endgroup$
    – Henry
    Aug 31 '15 at 11:50
  • $\begingroup$ In MRGs $x_i \in \{0,1,2,\ldots,m-1\}$ $\endgroup$
    – SMA.D
    Aug 31 '15 at 11:53
  • $\begingroup$ It would be helpful if all the $a_i$ (at the very least, one of them) were coprime with $m$ $\endgroup$
    – Henry
    Aug 31 '15 at 11:59
  • $\begingroup$ I think this assumption should not be necessary, according to the article of L'Ecuyer. However, in the special case that I'm looking for,i.e. $m=2^r$, the characteristic polynomial of the recursion is primitive modulo $2$ but in general I don't know. $\endgroup$
    – SMA.D
    Aug 31 '15 at 12:41
  • $\begingroup$ Well for example if $m=2^r$ and all the $a_i$ are even, that will fix the parity of $x_n$ $\endgroup$
    – Henry
    Aug 31 '15 at 12:48
2
$\begingroup$

Of course, no deterministic algorithm can generate truly random numbers. The goal is to find an algorithm that gives output values that 'behave as if' they are independent and identically distributed according to some distribution--usually $Unif(0, 1).$

By 'behave as if' one means that the pseudo-random numbers pass a large battery of benchmark tests for randomness, and give correct answers (within random error) to a large collection of problems known to be difficult to simulate. If a PRNG fails at one of these tasks, we know it's a 'bad' one. 'Good' PRNGs are ones that have not been proved bad after extensive testing. (Beyond the obvious, special attention is given to checking to see there is no multi-dimensional serial correlation, even in high dimensions.)

Some number-theoretic and other rules are known, telling kinds of algorithms and specific choices of constants (e.g, your $a_i$ and $m$) one must always avoid. Other rules are known for making 'potentially' promising PRNGs, but one never knows if a particular PRNG is useful until it is thoroughly vetted.

If you have access to R statistical software, a list of PRNGs currently regarded as 'good' is available by typing ? .Random.seed at the prompt > in the Session window. The default in R is the 'Mersenne-twister', which has a 'good' record after very extensive use.

There is controversy whether digits far out into the decimal representation of transcendental numbers such as $e$ and $\pi$ are random, but the controversy is not of practical importance because it takes too much computing to get vast numbers of digits rapidly enough for modern simulations.

The best efforts towards truly random numbers have used physical random noise of various sorts. But these methods are currently too slow for extensive simulations. Perhaps somewhere along the line toward the development of quantum computers a way to generate truly random values at a very rapid rate will be discovered.

$\endgroup$
4
  • $\begingroup$ Thank you for answering. Do you mean that there is no proof for the fact that 'this random-like behavior is uniform' and these PRNGs are classified to be uniform only by statistical tests? $\endgroup$
    – SMA.D
    Sep 3 '15 at 6:15
  • 1
    $\begingroup$ No formal mathematical proof. By their good works shall ye know them. $\endgroup$
    – BruceET
    Sep 3 '15 at 7:12
  • $\begingroup$ Do you know a good reference book containing statistical analysis of the subject? $\endgroup$
    – SMA.D
    Sep 4 '15 at 2:52
  • $\begingroup$ Most books on simulation have introductory chapters on PRNGs and how they are vetted. Pick one that matches your level of math and computer backgrounds. $\endgroup$
    – BruceET
    Sep 4 '15 at 4:10
1
$\begingroup$

The definite discussion on congruential random number generation is in Knuth's "Seminumerical Algorithms" (volume 2 of his "The Art of Computer Programming", Addison-Wesley). Lots of other types of generators have been proposed since, but as far as I know none has undergone the same theoretical and practical scrutiny. The last edition of the book recommends ran_array, a portable generator that is freely available (in FORTRAN and C).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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