PadhaikoAll subjects

Random Number (part 2: 6.4–6.6)

Simulation and Modeling (ENCT 353)

Open in the Padhaiko app

6.4 Tests for random numbers

Before using any pseudo-random number generator in a simulation, we test the generated stream against two statistical null hypotheses at significance level (commonly ):


6.4.1 Kolmogorov-Smirnov test

Definition

Kolmogorov–Smirnov (K–S) Test

The Kolmogorov–Smirnov (K–S) test checks uniformity by comparing the theoretical cumulative distribution function (for ) against the empirical CDF . It works directly on ungrouped data and is especially suited for small sample sizes ().

Procedure:

  1. Sort the numbers in ascending order: .
  2. Compute the one-sided maximum deviations:
  1. Form the K–S test statistic .
  2. Compare with the critical value for sample size : if , do not reject (uniformity is accepted); if , reject .

6.4.2 Chi-Square () test

The Chi-Square () goodness-of-fit test partitions into mutually exclusive intervals (typically equal-width sub-intervals with expected count ) and compares observed counts against expected counts :

Under , approximately follows a distribution with degrees of freedom. If , do not reject (uniformity holds); otherwise reject .

AspectKolmogorov-Smirnov TestChi-Square Test
Sample SizeExact for small and moderate Asymptotic; requires large ( per bin)
Data GroupingUses exact ungrouped observationsRequires grouping into class intervals
SensitivitySensitive to shifts across individual pointsDepends on bin count ; tests overall bin frequencies

6.4.3 Gap test

Definition

Gap Test for Independence

The gap test counts the number of consecutive random numbers (the gap length ) that lie outside a chosen target interval between two successive occurrences inside . Let be the interval length.

Under independence and uniformity, the theoretical probability of a gap of exact length is a shifted Geometric distribution:

Notice that a gap of occurs when two consecutive numbers both fall in . Using observed gaps, we compare the empirical cumulative gap frequencies with using the K–S statistic (or group tail gaps into classes and apply a test).


6.4.4 Poker’s method

The Poker test tests independence among consecutive digits inside each random number (or groups of consecutive random digits) by counting digit patterns analogous to poker hands and comparing observed frequencies against multinomial probabilities via a test.

Theoretical Probabilities for 3-Digit and 4-Digit Poker Tests
Digit Group SizePattern CategoryExact ProbabilityDegrees of Freedom ()
DigitsAll digits different ()
DigitsOne pair ()
DigitsAll digits alike ()
DigitsAll different ()
DigitsOne pair ()
DigitsTwo pairs ()
DigitsThree alike ()
DigitsAll alike ()

6.4.5 Testing for auto correlation

The autocorrelation test measures linear dependence between numbers separated by a constant lag , starting at index (), where is the largest integer satisfying .

Definition

Autocorrelation Test Statistic

For start index , lag , and consecutive lag pairs (), the sample autocorrelation estimator and its standard error are:

The standardized test statistic is:

At significance level , we do not reject independence () if (e.g., for ).


6.5 Generating discrete distribution

To simulate a discrete random variable taking values with probability mass function and cumulative distribution function :

  1. Draw .
  2. Return such that (with ).

Closed-Form Discrete Generators


6.6 Inversion, rejection, composition and convolution

Four universal techniques transform random numbers into arbitrary continuous random variates .

1. Inverse-Transform Method (Inversion)

Theorem

Inverse-Transform Theorem

If has a continuous, strictly increasing CDF , setting where and solving for produces variates distributed exactly according to .

Common Continuous Distributions via Inverse Transform
DistributionCDF Inverse-Transform Formula (using )
Uniform
Exponential() () (or )
Weibull()
Pareto() ()

2. Acceptance–Rejection Method

Used when has no closed form (e.g., Beta, Gamma, truncated Normal), given a target PDF bounded by where is an easy-to-sample proposal PDF ( for all ):

  1. Generate candidate and an independent .
  2. Accept if ; otherwise reject and repeat from step 1.

For bounded on , take () and accept if .

3. Composition Method

Used when the target CDF or PDF can be expressed as a convex mixture of simpler distributions:

  1. Draw to pick component index with probability .
  2. Draw and generate from (e.g., Laplace / double-exponential or piecewise-linear PDFs).

4. Convolution Method

Used when the target random variable is the sum of independent random variables :

(For exact Normal variates, Box–Muller transform uses and .)


