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

定義和用法

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

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

均勻隨機數生成

給定一個無限序列 $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. (a-1) 是 4 的倍數，如果 m 是。

增量 →

如果 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 mod8 + 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）分佈

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

                      (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$.