Method and apparatus for generating random numbers with improved statistical properties

• US 20030065691A1
• Filed: 04/13/2001
• Published: 04/03/2003
• Est. Priority Date: 04/13/2001
• Status: Active Grant

• Current Assignee: Leidos, Inc. (Leidos Holdings, Inc.)
• Original Assignee: Science Applications International Corporation
• Inventors: Schmidt, Douglas Charles
• Granted Patent: US 6,792,439 B2
• Time in Patent Office: Days
• US Class Current: 708/250
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/582 Pseudo-random number generators

Abstract

A method and an apparatus are provided for combining a plurality of random number generators into a combined random number generator. The outputs of the plurality of generators are interleaved into a combined stream of random numbers selected from each of the plurality of random-number generators. A value of x is calculated by each of the random number generators. Each of the values of x is mapped to a respective arrival time t for each of the random number generators. One of the random number generators having an earliest respective arrival time t is determined. A random number based on the arrival time t is generated.

Claims

1. A computer-implemented method of generating random numbers using a plurality of random number generators, the method comprising:

(1) generating a plurality of independent streams of events;

(2) selecting an event from the independent streams based on an arrival time of the event in relation to arrival times of other events in the plurality of independent streams of events; and

(3) using the selected event to generate a random number.

2. The computer-implemented method of claim 1, wherein act (2) comprises:

(2a) determining an earliest arrival time from among arrival times associated with each of the plurality of independent streams; and

(2b) selecting the event from a stream associated with the earliest arrival time.

3. The computer-implemented method of claim 2, further comprising:

(4) generating another event from one of the independent streams having the selected event;

(5) repeating acts 2 through 4 to produce successive random numbers.

4. A computer-implemented method of generating random numbers using a plurality of random number generators, the method comprising:

(1) using each of the random number generators to calculate a value of x for each of the random number generators;

(2) mapping each of the values of x to a respective time t for each of the random number generators;

(3) determining which one of the random number generators has the time t with a value being less than or equal to the respective time t of each of other ones of the random number generators; and

(4) generating, as output, a random number based on the lowest value of t determined in act (3).

5. The computer-implemented method of claim 4, further comprising:

(5) using the one random number generator determined in act (3) to calculate a new value of x;

(6) mapping the new value of x to a new value of t; and

(7) repeating acts 3 through 4 to generate another random number.

6. The computer-implemented method of claim 4, wherein act (2) comprises:

(a) converting the value of x to a probability number having a value between 0 and 1;

(b) determining a time increment Δ

t_jⁱ based on the probability number; and

(c) determining the time t based on the time increment Δ

t_jⁱ and a previous arrival time.

7. The computer-implemented method of claim 6, wherein act (a) comprises:

(a1) adding I to the value of x to produce a sum; and

(a2) dividing the sum by 1 plus a maximum value c which is generated by a corresponding one of the random number generators to produce the probability number.

8. The computer-implemented method of claim 6, wherein act (b) further comprises:

(b1) determining the time increment Δ

t_jⁱ based on;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{-\ln <br><br>\left(P_j^{\text{\hspace{1em}<br><br>}<br><br>i}\right)}{{\mathrm{\lambda <br><br>}}_i},$

 

where P_jⁱ is the probability number and λ

_i is the average arrival rate for a corresponding one of the random number generators.

9. The computer-implemented method of claim 7, wherein act (b) further comprises:

(b1) determining the time increment Δ

t_jⁱ based on;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{-\ln <br><br>\left(P_j^{\text{\hspace{1em}<br><br>}<br><br>i}\right)}{{\mathrm{\lambda <br><br>}}_i},$

 

where P_jⁱ is the probability number and λ

_i is the average arrival rate for a corresponding one of the random number generators.

10. The computer-implemented method of claim 6, wherein act (b) further comprises:

(b1) determining the time increment Δ

t_jⁱ based on;

Δ

t_jⁱ=−

