9.1 隨機數產生器#

概念說明#

電腦是決定性的機器，照理說產生不出「真正的隨機」。所謂偽隨機數產生器（PRNG），是一個確定性演算法：給定種子（seed），之後的整個數列就完全確定。好的 PRNG 要求：數列看起來像 iid 均勻隨機（通過統計檢定）、週期夠長、速度快、可重現（種子相同則數列相同——這對科學可重現性是優點而非缺點）。

經典教材是線性同餘產生器（Linear Congruential Generator）：

X_{n+1} = (a·Xₙ + c) mod m

選好參數（如 Numerical Recipes 的 a=1664525, c=1013904223, m=2³²）就能得到可用的數列。但 LCG 有已知缺陷：低位元週期短、連續取值在多維空間會落在少數超平面上（有名的 RANDU 醜聞）。現代標準是 Mersenne Twister（Python random 模組的預設，週期 2¹⁹⁹³⁷−1）與 xoshiro 系列，統計品質遠勝 LCG；但它們都不是密碼學安全的——看幾百個輸出就能反推內部狀態。安全場景必須用 CSPRNG（如 Python 的 secrets 模組，底層 OS 熵源）。

關鍵區分一句話：模擬要快且可重現 → random/numpy.random；抽金鑰、token、抽獎涉及金錢 → secrets。

演算法步驟#

LCG 產生 [0,1) 均勻亂數：

選定模數 m（通常 2³²）、乘數 a、增量 c（需滿足 Hull-Dobello 條件以達滿週期）。
設種子 X₀。
反覆：X ← (aX + c) mod m；輸出 X/m 作為 [0,1) 的浮點亂數。

品質檢驗的基本流程：

頻率檢定：各區間的出現次數是否均勻（卡方檢定，見 9.3 節）。
序列檢定：相鄰對 (xᵢ, xᵢ₊₁) 在平面上的分布是否均勻（視覺化最直觀）。
週期檢定：數列多久開始重複。

Python 程式碼範例#

import random, secrets
import numpy as np

# --- 自製 LCG ---
class LCG:
    def __init__(self, seed=1):
        self.a, self.c, self.m = 1664525, 1013904223, 2**32
        self.x = seed
    def next(self):
        self.x = (self.a * self.x + self.c) % self.m
        return self.x
    def random(self):
        return self.next() / self.m

lcg = LCG(seed=42)
vals = [lcg.random() for _ in range(100_000)]
print(f"LCG 平均 {np.mean(vals):.4f}（理論 0.5），"
      f"標準差 {np.std(vals):.4f}（理論 {1/np.sqrt(12):.4f}）")

# --- LCG 的三維超平面缺陷視覺化 ---
x = np.array([LCG(i).random() for i in range(1, 3001)])
# 用同一狀態連續取三個點
lcg = LCG(1)
triple = np.array([[lcg.random() for _ in range(3)] for _ in range(2000)])
print("三連值排序後的獨特平面角度數（LCG<10，好 PRNG≈全部）：")
proj = triple[:, 0] + triple[:, 1] * 1e5
print(f"  投影獨特值比例 ≈ {len(set(np.round(proj, 6))) / len(proj):.2f}")

# --- 對照 Mersenne Twister ---
rng = np.random.default_rng(42)
mt = rng.random(100_000)
print(f"MT19937 平均 {mt.mean():.4f}")

# --- 均勻性卡方檢定（頻率檢定） ---
def chi2_uniform(data, bins=20):
    obs, _ = np.histogram(data, bins=bins, range=(0, 1))
    exp = len(data) / bins
    return ((obs - exp)**2 / exp).sum()

print(f"LCG 卡方統計量 = {chi2_uniform(vals):.1f}（自由度 19，95% 臨界 ≈ 30.1）")
print(f"MT  卡方統計量 = {chi2_uniform(mt):.1f}")

# --- 密碼學安全 vs 一般用途 ---
token_insecure = random.randrange(2**32)      # 可被預測
token_secure = secrets.randbits(128)          # OS 熵源
print(f"普通亂數 token: {token_insecure:#010x}")
print(f"安全 token:     {token_secure:#034x}")

# --- 可重現性示範 ---
random.seed(7); print("seed=7 第一次:", [random.random() for _ in range(3)])
random.seed(7); print("seed=7 重跑:  ", [random.random() for _ in range(3)])

複雜度與安全性分析#

LCG 每次 O(1)（一次乘法加法取模），週期至多 m（2³² 約 43 億）；Mersenne Twister 每次 O(1) 攤提，週期 2¹⁹⁹³⁷−1，通過大多數統計檢定，但不是 CSPRNG：觀察 624 個連續輸出即可完全重建狀態並預測後續——這是安全考量的經典反例。secrets / OS 熵源（getrandom）提供密碼學安全保證，成本較高。統計檢定的判讀：卡方統計量在自由度 k 下應落在合理區間，持續偏大代表分布不均、持續偏小（過於完美）反而暗示相關性問題。進階檢定工具：TestU01 的 BigCrush 套件、NIST SP 800-22（密碼學用途）。實務守則總結：(1) 科學模擬一律設 seed 以保可重現；(2) 平行模擬用獨立 seed 流（numpy 的 SeedSequence.spawn），避免流重疊；(3) 任何安全用途禁用 random。

練習#

用本節 LCG 實作「擲兩顆骰子 10 萬次」，統計點數和的分布，與理論機率（8.2 練習 1 的數列）比對最大偏差。
用「中間平方法」（取平方後的中間位數）產生亂數，觀察它為何容易掉進零或短循環，記錄出現的週期長度。
模擬 RANDU（a=65539, c=0, m=2³¹）：取連續三個值畫 3D 散點圖（matplotlib 的 scatter 投影到 15 個平面），找出傳說中的 15 個超平面。