統計學/數值方法/隨機數生成

定義和用法

隨機數 → ”一串整數或數字組，在序列中的任何位置都絕對沒有相互關係。在任何時刻，所有整數都有相等的出現機會，並且它們以不可預測的方式出現”

許多統計方法依賴於隨機數。然而，隨機數的使用已經擴充套件到隨機抽樣或隨機分配處理到實驗單位之外。現在更常見的用途是在物理過程、分析上難以處理的數學表示式或從給定樣本中對該總體進行重取樣的模擬研究中。這三個應用的總體領域有時被稱為模擬、蒙特卡洛和重取樣。

均勻隨機數生成

給定一個無限序列 $R_{0},R_{1},...,R_{n},...$，大多數人對隨機的理解包括這些數字在區間 (0, 1) 中均勻分佈。我們用 U(0, 1) 表示這種分佈。我將在本文中介紹生成均勻隨機數的兩種方法：線性同餘生成器和Tausworthe 生成器。

線性同餘生成器

D. H. Lehmer 在 1948 年提出了線性同餘生成器作為隨機數的來源。在這個生成器中，每個數字都決定了它的後繼者。生成器的形式是

                       $X_{i+1}$ = (a$X_{i}$ + c) mod m   , with  0 ≤ $X_{i}$ ≤ m .

m 稱為模數。 $X_{0}$、a 和 c 分別稱為種子、乘數和增量。

例如，考慮 m = 31、a = 7、c = 0，並從 $X_{0}$ = 19 開始。序列中的下一個整數是

                      9, 1, 7, 18, 2, 14, 5, 4, 28, 10, 8, 25, 20, 16, 19,

因此，當然，此時序列開始重複。

如果我們取 a = 3 而不是 a = 7，我們將得到

     26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15,
              14, 11, 2, 6, 18, 23, 7, 21, 1, 3, 9, 27, 19

從上面的簡單例子中，我們可以猜到模數、乘數和增量線上性同餘生成器的週期長度中起作用。

週期 → 週期是最小的正整數 λ，對於它 $X_{\lambda }=X_{0}$。週期不能大於 m。因此，m 被選擇為等於或接近計算機中可表示的最大整數，以獲得較長的週期。

一個全週期生成器是週期為 m 的生成器，當且僅當

1. c 與 m 互質；2. (a-1) 是 m 的每個素因子 q 的倍數；3. 如果 m 是，(a-1) 是 4 的倍數。

增量 →

如果 c > 0，我們可以透過以下方式實現全週期 

1- m = $2^{b}$ → 更快的計算機運算,

2- 設定 (a-1) 作為 4 的倍數,

3- c 應該是奇數值,

4- 設定 b 儘可能高。例如，在 32 位計算機中 b=31。

如果 c = 0，則不可能實現全週期。在這種情況下，可以實現的最大隨機變數數量可以透過以下方式實現 

1- 一個最大週期生成器，其中 λ = m − 1，是一個其中 a 是模 m 的一個本原元素的生成器，如果 m 是素數。

                           i. a mod m 6= 0
                           ii. a(m−1)/q modm 6= 1 , for each prime q of (m-1)

2- 鑑於前面的評論，m 通常設定為小於 2b 的最大素數。最常用的模數是梅森素數 $2^{31}-1$。

最大週期 → m = 素數，a = 模 m 的本原元素

生成的數字中的結構

生成的隨機數背後的理念是這些數字應該真正隨機。這意味著這些數字應該看起來在分佈上相互獨立；也就是說，序列相關性應該很小。一個序列的結構有多糟糕（也就是說，這種情況導致輸出看起來有多不隨機）取決於格的結構。

考慮一個生成器，其中m = 31，a = 3，並從$x_{0}$=19 開始。繪製連續的數對。

                               (27, 19), (19, 26), (26, 16)...

從圖 1.2 可以很容易地看出，連續的隨機數對只位於三條線上。生成的數字似乎並不隨機。它們似乎存在相關性。從視覺角度來看，我們可以得出結論，具有少量行的生成器不能很好地覆蓋空間，並且具有較差的格點結構。

MacLaren 和 Marsaglia（1965）建議使用另一個生成器來排列原始生成器的子序列，從而對線性同餘隨機數生成器的輸出流進行洗牌。

透過這種方式，可以增加週期，並且輸出的洗牌還可以破壞不好的格點結構。

均勻偏差的 Bays-Durham 洗牌

