Brief
Implement four random number generators: RANDU (a famously flawed generator), a 64-bit LCG (linear congruential generator, x -> a*x + c modulo 2^64), xorshift and PCG32, vectorised in NumPy uint64. Write a small test battery that looks for hidden patterns: chi-square (are values evenly spread), serial (are consecutive pairs evenly spread), birthday spacings, the 3D-plane/spectral test (RANDU's consecutive triples fall on just 15 planes in 3D) and Kolmogorov-Smirnov (does the sample match the target distribution). On top, build three samplers: inverse-CDF (push uniform numbers through the inverse cumulative distribution function), the alias method (constant-time sampling from a discrete distribution using a precomputed table) and rejection sampling (propose a value and accept it with a computed probability). Add an exponentially tilted importance sampler for Gaussian tail probabilities: draw samples shifted toward the rare tail, then reweight them so the estimate stays unbiased.
Approach
Start with RANDU, because its flaw is pure algebra. It computes . Since , squaring gives , so every output is fixed by the two before it:
Divide by and you get for a whole number . With every in , only are possible: 15 parallel planes. Your 3D test has to see that structure without being told the formula.
PCG32 hides the LCG inside it. The state still moves by , but the output is a scrambled view of the old state: xor the state with itself shifted right 18 bits, shift right 27 bits, keep 32 bits, then rotate right by the top 5 bits of the state (). Get the order of operations exactly as in the reference code, or you will be close but never bit-exact.
For the rare event, plain Monte Carlo is hopeless: , and 1% relative error needs about samples. Instead draw and weight each hit by the density ratio:
where is the standard normal tail. Derive the variance yourself before trusting it; it decides your sample budget.
Where people get stuck
- Silent float promotion. In NumPy 1.x, mixing uint64 with a Python int or int64 can turn the whole expression into float64 and destroy the low bits. Keep every constant as
np.uint64and check the dtype after each step. - Rotations by zero. The rotate uses a left shift by
(-rot) & 31. Do it in 64-bit and mask to 32 bits afterwards, so a shift of 32 never happens. - Uniforms that hit 0. Dividing a 32-bit integer by can give exactly 0, and an inverse CDF then returns infinity. Use .
- Multiple testing. Five tests on four generators means some p-values below 0.05 by chance alone. A tiny p-value counts; a single 0.03 does not.
- One lucky run. With the shift the formula above gives a relative standard deviation of about 0.83% at . That is close to the 1% target, so roughly one run in five misses it (measured locally: 78% of 200 seeds landed inside). Check across many seeds, and consider a better proposal.
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- The battery flags RANDU with p < 1e-10 while PCG32 passes; PCG32 output is bit-exact with the reference implementation; P(Z > 6) is estimated within 1% using at most 10^5 samples. Record the median relative error over seeds with `python tools/mlarena.py record PM-I01 "<relative error>"`.
- Battery p-values on NumPy's PCG64 pass a uniformity check, so a failure means the generator, not the test.
- At least 95 of 100 independent seeds land within 1% of scipy.stats.norm.sf(6) at n = 10^5.
Side quests
Terms in plain words
- LCG (linear congruential generator)
- A random number generator that repeatedly computes x = a*x + c modulo m; fast, but with patterns that tests can detect.
- Test battery and p-value
- A set of statistical tests run on a generator's output; a tiny p-value means the output is very unlikely to be truly random.
- Importance sampling
- Sampling from a different distribution that hits the region you care about more often, then reweighting each sample to correct for that.
- Exponential tilting
- A specific way to build the importance distribution by multiplying the density by e^(t x), which shifts a Gaussian toward its tail.
- Alias method
- A table-based trick that samples from any discrete distribution in constant time per draw.
Why it rates ★★☆☆☆
Solid fundamentals. The importance-sampling result is the part that transfers to ML.