US4499551A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Rapid generation of discrete random variates from general distributions
Assignee: Nokia Bell Labs
•
Filing: 1982-09-27
•
Granted: 1985-02-12
•
Expires: 2002-09-27
Abstract
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.
Inventors
- 👤 Amalie J. Frank
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:33
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/58
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
186 words
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.
Claim 2
Dependent Claim
186 words
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.
Claim 3
Dependent Claim
26 words
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.
Claim 4
Dependent Claim
48 words
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.
Claim 5
Dependent Claim
30 words
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.
Claim 6
Dependent Claim
42 words
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.
Claim 7
Dependent Claim
36 words
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.
Claim 8
Dependent Claim
30 words
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.
Claim 9
Independent Claim
190 words
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.
Claim 10
Independent Claim
190 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1988-02-12 | 1988-08-13 | 1989-02-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-02-12 | 1992-08-13 | 1993-02-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-02-12 | 1996-08-13 | 1997-02-12 | $7700.00 | Window Closed / Lapsed |