在第一篇簡單的了解亂數產生器的基本概念後，在此篇將更詳細的介紹LCG的四項作法之差異。
線性同餘法(LCG，Linear Congruential Method):
目前被廣泛使用的亂數產生方式，是發展歷史最久的。
最早是在1951年由Lehmer所提出。
在線性同餘法裡，選擇一個很大的整數m，然後依下面的遞回方程式，創造出在0至m-1間之一連串整數群。
以下皆為整數:
y0 :種子值(seed)
a :固定乘數(constant multiplier)
c :增加量(increment)
m :模數(modulus)
y0是初始值，稱為種子值(seed)，其它的種子數yi是利用
依序產生出來，換言之就是自己產生的結果再拿來當種子數使用。
整個亂數列所產生的週期per(Ri)，將在per(Ri)<=m的條件下。
利用線性同餘法，當m=16、a=5、c=3、y0=7之週期:
線性同餘法範例:
參考下圖表格i=1~19的yi及sol，
由表格中可以看出y17=y1=6、y18=y2=1、y19=y3=8
由i=17、18、19與i=1、2、3相比較之下可以發現yi及sol有重複性。
因此可以定義i=1~16為一週期。
Full period 0<=yi<=m-1
若a、c選擇適當則可呈現full period
要使LCG有全週期(full period)，以避免隨機數快速重複。
a、c、m數值影響隨機亂數的好壞。
LCG要有全週期，須滿足三個情況:
-m、c互質
-x為質數，假如x可以除盡m，則q可以除盡a-1
-假如4可以除盡m，則4可以除盡a-1
依據c數值的不同，LCG可分為兩種格式:
-Mixed LCG
理論架構與LCG的原型相同，只是定義其中的c!=0
-Multiplicative LCG
理論架構與LCG的原型相同，只是定義其中的c=0
Mixed LCG:
1. 理論架構與LCG的原型相同，只是定義其中的c!=0
2. 假如要使Mixed LCG擁有全週期的特性，必須注重m值的挑選。假如m能夠是2的次方數，即m=2^i，最長的週期數則為P=m=2^i
3. c與a也有限制
甲、 c與m必須是互質
乙、 a=1+4k，其中k為整數
4. 讓m=2^i主要目的是為了迎合電腦的資料儲存與處理結構，假如i夠大，即i>=31，則m>=2^31，在一般32bit的電腦處理器上，可利用整數溢位(over flow)的技巧計算，可省下許多時間。
5. Kobayashi(1978)曾提出在i=31時，選擇a=314,159,269與c=453,806,245，為一良好的隨機亂數產生器。
Multiplicative LCG:
1. 理論架構與LCG的原型相同，只是定義其中的c=0
2. 使用m=2^i的形式，最長的週期是m/4=2^i-2，為了達到這個最大的週期數，種子數(seed)必須是奇數，a也有特定形式，即a=3+8k或是a=5+8k，k=0、1、2、3…
Multiplicative LCG範例:
利用Multiplicative LCG法求a=13,m=64，Y0=1,2,3,4(seed)之週期。
1.種子1及3的週期為16，種子2的週期為8，種子4的週期為4
2.最大週期為P=m/4=16。
3.這個週期是由奇數種子獲得，非偶數種子。
為了得到最大週期，所使用的a值一定是要滿足5+8k，k=0,1,2,3...之條件。
Prime Moduls Multiplicative LCG(PMMLCG):
1.由於Multiplicative LCG(c=0)這個結果達不到全週期的效果，因此，又有更進一步的研究。於是在c=0之下，又有人研發出另外一套m與a的關係，而這也是目前最常被使用的PMMLCG(Prime Modulus Multiplicative LCG)。
以下皆為整數:
y0 :種子值(seed)
a :固定乘數(constant multiplier)
c :增加量(increment)
m :模數(modulus)
0 <= yi <= m-1
2. 若m為質數，則可得到最大周期數為m-1，但a必須有限制，找一整數k使(a^k)-1可以被m整除。
3. 在m的研究上，若另m=(2^31)-1=2,147,483,647本身剛好就是一個質數，因此，許多的研究就不放在m的找尋，而放在a的找尋上。
4.目前有兩個a值為目前最廣泛被使用的，即a=16807與a=630,360,016。這兩個值皆為m的質數，且已經被廣泛的測試，不論是在周期、統計特性上都有相當好的表現，且可以在任何電腦上順利的使用。而這也是目前最常被使用的亂數產生方法。
隨機亂數之測試:
隨機亂數特性:
均勻性(uniformity)、獨立性(independence)。
為了要確認隨機亂數符合這兩個特性，有幾個測試的方法需要介紹。測試方法可分成兩類，一類測試是均勻性，另一類測試為獨立性。
-頻率測試(Frequency test)
-趨勢測試(Runs test)
-自相關測試(Autocorrelation test)
頻率測試(Frequency test):
1. 測試一個亂數產生器，最基本的測試為均勻性測試。
2. Komogorov-Smirnov及chi-square均可做為均勻性測試，兩種測試都是以虛無假設為”樣本的分配與理論的分配是無異”為基礎。
3. 以Chi-square測試為例:
卡方測試(Chi-square test)使用的統計值為:
Oi代表第i個分類的數量
Ei代表著期望的遞i個分類數量
X0^2的分配接近自由度為n-1的卡方分配
已均勻分配為例，期望的第i個分類數量為:
N代表著所有的觀測值，每一個分類的間隔是相等的。
趨勢測試(Runs test):
1. 獨立性測試
2. 測試數值上升或下降的趨勢
3. 利用實際的值與理想值比較，也是用chi-square來比較。楢樹值上升或下降的趨勢可以判斷出各個數值之間是否具有獨立性。
4. 舉例說明，若數值不斷上升或不斷下降，或者數值連續上升後就下降、下降後就上升都代表此隨機亂數不具獨立性。
自相關測試(Autocorrelation test figure):
1. 獨立性測試
2. 主要是測試序列數直間的相關性或相依性
3. 例如下列序列數值:
仔細觀察第5、第10、第15(每隔5個亂數)的數值都相當大，此代表此組亂數已不具獨立性。
此篇資料參考源至”清華大學工業工程與工程管理系電腦整合製造研究室 copyright 2001 林則孟“
留言列表