Worked Out Examples

Example 1

1

  1. Apply the Kolmogorov–Smirnov test at () to test uniformity of the five numbers: .
  2. A generator produces numbers sorted into equal sub-intervals with observed frequencies . Test uniformity using the Chi-Square () test at ().

Part 1 — K–S table on sorted data (): Sorting ascending: .

Kolmogorov-Smirnov Computation Table

Since , we do not reject uniformity.

Part 2 — Chi-Square test (, ):

With degrees of freedom, , so uniformity is accepted.

Answer:
  1. K–S test: do not reject (uniform).
  2. Chi-Square test: do not reject (uniform).
Example 2

2

  1. In a sequence of random numbers, the subsequence starting at with lag () is:

Perform the autocorrelation test at ().

  1. A -digit Poker test on numbers yields all-different, one-pair, and all-alike triplets. Test independence at ().

Part 1 — Autocorrelation test (): The largest integer such that is (so there are consecutive pairs).

Since , there is insufficient evidence of lag- autocorrelation.

Part 2 — Poker test (, -digit categories): Expected counts: , , .

Since , we reject independence!

Answer:
  1. Autocorrelation test: , inside do not reject .
  2. Poker test: reject (the digits are not independent).
Example 3

3

Using the numbers and :

  1. Generate two Exponential() variates via the inverse-transform method.
  2. Generate one Erlang-() variate via the convolution method.
  3. Generate one variate from the discrete distribution , , using .

Inversion for Exponential():

  • For : .
  • For : .

Convolution for Erlang-(): An Erlang- variate is the sum of independent variates:

Discrete Inverse Transform (): Cumulative probabilities: , , . Since , we output .

Answer:
  1. Exponential variates: , .
  2. Erlang- variate: .
  3. Discrete variate for : .

Exercises

Practice Exercises — Testing Random Numbers & Variate Generation

Question 1

Use the Kolmogorov–Smirnov test at () to test whether the numbers are uniformly distributed on .

Sorting and computing and for : Sorted values: , , .

  • : ; .
  • : ; .
  • : ; .

Comparing against critical value :

Answer:

, so we do not reject ; the sample is consistent with .

Question 2

Forty random numbers () are placed into equal intervals with observed frequencies . Perform a Chi-Square test at ().

Computing expected frequencies and : Expected count per interval: (, valid).

Decision at degrees of freedom: Since , do not reject .

Answer:

, so uniformity is not rejected.

Question 3

In a -digit Poker test on numbers, the two smallest classes (two pairs, three alike, and all alike, with combined probability ) are merged into a single "rare patterns" class so all expected counts exceed . The observed counts are: All different , One pair , Rare patterns . Test independence at ().

Computing expected counts ():

  • All different: .
  • One pair: .
  • Merged rare patterns: .

Computing and comparing with :

Since (), do not reject independence.

Answer:

, so the independence hypothesis is not rejected.

Question 4

Explain the gap test procedure for testing independence of random numbers, and briefly contrast acceptance–rejection, composition, and convolution methods for generating continuous random variates.

Gap Test Procedure: Choose an interval with length . Scan the sequence and count the gap length (number of consecutive values outside ) between consecutive hits inside . Compare the empirical gap-length distribution against the theoretical shifted Geometric distribution using a K–S or test.

Contrasting Variate Generation Methods:

  • Acceptance–Rejection: Samples from an easy bounding proposal and keeps candidate with probability —ideal when is not closed-form.
  • Composition: Writes as a mixture, randomly chooses component , then samples from .
  • Convolution: Generates by summing independent variates (e.g., Erlang- from Exponentials, or Normal via sum of Uniforms).
Answer:

The gap test compares observed intervals between hits in against . Acceptance–rejection uses a bounding envelope, composition samples from a probability mixture, and convolution sums independent variates.

Question 5

Using the inverse-transform method:

  1. Derive the variate generator for the Weibull() distribution (), and evaluate when , , and .
  2. Derive the generator for the right-triangular PDF on , and evaluate when .

Part 1 — Weibull Inverse Transform (): Setting :

Substituting :

Part 2 — Right-Triangular Inverse Transform (): Integrating from to :

Setting gives . For :

Answer:
  1. Weibull generator gives .
  2. Triangular generator gives .
← Random Number (part 1: 6.1–6.3)Verification and Validation of Simulation Models →