為什麼一台確定性的機器會想要隨機性
在上一級的尾聲，你看見了網格法撞上的高牆：要在一個區域上積分，就鋪一張每軸 m 個點的網格，而在 d 維裡這要花 m^d 個點——也就是維度詛咒。大約到第五、六維，每一條經典求積法則都乾脆死透。本整級就圍繞著那唯一能直接穿牆而過的方法打造：你不再在規律的網格上行軍走過空間，而是隨機擲飛鏢，再把擊中的東西平均起來。這就是蒙地卡羅，它的誤差只以 O(1/sqrt(N)) 下降——在一維裡慢得令人痛苦——但關鍵在於，那個速率完全不依賴於維度。
可是隨機擲飛鏢預設了你擁有隨機性，而這裡有個尷尬的真相，正是本篇存在要面對的：電腦一點也沒有。它執行的每一條指令都是確定性的。餵它相同的輸入，它每一次都回傳相同的輸出——而這正是讓它成為可靠計算機的那個性質。矽晶片裡並沒有藏著真正的擲硬幣。所以在本級任何方法能跑起來之前，我們得先回答一個尖銳的問題：如果機器本身根本不會被驚到，那些「隨機」數究竟從哪裡來？
答案是一場刻意而有用的造假。我們放棄追求真正的隨機，改而製造一個序列：它完全由一條公式決定，行為上卻在統計意義下像隨機數——不結團、看不出樣式、在每一段範圍裡都有恰當的比例。這樣的序列稱為偽隨機，而那個吐出它的小演算法，就是偽隨機數生成器，簡稱 PRNG。要牢牢記住的是那個字首：偽（pseudo）。這些數只是在假裝而已。
走進最簡單的生成器：一條公式，餵回它自己
要看清假隨機是怎麼造出來的，最乾淨的途徑是最古老的主力——線性同餘生成器（LCG）。它只保留一個整數狀態，稱它為 x_n，再用一行你親手就能算的式子產生下一個：x_{n+1} = (a*x_n + c) mod m。乘上一個常數 a，加上一個常數 c，再取除以模數 m 後的餘數，好讓值繞回到 0 到 m-1 的範圍裡。要把每個整數變成 [0, 1) 裡的一個分數，你只要除以 m。這就是整台引擎——一次乘法、一次加法、一次取餘。
Linear congruential generator (LCG):
x_{n+1} = (a * x_n + c) mod m
u_{n+1} = x_{n+1} / m # a fraction in [0, 1)
seed: x_0 chosen by the user
a, c, m: fixed constants of the generator
Same seed -> exactly the same sequence, forever.注意是什麼在做工：每個輸出都被直接餵回去當成下一個輸入。這串流是一條長鏈，每一個環節都被它前一個強迫決定。這正是為什麼那第一個值如此重要。起始狀態 x_0 就是種子，單憑它就選定了你會得到哪一個序列。把種子固定下來，你就把整條無窮的串流固定下來——明天給生成器同一顆種子，它就一字不差地、以同樣的順序重播同樣的數。這不是錯誤；我們稍後會看到，它是整套方案最有價值的特性之一。
因為狀態是一個只能取 m 種可能值的整數，這條鏈最終一定會重訪一個它已經產生過的值——而它一這麼做，整個序列就從那裡開始重複。繞回之前的長度就是週期。一個 a、c、m 都選得好的 LCG 能達到最大週期 m，在循環之前把每個值各拜訪一次。一個草率挑選的，週期可能短得可笑，或者更糟，在輸出裡留下刺眼的結構。著名的警世故事是 IBM 在 1960 年代的 RANDU：把它的「隨機」三元組畫成三維空間裡的點，竟然全部整整齊齊落在僅僅十五個平行平面上。它在一維裡看起來隨機，在三維裡卻明顯像晶體一樣。
這裡「好的」隨機性究竟是什麼意思
既然我們已放棄真正的隨機，就需要一個誠實的替代標準。我們不問這些數是不是「真的」隨機——它們可被證明並非如此——我們問的是：對於手頭的用途，它們是否在統計上與隨機無法區分。具體說，一個好的生成器要三件事：均勻分布（[0, 1) 的每一個子區間都拿到它應得的份額）、獨立性（知道過去的值，對下一個值給不出有用的線索）、以及一個長到在你的計算裡永遠走不到盡頭的週期。RANDU 的災難就在第二項上慘敗：它的值單獨看是均勻的，但三個一組地看卻劇烈相依。
在沒有一個真正隨機的對照可比的情況下，你要怎麼檢查這件事？你讓這條串流接受一整套統計檢驗——數遞增值的連段出現的頻率、量度許多落後距下的相關性、把值裝進高維立方體的格子裡，以揪出像 RANDU 那樣的隱藏平面。現代的檢驗套組（TestU01 的「BigCrush」套組是標準）會跑數十項這樣的探測。一個生成器被宣告為好，不是因為它真正隨機，而是因為它撐過了我們所知該怎麼寫的每一項檢驗。這是個更謙卑、也更誠實的主張，而且是正確的那個。
今天多數語言伸手去拿的生成器是梅森旋轉演算法（Mersenne Twister）。它保留一個龐大的狀態（624 個整數，而非一個），並用一條更精巧的遞迴去攪動它，因而買到一個天文般長的週期——2^19937 - 1，遠長於任何計算會用掉的量——以及跨許多維度的優秀均勻性，於是避開了沉掉 RANDU 的那種平面假象。它是大量科學蒙地卡羅背後的主力。不過誠實要求一條註腳：梅森旋轉並非密碼學安全的。觀察夠多它的輸出，你就能重建它的內部狀態並預測其餘。對我們的用途——積分、模擬、取樣——這無關緊要；但若用來產生秘密金鑰，這就是個嚴重的瑕疵。讓生成器配合工作。
確定性背後隱藏的好處
把「這些數其實不隨機」讀成一個需要道歉的弱點，是很誘人的。實情恰恰相反。確定性——同一顆種子重播一字不差的串流這個事實——正是讓「用隨機性做科學計算」這件事可信賴的關鍵。一個使用真正物理隨機性的蒙地卡羅模擬永遠無法重跑；如果它在第九個小時崩潰，或產出一個可疑的結果，你永遠無法重現那一次確切的運行來除錯。而一次偽隨機的運行，只要記下種子，就能逐位元地重播。
這就是可重現性，而在本級裡它不是奢侈品——它是「實驗」與「猜測」之間的分野。在論文裡報告一個蒙地卡羅結果，讀者必須能重建你確切的數字；記下種子，他們就能。要公平地比較兩個演算法，就餵給它們同一條隨機串流，使唯一的差異是演算法本身、而非抽籤的運氣——這個技巧叫做共同隨機數，它悄悄地讓幾乎每一場比較都更銳利。這一切若用真正的隨機都不可能。這個作弊本身，就是那個特性。
從一條均勻串流，通往其餘的一切
到目前為止的一切，都產出一個特定的東西：一條在 [0, 1) 上均勻的數流。那是通用的原料，也是一個 PRNG 唯一需要給你的東西。但接下來的方法很少想要單純的均勻數——它們想要的是來自鐘形曲線、指數衰減、或某個歪斜的自訂分布的樣本。令人愉快的驚喜，也正是下一篇的主題，是每一個這樣的分布都能靠一個巧妙的變換，從那單一條均勻串流裡造出來。均勻生成器是水龍頭；取樣則是把它的水重塑成你想要的任何分布的那套管路。
值得替本級裡一條沒走的路命名，因為它就緊挨在我們這條路旁邊。一旦你接受「你真正想要的，是把空間填得均勻的點，而不是彼此獨立的點」，你就能完全拋開隨機性的偽裝，改用低差異序列——一個被巧妙設計成非隨機的點集，刻意避開真正的隨機必然會留下的結團與空隙。把它們餵進蒙地卡羅，就得到準蒙地卡羅，在光滑的問題上它能收斂得比 O(1/sqrt(N)) 更快。我們稍後會碰到它；此刻先標記出來，只為強調「隨機」一直都是手段，從來不是目的。目的是把空間覆蓋得好。
所以這裡是一份關於「生成器是什麼、不是什麼」的誠實摘要。它是一條確定性的遞迴——通常只是一個被固定公式攪動的狀態——其輸出被工程化到能通過每一項隨機性的統計檢驗，卻又能從一顆種子完美重播。它不是真正隨機的來源、不是魔法，也並非總適合用於安全。把這兩個事實一起握住：這些數是假的，而正是這份假，讓本級其餘的部分既成為可能、又值得信賴。手裡握著一個可靠的均勻水龍頭，你就準備好去學習如何把它的輸出，塑造成你需要的任何分布了。