Rapid generation of discrete random variates from general distributions

• US 4,499,551 A
• Filed: 09/27/1982
• Issued: 02/12/1985
• Est. Priority Date: 09/27/1982
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Frank, Amalie J.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US06/423,856
• Time in Patent Office: 869 Days
• Field of Search: 364/717, 331/78, 178/22.19
• US Class Current: 708/250
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators

Abstract

Method and apparatus for the rapid generation of discrete random variates, of a general probability distribution, from random variates of a uniform distribution uses simple logic and moderate storage requirements. Access to a first table at an address which is a function of a uniform variate gives the desired variate value directly for a large percentage of cases and in the remaining cases the desired variate value is obtained by an indexed search of a second table of cumulative distribution function values. Results of greater precision are realized in faster execution times with less logic complexity and reduced storage bulk as compared with prior methods and apparatus.

Claims

1. A generator of discrete random variates comprising

a source of random numbers suppliable on demand from a uniformly distributed number set for use in generating addresses;

a first random access memory storing mappings of said addresses into a set of numerical values corresponding to a preselected discrete probability distribution, each numerical value covering a range of addresses, and coded addresses corresponding to transitional values in said probability distribution;

a second random access memory storing transitional values only of a cumulative distribution function derived from said probability distribution;

means responsive to the address corresponding to a selected random number from said source for accessing said first memory to retrieve a random variate directly, and for accessing said second memory using said coded address; and

means responsive to a coded address corresponding to a selected random number from said source for comparing said selected random number with successive cumulative distribution function values from said second memory in increasing order until the cumulative distribution function value next higher than said random number is determined, the random variate corresponding to such next highest value being the valid output random variate.

2. The generator of random variates defined in claim 1 in which said first and second random access memories are preprogrammed according to said preselected probability distribution.

3. The generator of random variates defined in claim 2 in which said first and second random access memories are preprogrammed according to the Poisson probability distribution function of the form ##EQU2## where P=Poisson probability,

λ

=mean value of the Poisson distribution,

n=number of events, and

e=base of natural logarithms.

4. The generator of random variates defined in claim 1 in which said means for comparing determines whether one input value is numerically greater than or equal to another input value.

5. The generator of random variates defined in claim 1 further comprising means for selecting a fixed segment of a fixed multiple of a random number from said source and means for generating a fixed multiple of a random number from said source.

6. The generator of random variates defined in claim 1 further comprising means for offsetting a truncated narrow range of cumulative distribution function values and means for generating a truncated narrow range of cumulative distribution function values.

7. The generator of random variates defined in claim 1 further comprising means for offsetting numerical values at coded addresses by the number of transitional cumulative distribution values chosen for truncation.

8. A method for generating discrete random variates comprising the steps of:

supplying on demand a random number selected from a uniformly distributed number set;

forming an address for a first random access memory from a fixed segment of a fixed multiple of said random number;

addressing said first random access memory with said address, said first memory storing mappings of said addresses into a set of numerical values corresponding to a predetermined discrete probability distribution, each numerical value covering a range of addresses, and coded addresses corresponding to transitional values in said probability distribution;

reading out the desired random variate directly from said first memory where said address is uncoded;

addressing a second random access memory where said address is coded, said second memory storing transitional values only of a cumulative distribution function derived from said probability distribution;

comparing said selected random number with successive transitional cumulative distribution function values from said second memory until the cumulative distribution function value next higher than the selected random number is found; and

reading out the desired random variate corresponding to said next higher cumulative distribution value as the valid output random variate.