Random Number (part 2: 6.4–6.6)
Open in the Padhaiko app6.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 ):
- Frequency (Uniformity) Tests: (Kolmogorov–Smirnov test, Chi-Square test).
- Independence Tests: are mutually independent (Gap test, Poker test, Autocorrelation test, Runs test).
6.4.1 Kolmogorov-Smirnov test
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:
- Sort the numbers in ascending order: .
- Compute the one-sided maximum deviations:
- Form the K–S test statistic .
- 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 .
| Aspect | Kolmogorov-Smirnov Test | Chi-Square Test |
|---|---|---|
| Sample Size | Exact for small and moderate | Asymptotic; requires large ( per bin) |
| Data Grouping | Uses exact ungrouped observations | Requires grouping into class intervals |
| Sensitivity | Sensitive to shifts across individual points | Depends on bin count ; tests overall bin frequencies |
6.4.3 Gap test
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.
| Digit Group Size | Pattern Category | Exact Probability | Degrees of Freedom () |
|---|---|---|---|
| Digits | All digits different () | ||
| Digits | One pair () | ||
| Digits | All digits alike () | ||
| Digits | All different () | ||
| Digits | One pair () | ||
| Digits | Two pairs () | ||
| Digits | Three alike () | ||
| Digits | All 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 .
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 :
- Draw .
- Return such that (with ).
Closed-Form Discrete Generators
- Bernoulli(): Return if , else .
- Discrete Uniform on : Return .
- Geometric() (trials until first success): Return .
- Binomial(): Sum independent Bernoulli() variates, or use the inverse CDF table.
6.6 Inversion, rejection, composition and convolution
Four universal techniques transform random numbers into arbitrary continuous random variates .
1. Inverse-Transform Method (Inversion)
Inverse-Transform Theorem
If has a continuous, strictly increasing CDF , setting where and solving for produces variates distributed exactly according to .
| Distribution | CDF | 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 ):
- Generate candidate and an independent .
- 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:
- Draw to pick component index with probability .
- 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 :
- Erlang-(): Sum of i.i.d. variates:
- Approximate Standard Normal (CLT): Sum independent numbers (, ):
(For exact Normal variates, Box–Muller transform uses and .)
Worked Out Examples
1
- Apply the Kolmogorov–Smirnov test at () to test uniformity of the five numbers: .
- 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: .
Since , we do not reject uniformity.
Part 2 — Chi-Square test (, ):
With degrees of freedom, , so uniformity is accepted.
- K–S test: do not reject (uniform).
- Chi-Square test: do not reject (uniform).
2
- In a sequence of random numbers, the subsequence starting at with lag () is:
Perform the autocorrelation test at ().
- 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!
- Autocorrelation test: , inside do not reject .
- Poker test: reject (the digits are not independent).
3
Using the numbers and :
- Generate two Exponential() variates via the inverse-transform method.
- Generate one Erlang-() variate via the convolution method.
- 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 .
- Exponential variates: , .
- Erlang- variate: .
- Discrete variate for : .
Exercises
Practice Exercises — Testing Random Numbers & Variate Generation
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 :
, so we do not reject ; the sample is consistent with .
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 .
, so uniformity is not rejected.
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.
, so the independence hypothesis is not rejected.
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).
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.
Using the inverse-transform method:
- Derive the variate generator for the Weibull() distribution (), and evaluate when , , and .
- 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 :
- Weibull generator gives .
- Triangular generator gives .