機率研究 (2) - 亂數產生器文獻探討以及其在 Mathematica 上的實作

 在第一篇研究，我們觀察到，所有控制機率事件的根源是 randInt()，也就是說，除了控制機率數值的事件數量、空間大小決定機率表之外，有沒有辦法透過機率本身去改動什麼，因此，從簡單的 random 開始研究起。

在研究上，意外有幾個發現，對於亂數產生器實作層面上的考量，會因為不同的應用情景，有不同的需求。

對於亂數產生器，最極端的情形要分成兩種: 可預測性、不可預測性。

對於 《伪随机生成器具体实现——杂乱的方法》 這篇文章的說法，我覺得具有蠻重要的意義:

雜亂或極度混亂的方法做出來的亂數，如果無法判斷演算法的「週期」或是「預測性」，那對於一個謹慎的應用而言，也無法證明這個亂數產生器是否具備不可預測性；「不可預測性」 是亂數產生器很重要的指標。

對於密碼學技術而言，如果亂數產生器本身是可預測的 (有可能是週期較短)，那就不可以應用在密碼學技術上。

對於雜亂混亂的方法做出來的亂數，在重複週期上都比較短，所以很可能會被觀察出來。

除了預測性以內的考量，還有:

• 產生速度
• 較長的週期
• 可移植性
• 亂數需具有 [0, 1] 之間的均勻性與統計上的獨立性

這個部分可以參考 [2]。

對於產生的方法，對於 Wiki 上的說明，有物理方法、計算方法、概率分佈生成、人類。

或許，日後幾篇文章再得到我想要的【控制機率】之後，來研究看看物理方法所產生出來的亂數，劇說 Cloudflare 是用熔岩燈做亂數生產的，之後可以來研究看看是怎麼回事。

對於幾種亂數產生器的演算法，有幾種:

1. 線性同餘
2. ANSI X9.17
3. 單向雜湊函式
4. 密碼法: AES、RSA 密碼

線性同餘

本篇著重研究線性同餘以及他的幾種延伸實作，經過 Reference 幾篇研究，該方法不能被用於密碼技術，因為線性同餘不具備不可預測性。

我們想先研究的是【可預測性】的機率，原因是我們想【控制機率】，所以對於不可預測的性質目前還不感興趣。

從 [6] 的參考中，我們了解線性同餘的定理性質:

$$ y_0 \in \mathbb{R} \space\space \fbox{seed} \newline a \in \mathbb{R} \space\space \fbox{constant multiplier} \newline c \in \mathbb{R} \space\space \fbox{increment} \newline m \in \mathbb{N} \space\space\fbox{modulus} \newline y_{i+1} = (ay_i + c) \mod{m} \tag{1}$$

舉例計算方式:

對於 Formula (1) 而言，我們可以給定初始值參數，得到 y0:

$$ seed = 7, \space m=16, \space a=5, \space c=3 \newline y_0 = [(5 * 7) + 3] \mod{16} \newline y_0 = 16 $$

接著，我們可以使用 Wolframe Mathematica 數學軟體計算遞迴表，其中生成函數是這個 y :

RecurrenceTable[{y[n] == Mod[a*y[n - 1] + c, m], y[1] == y0}, y, {n, 10}]

得到最初開始算的 10 個值的 Sequence。

參數調整

在研究線性同餘之時，也需要了解幾種參數調整，有哪些實作的形式，看到了 [6] 的文獻，我們可以看到線性同餘有公認的調整參數的規則。

線性同餘: Linear Congruential，他的生成函數就是 Linear Congruential Generator 簡稱 LCG。

根據 [9] 文獻的說明，線性同餘有兩大種數學架構分類:

• Mixed LCG 
  $$ 條件:  c \neq 0 $$
  
  
• Multiplicative LCG
  $$ 條件:  c  = 0 $$

可以看 wiki 上說明的這段話:

「 are integer constants that specify the generator. If c = 0, the generator is often called a multiplicative congruential generator (MCG), or Lehmer RNG. If c ≠ 0, the method is called a mixed congruential generator.[2]:4- 」。

Wiki 有提供常用參數表，請參見 〈Parameters in common use〉 小節。

在這裡備註，下面篇幅的內部狀態 (status) 是上述公式的 

$$ y_n $$

因此，下面篇幅的 

$$ state_{n+1} $$

就是指

$$ y_{n+1} $$

根據 [5] 的文獻，它選出了兩種常用的參數實作，分別對照是:

•  BSD Formula ，是 Wiki 上的 glibc
  $$ state_{n+1} = 1103515245 \times state_n + 12345 \mod{2^{31}}$$
  
  
• Microsoft Formula ，是 Wiki 上的 Microsoft Visual/Quick C/C++
  $$ state_{n+1} = 214013 \times state_n + 2531011 \mod{2^{31}} $$

BSD Formula Mathematica 實作 (文獻 [5]):

BSDrand[x_] := Mod[x*1103515245 + 12345, 2147483648]
NestList[BSDrand, 0, 10]

Microsoft Formula Mathematica 實作 (文獻 [5]):

MSrand[x_] := Mod[x*214013 + 2531011, 2147483648]
BitShiftRight[ NestList[MSrand, 0, 10], 16]

探討完亂數產生器後，這告訴我們亂數產生是在決定可不可預測性，這與我當初想像的控制機率事與願違，下一節應該會研究剛才看到的概率分佈生成。

Reference:

[1] https://blog.csdn.net/chengqiuming/article/details/83037257
[2] https://jk3527101.pixnet.net/blog/post/14108716
[3] https://en.wikipedia.org/wiki/Random_number_generation
[4] https://blog.csdn.net/chengqiuming/article/details/83039265
[5] https://rosettacode.org/wiki/Linear_congruential_generator#Java
[6] https://jk3527101.pixnet.net/blog/post/14108713
[7] https://muzibing.github.io/2019/05/28/2019.05.28%EF%BC%8863%EF%BC%89/
[8] https://halfrost.com/random_number/
[9] https://en.wikipedia.org/wiki/Linear_congruential_generator