koukai的Blog

所謂80-20守則，就是根據統計有80%的機會會落在20%的區域裡面，
例如80%對檔案的存取，會只存取硬碟中20%的檔案[1]  阿我懶得列文獻啦 =.=

但你要用C寫出一個令人信服的程式，就不是那麼簡單的事情，
因為一般來說rand()出來的值是uniform distribution的，
也就是說從0~RAND_MAX的每個值出來的機率是一樣的，
不信你可以統計看看 XDDDD
而且重點是你自己寫的對 reviewer來說沒有說服力XDDDD

這是直接用rand()產生1百萬個0~800之間的值的分佈圖，縱軸是累計次數，可以看到差不多
注意哦!縱軸是1100~1350.....

接著下面是CDF(累計機率)圖，很明顯的一直線就是uniform分佈的特徵：

以下是教學：
這次我們要產生的值域是0~800，
平均值是400，然後希望80%落在中間20%的區域，
也就是320~480的區域

首先要先求出這個條件下，標準差應該要是多少
Fx(x) = P[X <= x] 是說X<=x的機率是多少

我們要求的是 P[320 < X <= 480] = 0.8
根據CDF定理[2][3]:
P[320 < X <= 480] = Fx(480) - Fx(320) = 0.8

而根據常態分佈的定理，請畫圖 Orz
Fx(480) = 0.9, Fx(320) = 0.1

而Fx(x) = Φ(z) = Φ((x - μ)/σ)   μ是平均值, σ是標準差
因為Fx(x) = 0.9，根據查表[3][6]，可得z約落在1.28~1.29間，
1.29比較接近用1.29，所以(x - μ)/σ = 1.29
代入已知的值x=480, μ=400，可求得σ = 62.02 !!!!

有了平均值、標準差，就可以產生我們要的常態分佈圖了，
最後根據Box–Muller transform[4][5]，我們可以將C裡面的rand()
從uniform分佈轉換成常態分佈，
code怎麼寫？
請看http://koukaipan.pixnet.net/blog/post/24159101

最後也來看看圖表證明一下，一樣是產生1百萬個0~800的值
這是分佈圖：

下圖是CDF：
可以用尺對一下累計機率0.9時，會約落在480的位置；累計機率0.1落在320，
所以落在320~480之間的機率是0.8!!

[1] 忘了，反正好幾篇....
[2] http://en.wikipedia.org/wiki/Standard_normal_table
[3] Probablity and Stochastic Processes, 2nd, Roy D. Yates and David J. Goodman, Wiley
[4] http://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform
[5] G. E. P. Box and Mervin E. Muller, A Note on the Generation of Random Normal Deviates, The Annals of Mathematical Statistics (1958), Vol. 29, No. 2 pp. 610-611
[6] http://en.wikipedia.org/wiki/Standard_normal_table
--
要是每科數學都能這麼有趣，我一定都會認真上課....
--
謝老師～我沒有忘記隨機程序哦 :'(