Bays 和 Durham 建議使用單個生成器填充長度為 k 的表格，然後使用單個流從表格中選擇一個數字並補充表格。在將表格 T 初始化為包含$x_{1},x_{2},...,x_{k},$ 後，設定 i = k+1 並生成$x_{i}$ 用作表格的索引。然後使用$x_{i+1}$ 更新表格。

例如，使用圖 1.3 中的生成器，它產生了序列

             27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15,
                           14, 11, 2, 6, 18, 23, 7, 21, 1, 3, 9,

我們選擇 k = 8，並將表格初始化為

                                 27, 19, 26, 16, 17, 20, 29, 25.

然後，我們使用下一個數字 13 作為輸出流中的第一個值，並作為表格的隨機索引。如果我們將索引形成為 13 mod 8 + 1，我們將得到第六個表格值 20，作為輸出流中的第二個數字。我們生成原始流中的下一個數字 8，並將其放入表格中，因此我們現在有表格

                                 27, 19, 26, 16, 17, 8, 29, 25.

現在，我們使用 20 作為表格的索引，並得到第五個表格值 17，作為輸出流中的第三個數字。透過繼續以這種方式生成 10,000 個偏差並繪製連續的數對，我們得到圖 1.6。

Tausworthe 生成器

Tausworthe（1965）引入了一種基於 0 和 1 序列的生成器，該序列由以下形式的遞迴生成

$b_{i}\equiv (a_{p}b_{i-p}+a_{p-1}b_{i-p+1}+...+a_{1}b_{i-1}){\textit {mod}}2$

其中所有變數都取 0 或 1 的值。

為了計算效率，方程式中大多數 a 設定為零。然後我們得到，

                                $b_{i}\equiv (b_{i-p}+b_{i-p+q}){\textit {mod}}2$

在該遞迴被評估足夠多次後，例如l，a 的l 元組被解釋為 2 進位制數。這被稱為 a 序列的l 位抽取。

例如，取一個模 2 的原始三項式，

                                         x4 + x + 1,

並從位序列開始

                                         1, 0, 1, 0.

對於這個多項式，p = 4，q = 3 在遞迴中。操作生成器，我們得到

                          1, 1, 0, 0,1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0,

此時序列重複。4 位抽取產生數字

                                        12, 8, 15, 5, … 

與線性同餘生成器一樣，c 的不同值甚至 a 的起始值都可能產生好或壞的生成器。

擬合優度檢驗

在本部分，我將向您介紹基本的擬合優度檢驗，透過這些檢驗我們可以評估使用上述方法建立的隨機數序列。

卡方擬合優度檢驗

            $\chi ^{2}=\sum _{i=1}^{k}{\frac {(o_{i}-e_{i})^{2}}{e_{i}}}$

→ 零假設：隨機變數具有均勻 (0,1) 分佈

→ 計算每個 10 個區間中觀測值的個數

                      (0, 0.1], (0.1, 0.2], ..., (0.9, 1.0)

→ 將這些計數與預期數字進行比較。

→ 如果觀測到的數字與預期數字顯著不同，我們有理由拒絕零假設。

Kolmogorov-Smirnov 檢驗

此檢驗將經驗累積分佈函式 (c.d.f) ${\hat {F}}(.)$ 與理論 c.d.f F(.) 進行比較。

→ H0：F(x) = x，0 _ x < 1

→ 對觀測結果進行排序，以便$R^{(1)}\leq R^{(2)}...\leq R^{n}$

${\hat {F}}(x)={\frac {i}{n}}$ ，並且 $R^{(n+1)}\equiv 1$

→ 其中 $R^{(0)}\equiv 0$ **並且** $R^{(n+1)}\equiv 1$.

→ 檢驗統計量衡量了這兩個之間最大差異的大小

$D_{n}=max_{0\leq x<1}$ $\left|{\hat {F}}(x)-F(x)\right|$

線性依賴性檢驗

→ 測試序列中數字之間依賴關係的一種方法是將這種檢查限制在相隔 k 個數字的觀察結果之間的線性依賴關係。

→ 給定 n 個隨機數的實現 $R_{0},R_{1},\ldots ,R_{n}$，滯後 k 的樣本協方差為

$C_{k}=(n-k)^{-1}\sum _{i=1}^{n-k}(R_{i}-{\frac {1}{2}})(R_{i+k}-{\frac {1}{2}}).$

→ 在隨機性下 $E[C_{k}]=0$.