Conference rusure::math

755.0. "Dist. of Random Nos." by MYKENE::TURNER () Fri Aug 28 1987 07:06

This note describes a slow but flexible and apparently accurate way
of adapting uniform random numbers to fit any arbitrary distribution.
I looked over previous discussions of randomness; apologies if this 
duplicates previous notes.  

This method is my own improvisation.  I'd appreciate any descriptions
of improvements or better methods.  I'm aware that there are specific 
transforms and methods available for specific distributions; I don't
have a knowledge of (or good access to) the literature.

Assumptions:	. An acceptable uniform random generator is available.

		. The uniform generator produces numbers in the
		  interval between a and b, inclusive.

		. The generating function, f(x), is available for
		  the desired distribution in a form such that the 
		  domain and range are both in the a-to-b range 
		  (a problem for many or most distributions; see
		  below).

Method:		1. Produce a uniform random number, n1.
		2. Produce f(n1).
		3. Produce a second uniform random number, n2.
		4. If n2 .le. f(n1) then accept n1.
		5. Go to 1 if (4) fails or if another number is sought.

Issues:		. Efficiency. The speed of this method seems to depend
		  on something like the average deviation of f(x) from
		  the median (= (b - a)/2).  Naturally this varies quite
		  a bit for the various distributions and their parameters.

		. Open vs. closed domains and ranges.  Since many
		  distributions are defined for a domain and/or range
		  of plus or minus infinity, this method is limited in
		  accuracy.  The only ways out that occurred to me:

			. Limit the method to truncated versions
			  of distributions.

			. Attempt to normalize n1 by using the
			  ratio:

			    variance(uniform distribution from a to b)
			    ------------------------------------------
			         variance(desired distribution)

    After finding a bit more information from textbooks, it seems that
    the usual methods for doing this kind of transformation include:
    
    	. graphic inversion
    	    . general (can be applied to any distribution)
    	    . need graphic tool
    	. analytic inversion
    	    . possible only for certain distributions
    	. tabular methods
    	    . general
    	    . need to generate table with required precision
    
    In contrast, the trial-and-error method in .0 is general,
    requires only the generating function, but is potentially
    slow.  I'll work out some predictions of speed under different
    conditions, and post them when ready.
                                                          

    I finally found this method in Knuth vol. 2.  It's a variation of
    something called the "discard method", apparently invented by
    Jon von Neumann (sp?).