14.4 Exponentially Distributed Random Numbers

   

 
Java Number Cruncher: The Java Programmer's Guide to Numerical Computing
By Ronald Mak

Table of Contents
Chapter 14.  Generating Random Numbers

14.4 Exponentially Distributed Random Numbers

Exponentially distributed random values model service times, component lifetimes, and the elapsed time between two random events. The distribution function is

graphics/14equ06.gif


where m is the mean of the distribution.

We'll examine two algorithms for generating exponentially distributed random values. Like the algorithms that generate normally distributed random values, these algorithms also work from uniformly distributed random values. The references at the end of this chapter contain proofs of why they work.

The first algorithm, the logarithm algorithm, is simple to program. If values of u are uniformly distributed, then for u 0, the values of x defined by

graphics/14equ07.gif


are exponentially distributed.

The second algorithm is the von Neumann algorithm, which is named after its discoverer. It is a bit strange :

  1. Set k = 0.

  2. Generate a sequence of uniformly distributed random values u 1 , u 2 , . . . , u n as long as their values are decreasing that is, until u n + 1 > u n .

  3. If n is even, then deliver the value x = u 1 + k. Otherwise, increase k by 1 and go back to the previous step.

The values of x that this algorithm delivers are exponentially distributed.

Listing 14-2a shows class RandomExponential in package numbercruncher. mathutils , which implements these two algorithms.

Listing 14-2a Class RandomExponential , which implements two algorithms for generating exponentially distributed random values.
 package numbercruncher.mathutils; import java.util.Random; /**  * Utility class that generates exponentially-distributed  * random values using several algorithms.  */ public class RandomExponential {     private float mean;     /** generator of uniformly-distributed random values */     private static Random gen = new Random();     /**      * Set the mean.      * @param mean the mean      */     public void setParameters(float mean) { this.mean = mean; }     /**      * Compute the next random value using the logarithm algorithm.      * Requires a uniformly-distributed random value in [0, 1).      */     public float nextLog()     {         // Generate a non-zero uniformly-distributed random value.         float u;         while ((u = gen.nextFloat()) == 0);     // try again if 0         return (float) (-mean*Math.log(u));     }     /**      * Compute the next randomn value using the von Neumann algorithm.      * Requires sequences of uniformly-distributed random values      * in [0, 1).      */     public float nextVonNeumann()     {         int   n;         int   k = 0;         float u1;         // Loop to try sequences of uniformly-distributed         // random values.         for (;;) {             n  = 1;             u1 = gen.nextFloat();             float u     = u1;             float uPrev = Float.NaN;             // Loop to generate a sequence of ramdom values             // as long as they are decreasing.             for (;;) {                 uPrev = u;                 u     = gen.nextFloat();                 // No longer decreasing?                 if (u > uPrev) {                     // n is even.                     if ((n & 1) == 0) {                         return u1 + k;  // return a random value                     }                     // n is odd.                     else {                         ++k;                         break;          // try another sequence                     }                 }                 ++n;             }         }     } } 

Program 14C2 demonstrates both algorithms and, like Program 14C1, prints bar charts with timings. See Listing 14-2b.

Listing 14-2b A demonstration of two algorithms for generating exponentially distributed random values.
 package numbercruncher.program14_2; import numbercruncher.mathutils.RandomExponential; import numbercruncher.randomutils.Buckets; /**  * PROGRAM 14-2: Exponentially-Distributed Random Numbers  *  * Demonstrate algorithms for generating exponentially-distributed  * random numbers.  */ public class GenerateRandomExponential {     private static final int NUMBER_COUNT = 100000;    // 100K     /** counters of random values that fall within each interval */     private Buckets buckets;     private RandomExponential exponential;     private void run(float mean)     {         long startTime;     // starting time of each algorithm         // Initialize the random number generator.         exponential = new RandomExponential();         exponential.setParameters(mean);         // Logarithm algorithm.         startTime = System.currentTimeMillis();         buckets = new Buckets(32);         buckets.setLimits(0, 2);         log();         print("Logarithm", startTime);         // von Neumann algorithm.         startTime = System.currentTimeMillis();         buckets = new Buckets(13);         buckets.setLimits(0, 12);         vonNeumann();         print("von Neumann", startTime);     }     /**      * Print the results of an algorithm with its elapsed time.      * @param label the algorithm label      * @param startTime the starting time      */     private void print(String label, long startTime)     {         long elapsedTime = System.currentTimeMillis() - startTime;         System.out.println("\n" + label + " (" + elapsedTime +                            " ms):\n");         buckets.print();     }     /**      * Invoke the logarithm algorithm.      */     private void log()     {         for (int i = 0; i < NUMBER_COUNT; ++i) {             buckets.put(exponential.nextLog());         }     }     /**      * Invoke the von Neumann algorithm.      */     private void vonNeumann()     {         for (int i = 0; i < NUMBER_COUNT; ++i) {             buckets.put(exponential.nextVonNeumann());         }     }     /**      * Main.      * @param args the array of program arguments      */     public static void main(String args[])     {         float mean = 0.5f;         GenerateRandomExponential test =                                 new GenerateRandomExponential();         test.run(mean);     } } 

Output:

 Logarithm (330 ms):  0  11697: **************************************************  1  10536: *********************************************  2   9197: ***************************************  3   8012: **********************************  4   6986: ******************************  5   6406: ***************************  6   5447: ***********************  7   4910: *********************  8   4400: *******************  9   3894: ***************** 10   3332: ************** 11   2943: ************* 12   2591: *********** 13   2373: ********** 14   1973: ******** 15   1825: ******** 16   1522: ******* 17   1400: ****** 18   1180: ***** 19   1158: ***** 20    968: **** 21    845: **** 22    689: *** 23    696: *** 24    595: *** 25    530: ** 26    475: ** 27    411: ** 28    363: ** 29    306: * 30    254: * 31    236: * von Neumann (550 ms):  0  31690: **************************************************  1  22331: ***********************************  2  15291: ************************  3  10374: ****************  4   6934: ***********  5   4549: *******  6   3087: *****  7   2009: ***  8   1320: **  9    868: * 10    527: * 11    365: * 12    238: 

Screen 14-2 shows two screen shots of the interactive version of Program 14C2 in action.

Screen 14-2. Screen shots of the interactive version of Program 14C2, showing the logarithm algorithm and von Neumann's algorithm.

graphics/14scr02a.jpg

graphics/14scr02b.jpg


   
Top
 


Java Number Cruncher. The Java Programmer's Guide to Numerical Computing
Java Number Cruncher: The Java Programmers Guide to Numerical Computing
ISBN: 0130460419
EAN: 2147483647
Year: 2001
Pages: 141
Authors: Ronald Mak

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net