ln(P_jⁱ), where P_jⁱ is the probability number.

11. The computer-implemented method of claim 4, wherein act (4) comprises:

determining P_i as the random number, wherein;

P_i =e<sup>−

n(t_i−

t<sub>i−

1</sub>)</sup>, where P_i is the i^th random number generated, n is a number of random number generators and t_i−

t<sub>i−

1</sub> is a difference between a value of the time t at an i^th arrival time and a value of the time t at an (i^th−

1) arrival time.

12. The computer-implemented method of claim 4, wherein act (4) comprises:

determining P_i as the random number, wherein;

$P_i={\mathrm{<br><br>}}^{-\left(\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j\right)<br><br>(\text{\hspace{1em}<br><br>}<br><br>t_i-t_{i-1})},$

 

where P_i is the i^th random number generated, λ

_j is an average arrival rate for the j^th random number generator, where j will vary from 1 to n, n is a number of random number generators, and t_i−

t<sub>t−

1</sub> is a difference between a value of the time t at an i^th arrival time and a value of the time t at an (i^th−

1) arrival time.

13. An apparatus for generating random numbers comprising:

a plurality of random number generators;

a plurality of converters, each of the converters being configured to map a respective random number value of x, generated by each of the random number generators to a time t; and

a selector to determine which one of the random number generators has a lowest value for the time t, wherein;

the selector is arranged to generate a random number based on the lowest value for the time t.

14. The apparatus of claim 13, wherein each of the converters comprises:

an xconverter to convert the value of x to a probability number having a value between 0 and 1.

15. The apparatus of claim 14, wherein the xconverter is configured to add 1 to the value of x to produce a sum and the sum is divided by one plus a maximum value c to produce the probability number, wherein c is a maximum value generated by a corresponding one of the random number generators.

16. The apparatus of claim 14, wherein each of the converters further comprises an inter-arrival time calculator configured to receive the probability number from the Xconverter and determine a time increment Δ

t_jⁱ based on;

17. The apparatus of claim 14, wherein each of the converters further comprises an inter-arrival time calculator configured to receive the probability number from the Xconverter and determine a time increment Δ

t_jⁱ based on;

Δ

t_jⁱ=−

ln(P_jⁱ), where P_jⁱ is the probability number.

18. The apparatus of claim 16, wherein each of the converters further comprises an arrival time calculator that is configured to receive the time increment from the inter-arrival time calculator and determine a next arrival time based on the time increment.

19. The apparatus of claim 13, wherein the selector comprises a comparator to compare the arrival times associated with each of the random number generators and to select the arrival time having the lowest value.

20. The apparatus of claim 19, wherein the selector further comprises a producer to receive the arrival time having the lowest value and to generate a random number P_i, wherein:

21. A machine-readable medium having instructions recorded thereon, the instructions comprising:

(1) generating a plurality of independent streams of events;

(2) selecting an event from the independent streams based on an arrival time of the event in relation to arrival times of other events in the plurality of independent streams of events; and

(3) using the selected event to generate a random number.

22. The machine-readable medium of claim 21, wherein act (2) comprises:

(2a) determining an earliest arrival time from among arrival times associated with each of the plurality of independent streams; and

(2b) selecting the event from a stream associated with the earliest arrival time.

23. The machine-readable medium of claim 22, further comprising:

(4) generating another event on one of the independent streams having the selected event;

(5) repeating acts 2 through 4 until a desired quantity of random numbers are produced.

24. A machine-readable medium having instructions recorded thereon, the instructions comprising:

(1) using each of a plurality of random number generators to calculate respective random number values of x;

(2) mapping each of the respective values of x to a respective time t for each of the random number generators;

(3) determining which one of the random number generators has the time t with a value being less than or equal to the respective time t of each of other ones of the random number generators; and

(4) generating, as output, a random number based on the lowest value of t determined in act (3).

25. The machine-readable medium of claim 24, further comprising:

