home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / stat / 1526 < prev    next >
Encoding:
Internet Message Format  |  1992-07-27  |  2.2 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!mips!sdd.hp.com!cs.utexas.edu!asuvax!ncar!noao!amethyst!organpipe.uug.arizona.edu!news
  2. From: paul@music.sie.arizona.edu (Paul J. Sanchez)
  3. Newsgroups: sci.math.stat
  4. Subject: Re: random number generator
  5. Message-ID: <1992Jul27.201230.984@organpipe.uug.arizona.edu>
  6. Date: 27 Jul 92 20:12:30 GMT
  7. References: <1992Jul27.132508.217@ginger.hnrc.tufts.edu>
  8. Sender: news@organpipe.uug.arizona.edu
  9. Organization: University of Arizona UNIX Users Group
  10. Lines: 41
  11.  
  12. Jerry Dallal writes
  13. > In article <1992Jul27.124120.29511@cl.cam.ac.uk>, nmm@cl.cam.ac.uk (Nick  
  14. Maclaren) writes:
  15. > > In article <1992Jul27.103659.11820@kth.se>, md87-mpe@hemul.nada.kth.se
  16. > > (Magnus Pettersson) writes:
  17. > >  
  18. > > |> 3. G.E.P.Box and M.E.Mueller
  19. > > |>    A Note on the Generation  of Random Normal Deviates
  20. > > |>    Ann.Math.Stat. (1958) 29, 610-611
  21. > > 
  22. > > Don't use this method in single precision [...]
  23. > > 
  24. > 
  25. > Wait! . . .  Stop! . . . Hold on a moment! . . .
  26. > 
  27. > There is nothing wrong with the Box-Muller method.  It is
  28. > theoretically sound [...]
  29.  
  30. Theory works beautifully when all of the assumptions hold.  One of the  
  31. assumptions for the Box-Muller method is that you have i.i.d. uniform  
  32. variables on the input side.  This happens to be false in most computing  
  33. contexts -- most people use a sequence of pseudo-random numbers which are  
  34. uncorrelated but hardly independent.
  35.  
  36. The most common source of pseudo-random numbers is the Linear Congruential  
  37. Generator algorithm, or LCG for short.  A result by Marsaglia states that  
  38. k-tuples from a LCG all fall on a bounded number of hyperplanes.  As a  
  39. result, there is an interaction with the Box-Muller algorithm which causes  
  40. all of the values produced to fall along a spiral.  For some very pretty  
  41. pictures, check out the book "Stochastic Simulation" by Brian D. Ripley  
  42. ('87, J. Wiley & Sons).  Pages 55-58 should do a good job of convincing  
  43. you that the results are definitely not independent normals.
  44.  
  45. There are a couple of morals to this story:
  46. a) If you want to use Box-Muller, use something other than a LCG; and
  47. b) Just because an algorithm is theoretically sound, don't assume you'll  
  48. get usable results.
  49.  
  50. --paul
  51. paul@music.sie.arizona.edu
  52. (NeXT mail welcome!)
  53.