4
$\begingroup$

Take the R runif function for example.
It sure is a very performing pseudo-random generator. Even if I don't really know what it means I think I read somewhere that it will produce uniformly distributed variables up to more than 600 dimensions (based on the default Mersenne Twister).
Apart from simulating an extremely large number of observations to actually see that this not absolutely random, is there a way which will not rely on very heavy computing to see its limited randomness? More generally, is there a " simple test" that even the current best PRG fail to pass?

$\endgroup$
2
  • 1
    $\begingroup$ I don't think such a test exists. A famous set of tests are the en.wikipedia.org/wiki/Diehard_tests $\endgroup$ Nov 28, 2019 at 16:46
  • $\begingroup$ If it were easy to show that runif does not produce independent, identically distributed uniform random observations, then a different algorithm for runif would have beeen implemented. $\endgroup$
    – BruceET
    Nov 28, 2019 at 22:11

2 Answers 2

7
$\begingroup$

Some years ago the multiplicative congruential generator $r_{n+1} = ar_i \;(\!\!\mod d\,),$ with $a = 65539, d = 2^{31}$ was proposed (and used for a while) to generate numbers $u_i = \frac{r-.5}{d-1},$ intended to be essentially independent and identically distributed on $(0,1).$ However, when triads of these numbers are plotted in the three dimensional unit cube, it can be seen that the points fall in only a few parallel planes.

Two plots of points of this generator are shown below. At left, is a plot of points $(u_i, u_{i+1}),$ generated points look random; at right, a thin veneer from the front face of successive points plotted in the unit cube shows edges of the few planes on which all points lie.

a = 65539;  d = 2^31;  s = 10
m = 40000;  r = numeric(m);  r[1] = s
for(i in 1:(m-1))
   { r[i+1] = (a*r[i]) %% d }
u = (r-.5)/(d-1) 
u1 = u[1:(m-2)];  u2 = u[2:(m-1)];  u3 = u[3:m]

par(mfrow=c(1,2))
 plot(u1,u2, pch=".", xlim=0:1, ylim=0:1, 
      main="Unit Square")
 plot(u1[u3 < .01], u2[u3 < .01], pch=".", xlim=0:1, ylim=0:1, 
      main="Face of Cube")
par(mfrow=c(1,1))

enter image description here

Nowadays a proposed pseudorandom number generation algorithm is typically subjected to a 'battery' of tests before it is implemented for practical use. These tests are tasks known to be difficult to simulate, and include tasks that previous unsatisfactory generators have not been able to handle.

$\endgroup$
1
  • $\begingroup$ Nice! Came here to see this. I remember the first time a friend simply plotted a large string of pseudorandom numbers into a square gif. It was instructive, as was walking through a variety of pseudo-RNGs. $\endgroup$
    – Alexis
    Nov 28, 2019 at 23:55
2
$\begingroup$

I believe R uses a Mersenne Twister. It's good, it's widely used, but it's not clear that it's "the best". As BruceET mentions, there are test suites. Diehard is kind of old, and TestU01 incorporates many of its tests and more. There are a couple of tests in TestU01 that the standard Mersenne Twister fails, because it does exactly the kind of thing that those tests look for. The paper at that site and Pierre L'Ecuyer's other papers are good sources. Melissa O'Neill's paper is very informative in general, and it will give you a lot of information about visualizations. I list some other resources, including introductory books, in this answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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