home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / stat / 2753 < prev    next >
Encoding:
Text File  |  1993-01-12  |  4.2 KB  |  95 lines

  1. Newsgroups: sci.math.stat
  2. Path: sparky!uunet!cs.utexas.edu!torn!news.ccs.queensu.ca!mast.queensu.ca!dmurdoch
  3. From: dmurdoch@mast.queensu.ca (Duncan Murdoch)
  4. Subject: Re: Nonrandom Random Numbers?
  5. Message-ID: <dmurdoch.393.726873235@mast.queensu.ca>
  6. Lines: 83
  7. Sender: news@knot.ccs.queensu.ca (Netnews control)
  8. Organization: Queen's University
  9. References: <1993Jan12.132319.6437@cbis.ece.drexel.edu> <1993Jan12.140114.620@hnrc.tufts.edu>
  10. Date: Tue, 12 Jan 1993 21:13:55 GMT
  11.  
  12. In article <1993Jan12.140114.620@hnrc.tufts.edu> jerry@hnrc.tufts.edu (Jerry Dallal) writes:
  13. >For those who do not have the Times, the article says, " . . . the scientists
  14. >showed that five of the most popular computer programs for generating streams
  15. >of random numbers produced errors when they were used in a simple mathematical
  16. >model of the behavior of atoms in a magnetic crystal."  
  17.  
  18. >Unfortunately (and understandably) the article does not identify the 5 
  19. >algorithms.  However, the article cites the original report from Ferrenberg et
  20. >al. in the Dec. 7 issue of Physical Review Letters.  I would be grateful if
  21. >someone with access to PRL would post the five generators.
  22.  
  23. The paper is Ferrenberg, A. M., Landau, D.P., and Wong, Y.J. (1992), Monte 
  24. Carlo simulations:  hidden errors from "good" random number generators,
  25. Physical Review Letters 69 no. 23, 3382-3384.
  26.  
  27. The generators tested were:
  28.  
  29. CONG:  A linear congruential generator
  30.          X_n = (16807 X_{n-1}) mod (2^{31} - 1)
  31.  
  32. R250:  A shift register algorithm:
  33.          X_n = X_{n-103} XOR X_{n-250}
  34.  
  35. R1279: Another shift register algorithm:
  36.          X_n = X_{n-1063} XOR X_{n-1279}
  37.  
  38. In R250 and R1279, "XOR" is a bitwise exclusive OR; it doesn't say how 
  39. many bits were used, but I'd assume 32 from the context.
  40.  
  41. SWC:   A subtract with carry generator (Marsaglia et al, Comput Phys Commun
  42. 60, p 345, 1990):
  43.  
  44.          X_n = X_{n-22} - X_{n-43} - C
  45.          if X_n >= 0, C=0,
  46.          if X_n < 0, X_n = X_n + (2^32-5), C=1
  47.  
  48. SWCW:   A combined subtract with carry Weyl generator (ibid):
  49.  
  50.          Z_n = X_{n-22} - Z_{n-43} - C
  51.      if Z_n >= 0, C=0
  52.          if Z_n < 0, Z_n = Z_n+(2^32-5), C=1
  53.      Y_n = (Y_{n-1} - 362436069) mod 2^32
  54.      X_n = (Z_n - Y_n) mod 2^32
  55.  
  56. The simulations they did were of an Ising model on a 16 x 16 lattice with
  57. periodic boundary conditions, where exact results are known.  They estimated 
  58. the internal energy and specific heat using the Wolff cluster-flipping 
  59. algorithm (Phys Rev Lett 62, p 361, 1989) the Swendsen-Wang algorithm 
  60. (Phys Rev Lett 58, p 86, 1987) and a single-spin-flop Metropolis algorithm 
  61. with sequential updating (see e.g. D.P. Landau in Applications of the Monte 
  62. Carlo Method, K. Binder ed., Springer-Verlag 1987).
  63.  
  64. They used CONG to initialize the other generators.
  65.  
  66. Between 5 and 10 runs of 10^7 updates were performed.
  67.  
  68. They found the Wolff algorithm produced estimates which were 
  69. systematically biased for internal energy and/or specific heat for all 
  70. random number generators except CONG; the biases were all small (around 1 
  71. part in 10^-4), but large in terms of standard errors (from 3 to 100 
  72. standard errors from the true value for at least one of those measures).  
  73. The CONG algorithm was within 1 standard error on both measures.
  74.  
  75. CONG did badly (more than 13 s.e.) when used in the Metropolis algorithm 
  76. but okay in Swendsen-Wang; R250 and SWC were fine in Metropolis but bad in 
  77. S-W  (6 and 4 s.e. respectively).  However, overall the problems weren't as 
  78. severe as with the Wolff algorithm.
  79.  
  80. The authors conclude (with their italics marked _so_):
  81.  
  82. "In conclusion, extensive Monte Carlo simulations on an Ising model for 
  83. which the exact answers are known have shown that ostensibly high quality 
  84. random number generators may lead to subtle, but _dramatic_, systematic 
  85. errors for some algorithms, but not others.  Since there is no reason to 
  86. believe that the model which we have investigated has any special 
  87. idiosyncracies, these results offer another stern warning about the need to 
  88. very carefully test the implementation of new algorithms.  In particular, 
  89. this means that a specific algorithm must be tested together with the random 
  90. number generator being used _regardless_ of the tests which the generator 
  91. has passed."
  92.  
  93. Duncan Murdoch
  94. dmurdoch@mast.queensu.ca
  95.