(5) using the one random number generator determined in act (3) to calculate a new value of x;

(6) mapping the new value of x to a new value of t; and

(7) repeating acts 3 through 4 to generate another random number.

26. The machine-readable medium of claim 24, wherein act (2) comprises:

(a) converting the value of x to a probability number having a value between 0 and 1;

(b) determining a time increment Δ

t_jⁱ based on the probability number; and

(c) determining the time t based on the time increment Δ

t_jⁱ and a previous arrival time.

27. The machine-readable medium of claim 26, wherein act (a) comprises:

(a1) adding 1 to the value of x to produce a sum; and

(a2) dividing the sum by 1 plus a maximum value c which is generated by a corresponding one of the random number generators to produce the probability number.

28. The machine-readable medium of claim 26, wherein act (b) further comprises:

(b1) determining the time increment Δ

t_jⁱ based on;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{-\ln <br><br>\left(P_j^{\text{\hspace{1em}<br><br>}<br><br>i}\right)}{{\mathrm{\lambda <br><br>}}_i},$

 

where P_jⁱ is the probability number and λ

_i is the average arrival rate for a corresponding one of the random number generators.

29. The machine-readable medium of claim 27, wherein act (b) further comprises:

(b1) determining the time increment Δ

t_jⁱ based on;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{-\ln <br><br>\left(P_j^{\text{\hspace{1em}<br><br>}<br><br>i}\right)}{{\mathrm{\lambda <br><br>}}_i},$

 

where P_jⁱ is the probability number and λ

_i is the average arrival rate for a corresponding one of the random number generators.

30. The machine-readable medium of claim 26, wherein act (b) further comprises:

(b1) determining the time increment Δ

t_jⁱ based on;

Δ

t_jⁱ=−

ln(P_jⁱ), where P_jⁱ is the probability number.

31. The machine-readable medium of claim 24, wherein act (4) comprises:

determining P_i as the random number, wheren;

P_i=e<sup>−

n(t_i−

t<sub>i−

1</sub>)</sup>, where P_i is the i^th random number generated, n is a number of random number generators and t_i−

t<sub>t−

1</sub> is a difference between a value of the time t at an i^th arrival time and a value of the time t at an (i^th−

1) arrival time.

32. The machine-readable medium of claim 24, wherein act (4) comprises:

determining P_i as the random number, wherein;

$P_i={\mathrm{<br><br>}}^{-\left(\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j\right)<br><br>(\text{\hspace{1em}<br><br>}<br><br>t_i-t_{i-1})},$

 

where P_i is the i^th random number generated, λ

_j is an average arrival rate for the j^th random number generator, where j will vary from 1 to n, n is a number of random number generators, and t₁−

t<sub>t−

1</sub> is a difference between a value of the time t at an i^th arrival time and a value of the time t at an (i^th−

1) arrival time.

33. A computer-implemented method of generating random numbers using a plurality of random number generators, the method comprising:

(1) calculating a random number value of x from each of a plurality of random number generators;

(2) converting each of the values of x to a respective probability number according to a formula;

$P_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{x+1}{c_i+1},$

 

where P_jⁱ is the respective probability number and c_i is a maximum number which can be generated by a respective one of the random number generators;

(3) determining a respective time increment Δ

t_jⁱ for each of the respective random number generators based on the respective probability number P_jⁱ for each of the random number generators according to a formula;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{-\ln <br><br>\left(P_j^{\text{\hspace{1em}<br><br>}<br><br>i}\right)}{{\mathrm{\lambda <br><br>}}_i},$

 

where λ

_i is the average arrival rate for an i^th one of the random number generators;

(4) determining a respective arrival time t for each of the random number generators by adding a current time to the respective time increment Δ

t_jⁱ to produce the respective arrival time t;

(5) determining which one of the random number generators has a smallest value of the arrival time t;

(6) generating a random number P_i according to a formula;

