隨機數探究

作者﹕HKACT 網主 Zinedine

淺談「隨機數」 (random number)
(參考自《離散數學教程》-四川大學出版社,吳子華、張一立、唐常杰編)

在計算機的教學文件之中談論到「隨機數」是遊戲的主要內容之一。然而我們對於隨機數的認識並不深入,在眾多的測試結果之中使我們明白到「隨機數」並不是完全的「隨機」。越多的樣本數字並不是趨向於 0.5 。例如 fx-3900Pv 主要是 0.508 ,而 fx-3600Pv 則主要是 0.498。為甚麼會有這樣的情況出現呢?要深入了解,就要從隨機數的產生過程開始。

科學化的隨機數

所謂「隨機數」,我們可以理解為「在產生一系列數的過程中,其中每個數的出現與這個序列中其它數的出現無關,並且每個數落在指定範圍內的概率滿足一定的分佈要求」,當然我們的「要求概率」是盡量的平均。隨機數的產生方法有很多,如 Carto 曾經回答過筆者,說隨機數可以以 "Time Signature" 來產生。而今次我想介紹的,是一種比較使讀者明白的「線性同餘迭代式」方法。

「隨機數」不「隨機」

這是其中的一條式:

Xn+1 = (AXn + C) mod m

其中 A, C, m 是確定的常數整數,它們的值的選擇須使得產生的隨機數 (X1, X2, X3, X4...) 滿足在 0 和 m 之間均勻分佈的統計性質。在程式輸入初始值 X0 之後,X1, X2, X3 等等就可以自動產生出來。故此「隨機數」並不隨機,只是看起來像是而已,所以是一種「偽隨機數」。然而,由於計算機字長的限制和青示實數值的近似性等因素的作用,在 A, C, m 選得適當時,由乘數同餘方法產生的隨機數具有良好的分佈性,可以滿足需要。可是,如果錯誤地選擇三者的值的話,就會使其有周期性的特點。例如,令 A=2, C=4, m=7, 設 X0=2,產生的數字將會是:

2, 1, 6, 2, 1, 6, 2, 1, 6, ......

這是一個長度為 3 的周期的序列。而一個有用的隨機數系統應該有一個盡可能長的周期,因此常數 A, C, m 以及初始值 X0 的選擇就十分重要了。

(以下將會繼續深入探討以上數式。但由於筆者數學知識有限,並未能有足夠的知識去蕪存菁,但又覺得對計算機的知識十分有幫助,故此只好原文抄錄,唯希高人指教,略加解釋,深表謝意!)


計算機上的實際應用

  假如所使用的計算機字長為 L (如 fx-3900Pv 就是 10+2 位) ,通常把 m 選擇為 2L,也就是它所能表示的最大的無符號整數。要是參數 A, C 都是用同樣字長表示的無符號整數,那麼由

Xn+1 = (AXn mod 2L ) + C

得到的只是 2L 位的乘積的低位數據加上 C 的結果。這一加法運算可能造成(上)溢出(按:這裡的意思是指「可能會超出特定範圍」),但它無關緊要。這樣產生的低位數據自然不具有多大的隨機性。為彌補這一缺陷,通常把它當成小數部分看待,於是由上式得到的數可以變成 [0, 1] 區間的小數。由於計算機表示實數時只有有限位精確數字,實數的小數部份比全字長整數所佔位數要少,因而在把隨機整數 X 換成實數 Y 的過程中,某些低位數字可能被丟棄了,所得小數部份的隨機性也隨之增加。這時要由 Y 得到在範圍 1~k 的隨機整數 x', 只需令 x' = L y × k + 1 就行了。

如果對此有興趣之讀者,可以參考另一文獻:
D.E. Knuth, The Art of Computer Programming. Vol 3, 1973