RandomNumberGenerators

From Nsnam
Revision as of 07:13, 30 May 2009 by Craigdo (Talk | contribs) (Hypothesis Testing)

Jump to: navigation, search

Random Number Generator Validation Tests

Random numbers are sequences of numbers that contain no recongnizable patterns or regularities, biases or correlations. True randomness arises out of physical processes, such as Brownian motion, roulette wheels or dice, or can result from sensitive dependence on initial conditions (chaols). Random numbers generated by computers can simulate this property but do ultimately have repeating patterns. Algorithms that implement this behavior are called pseudo-random number generators.

Ns-3 can simulate many interesting deterministic processes, but if real phenomena that are governed by unpredictable events are to be included, the underlying source of unpredictability must be simulated by pseudo-random numbers. The different applications of randomness have led to many different methods for generating random numbers and also the requirement for various distributions of generated random numbers.

Since the goal of a stocahstic simulation is ultimately to mimic the behavior of some system that is really governed by a random process, the fidelity of the simulation is directly related to the fidelity of the random number generator driving the simulated process. Mathematician Robert Coveyou titled a paper written in 1969, "the generation of random numbers is too important to be left to chance."

There are many test suites for testing random number generator implementations. These range from the trivial to the incredibly sophisticated. Some of the most sophisticated tests are related to random number generators used in cryptographic appliations. For example, the U.S. National Institute of Standards and Technology (NIST) has developed, implemented and evaluated a suite of sixteen statistical tests for random number generators (see http://csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html). NIST provides a standards-based procedure for formal validation of a random number generator called the Random Number Generator Validation System (RNGVS). This level of testing is well behond the scope of ns-3 validation testing.

The random number generator used in ns-3 is the Combined Multiple Recursive Generator (MRG) MRG32k3a from Pierre L'Ecuyer (see http://www.iro.umontreal.ca/~lecuyer/myftp/papers/streams00.pdf). This generator is very well tested and has found a home in products such as MATLAB.

Our tests are relatively high-level tests designed to validate that the ns-3 implementation of the RNG and the various generated distributions behaves according to generally accepted statistical definitions.

Basic Concepts Used in the Tests

Every measurement of a random variable can be considered an individual. Repeated measurements genearate an aggregate of results called the population. If an infinite number of measurements is made, the result is called the parent population. The parent population is defined by a number of parameters. The basic goal of statistical analysis is to make an estimate of the parameters of the parent population along with some indication of the uncertainty of that estimate. The estimates are called statistics and are calculated from measured data.

Implicit in this is the fact that popultions show variation. The study of variation requires the concept of frequency distribution. Given a random variable, called the variate, a frequency distribution specifies how often that variate takes on each of its possible values. A histogram is a commonly used tool for visualizing frequency distributions.

If a frequency distribution is described by an infinitesimal proportion of the population that resides in an infinitesimal interval, that differential description is called the probability density function (PDF). If this differential function is integrated, a cumulative density function (CDF) results. This function describes the proportion of the population for which the variate is less than the upper limit of integration.

An almost intuitive parameter used to describe a population is the mean or arithmetic average,

Rng average.gif.

The deviation is the absolute value of the difference beteeen a particular measurement and some value, generally the average. The variance is defined as the average value of the square of the individual deviations,

Rng variance.gif.

The standard deviation is the square root of the variance,

Rng standard deviation.gif.

Hypothesis Testing

The goal of hypothesis testing is to make a determination that some aggregate of measured data match a model well enough to accept the data as, in fact, matching the model.

Technically, we propose a "Null Hypothesis" that the data do match the model. If we determine this is the case, we will have determined that the data and the model are drawn from the same population distribution. We also propose an "Alternate Hypothesis" that the data do not match.

We first histogram the measurement data to establish an esitmate for the probability density function (PDF). We use a known PDF to create a matching histogram that represents the parent population PDF. Pearson's test, also known as the chi-squared test is often used to come up with a quantitative description of the differences between the measured PDF and the parent population PDF.

In this statistic, the measured data is aggregated into a histogram indicated by the n variable below. The model histogram is aggregated into a histogram indicated by the m variable. The square root of the m variable is the standard deviation of the indexed bin based on Poisson statistics.

Rng chi squared.gif.

The chi-squared statistic is basically the sum of the squared deviations divided by the

The Simple Frequency Test or Test for Uniform Distribution

The goal of this test is to ensure that

The Pairs Frequency Test

  1. Uniform Random Number Generator
  2. Normal Random Number Generator
  3. Exponential Random Number Generator
  4. Pareto Random Number Generator

The following is an illustration of how a failure would appear.

  1. Confused Random Number Generator

Craigdo 06:27, 30 May 2009 (UTC)