$P_i={\mathrm{<br><br>}}^{-\left(\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j\right)<br><br>(\text{\hspace{1em}<br><br>}<br><br>t_i-t_{i-1})},$

 

where λ

_j is an average arrival rate for the j^th random number generator, where j will vary from 1 to n, n is a number of random number generators, and t<sub>i−

ti−

1</sub> is a difference between a value of the time t at an i^th arrival time and a value of the time t at an (i^th−

1) arrival time, where t_i has the smallest value of the arrival time determined by act 5;

(7) determining a new value of x for the one of the random number generators;

(8) converting the new value of x to the respective probability number according to the formula;

$P_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{x+1}{c_i+1},$

 

where P_jⁱ is the respective probability number and c_i is a maximum number which can be generated by the respective one of the random number generators;

(9) determining the respective time increment Δ

t_jⁱ for the respective random number generator based on the respective probability number P_jⁱ for the one of the random number generators according to the formula;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{-\ln <br><br>\left(P_j^{\text{\hspace{1em}<br><br>}<br><br>i}\right)}{{\mathrm{\lambda <br><br>}}_i},$

 

where λ

_i is the average arrival rate for the respective random number generator;

(10) determining a respective arrival time t for the respective random number generator by adding the current time to the respective time increment Δ

t_jⁱ to produce the respective arrival time t;

(11) repeating acts 5 through 10 to produce a next random number P_jⁱ.

34. The method of claim 33, wherein λ

_i=1.

35. A machine-readable medium having instructions recorded thereon, the instructions comprising:

(1) calculating a random number value of x from each of a plurality of random number generators;

(2) converting each of the values of x to a respective probability number according to a formula;

$P_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{x+1}{c_i+1},$

 

where P_jⁱ is the respective probability number and c_i is a maximum number which can be generated by a respective one of the random number generators;

(3) determining a respective time increment Δ

t_jⁱ for each of the respective random number generators based on the respective probability number P_jⁱ for each of the random number generators according to a formula;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{-\ln <br><br>\left(P_j^{\text{\hspace{1em}<br><br>}<br><br>i}\right)}{{\mathrm{\lambda <br><br>}}_i},$

 

where λ

_i is the average arrival rate for an i^th one of the random number generators;

(4) determining a respective arrival time t for each of the random number generators by adding a current time to the respective time increment Δ

t_jⁱ to produce the respective arrival time t;

(5) determining which one of the random number generators has a smallest value of the arrival time t;

(6) generating a random number P_i according to a formula;

$P_i={\mathrm{<br><br>}}^{-\left(\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_j\right)<br><br>\left(t_i-t_{i-1}\right)},$

 

where λ

_j is an average arrival rate for the j^th random number generator, where j will vary from 1 to n, n is a number of random number generators, and t−

t<sub>t−

1</sub> is a difference between a value of the time t at an i^th arrival time and a value of the time t at an (i^th−

1) arrival time, where t_i has the smallest value of the arrival time t determined by act 5;

(7) determining a new value of x for the one of the random number generators;

(8) converting the new value of x to the respective probability number At according to the formula;

$P_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{x+1}{c_i+1},$

 

where P_jⁱ is the respective probability number and c_i is a maximum number which can be generated by the one of the random number generators;

(9) determining the respective time increment Δ

t_jⁱ for the respective random number generator based on the respective probability number Pn for the one of the random number generators according to the formula;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>t_j^{\text{\hspace{1em}<br><br>}<br><br>i}=\frac{-\ln <br><br>\left(P_j^{\text{\hspace{1em}<br><br>}<br><br>i}\right)}{{\mathrm{\lambda <br><br>}}_i},$

 

where λ

_i is the average arrival rate for the one of the random number generators;

(10) determining a respective arrival time t for the one of the random number generators by adding the current time to the respective time increment Δ

t_jⁱ to produce the respective arrival time t;

(11) repeating acts 5 through 10 to produce a next random number P_i+1.

36. The machine-readable medium of claim 35, wherein λ

_i=1.