[問題] 亂數生成問題(已修改問題)

看板C_and_CPP作者 (黑麻糬)時間9年前 (2014/08/19 23:28), 9年前編輯推噓6(6推 0噓 45→)
留言51則, 8人參與, 最新討論串1/2 (看更多)
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) Dev C++ 4.9.9.2 問題(Question)： 我的想要做遊戲模擬來驗證數學計算結果，遊戲大略結構如下 有五個黑袋子，袋中分別有 21, 22, 23, 24, 25 個球 有五個紅袋子，袋中分別有 11, 12, 13, 14, 15 個球 程式結構含有 1. function A (負責額外紅袋子的 Bonus) 2. function B (負責算黑袋子的分數) --> 裡頭有 call 到 function A int main() { clock_t seed=time(0)+clock(); srand(seed); for (1~10^10) { repeat call function B // 一秒約可執行兩千~三千次 B } } 後來仔細思考後，因為我要做的是 "驗證"， 所以應該不是 "亂度" 問題，而是如何保持 "均勻度" 問題 function A & function B 的抽球部分也簡化 int L[5]={21,22,23,24,25}; for (int i=0;i<=4;i++) { int r=(int)(L[i]*(double)(rand())/(RAND_MAX+1.0)); // 直接取 0~1 的 double number 再乘上 L[i] 變成 0~(L[i]-1) 共 L[i] 個數 // 基本上 rand() 帶給我的亂數在機率上是均勻的 } 但目前遇到的問題是 在 "同一張亂數表" 下，對 "同一個袋子" 取很多很多次球 因為均勻的關係，久了下來每個球被取到的次數(比例)會很貼近 平均得分的結果自然就可以拿來驗證我的數學期望值計算 但是我現在有五個袋子...如果第一個袋子抽到了 10 號 那這個 "10 號" 不就影響了後面袋子抽到 10 號的機會了? 因為整張表是均勻的，但是分給五個袋子使用的話就...完蛋了。 Q1: 我要如何指定給每個袋子一張亂數表(seed)，且保留那個袋子自己該有的表格 使得彼此之間的亂數生成是獨立的呢? (不會因為後四個袋子的抽球而影響了第一個袋子的均勻度) Q2: Q1 的解決方法也可以用到函數裡頭去嗎? (我需要五個 seed 給黑袋子 1~5 號 & 五個 seed 給紅袋子 1~5 號) 請問各位版大先進有沒有想法可以面對以上的問題 還請不吝給點教學材料教教小弟，感激不盡 ========================== 我是分隔線 =========================== 又有胡思亂想的新問題嚕~! 就我自己曉得的電腦亂數 rand() 是一張亂數表為底，在亂數種子未重設之前 它在這張表中依序取出數字出來當做亂數 因為我現在是想透過電腦模擬來驗證數學結果 數學結果是 "最理想" 的狀態下的期望值結果 但是不論我怎麼試，模擬的結果似乎都無法做到以上的這點 因為模擬結果 dependent on random table 例如： 兩張只含有 8 個 0, 1 亂數的亂數表 A, B, C， A： 1 1 0 1 0 0 0 1 B： 1 1 0 1 0 0 1 0 C： 1 1 1 1 0 0 0 0 三表都各含 4 個 0、4 個 1，從這三表去取出來的數滿足 P(A)=P(偶)=0.5 如果遊戲規則訂為 "投入1$，取兩數，若是一奇一偶則多得 1$，反之 1$ 就沒了。" 就數學的角度，在公平的遊戲中，機率為 P(奇 & 奇)=P(奇 & 偶)=P(偶 & 奇)=P(偶 & 偶)=0.25。 就電腦亂數表的角度，頭尾相接持續取亂數 A 表滿足以上各 Case 機率=0.25 的性質=================> P(+分)=P(-分)=4/8 B 表 n(奇&奇)=1、n(奇&偶)=3、n(偶&奇)=3、n(偶&偶)=1 => P(+分)=6/8, P(-分)=2/8 C 表 n(奇&奇)=3、n(奇&偶)=1、n(偶&奇)=1、n(偶&偶)=3 => P(+分)=2/8, P(-分)=6/8 用這三張亂數表去做這個遊戲的模擬 那 A 表的顯示遊戲公平(與數學結果相同)，B 表顯示玩家得利，C 表顯示莊家得利 Q：原表亂數 equally likely 不能 implies 帶出來的遊戲模擬結果也是 equally likel y 的吧? 那在模擬時要怎麼辦? 先做出滿足條件的亂數表? 還是這兩數各給一張表? 希望版大們能給點意見~ 腦筋打結時容易鑽牛角尖，版大們也可以當我胡思亂想。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.170.211.100 ※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1408462098.A.24D.html
推
08/20 00:07, , 1F
我不建議你再研究這問題，答案是它的周期約是 21 億個數,
08/20 00:07, 1F
→
08/20 00:08, , 2F
解決它的方法是換一個亂數產生器,若願意從dev-c++跳出來
08/20 00:08, 2F
→
08/20 00:08, , 3F
的話，有其他周期較長，基本上不會讓你重覆的。
08/20 00:08, 3F
→
08/20 07:43, , 4F
那請問 Visual C++ 會有比較可行的方案嗎? 感謝您。
08/20 07:43, 4F
推
08/20 08:19, , 5F
只要你用的亂數源的Bit數有限，總有一天會再重覆的。
08/20 08:19, 5F
→
08/20 08:37, , 6F
比較新的編譯器能用Mersenne twister
08/20 08:37, 6F
推
08/20 13:47, , 7F
C++11 有比較好用的 random
08/20 13:47, 7F
※ 編輯: hexjacal (1.165.185.171), 08/20/2014 14:27:05
推
08/20 19:27, , 8F
亂數 "分給五個袋子使用" 會 "不均勻"? 是你的實測還是推測?
08/20 19:27, 8F
→
08/20 19:33, , 9F
我稍微測一下, 且即使把rand()換成MSVC的實作(#1JLwsGtg推文)
08/20 19:33, 9F
→
08/20 19:35, , 10F
不管是一組或分多組, 每球被抽出的計次看來差異不大...
08/20 19:35, 10F
→
08/20 19:42, , 11F
^同組內的
08/20 19:42, 11F
推
08/20 21:00, , 12F
google C++11 mt19937,它的週期絕對讓你夠用.
08/20 21:00, 12F
→
08/20 21:01, , 13F
原理如 az~ 大所言，用的是梅森旋轉法.
08/20 21:01, 13F
→
08/20 21:10, , 14F
分組不會影響均勻度，如果袋子的球數差異性很大呢?
08/20 21:10, 14F
→
08/20 21:14, , 15F
品質好的亂數產生器不會因為分組產生差別
08/20 21:14, 15F
→
08/20 21:14, , 16F
會有問題我覺得是程式寫法或統計的問題
08/20 21:14, 16F
→
08/20 21:17, , 17F
我在同張亂數表連取五數下對 21~25 取餘數作取球
08/20 21:17, 17F
→
08/20 21:18, , 18F
總感覺袋子間取的號碼不獨立，想分開來取試試看
08/20 21:18, 18F
→
08/20 21:20, , 19F
"感覺"是什麼? 有數據嗎? 低樣本數看起來有模式很正常
08/20 21:20, 19F
→
08/21 22:49, , 20F
如果是要數學上的均勻分布U(0,1) 有標準的演算方法
08/21 22:49, 20F
→
08/21 22:53, , 21F
然後設v抽出來的值,取f(v)=(b-a)v+a
08/21 22:53, 21F
→
08/21 22:55, , 22F
f(v)=U(a,b),這樣就有a到b的均勻分布
08/21 22:55, 22F
→
08/21 22:58, , 23F
最後 如果要1,2,3,4,5均勻抽樣 就設a=0.5,b=5.5,f(v)四捨五
08/21 22:58, 23F
→
08/21 22:59, , 24F
入就是標準解
08/21 22:59, 24F
推
08/21 23:02, , 25F
如果你要抽的不是uniform,要抽的pdf,g1(v),
08/21 23:02, 25F
→
08/21 23:06, , 26F
就先對g1(v)積分得到G1(v),其反函數為G1-1(v)
08/21 23:06, 26F
→
08/21 23:09, , 27F
所以抽出值為v=G1-1(U(0,1)),就會是你要的pdf
08/21 23:09, 27F
→
08/21 23:17, , 28F
最後在高維度抽樣,f(v1,v2,...,vn),做法一樣
08/21 23:17, 28F
→
08/21 23:20, , 29F
先求出邊際pdf f1(v1),f2(v2),...,fn(vn),積分得F1,F2,...,F
08/21 23:20, 29F
→
08/21 23:23, , 30F
...,Fn 按照Fn的值取P個分割,所以全域有P^n
08/21 23:23, 30F
→
08/21 23:25, , 31F
最後先抽U(0.5,P^n+0.5)決定在哪個分割,在分割內再
08/21 23:25, 31F
→
08/21 23:29, , 32F
各變數自己抽,vi=U(Low Bounded ,Up Bounded)
08/21 23:29, 32F
→
08/21 23:31, , 33F
這裡的Low或Up都是指vi這個分割內的上下界
08/21 23:31, 33F
→
08/21 23:35, , 34F
另外,有另一種方法是在v方向做分割在值的方向
08/21 23:35, 34F
→
08/21 23:39, , 35F
放機率(想成求期望值),這樣就可以得到抽樣結果(以pdf表示)
08/21 23:39, 35F
→
08/21 23:45, , 36F
以上是之前處理10k個隨機變數的心得
08/21 23:45, 36F
→
08/21 23:49, , 37F
我的問題應該是模擬過程中，給定亂數表帶來的毛病，
08/21 23:49, 37F
→
08/21 23:50, , 38F
同張表出現的亂數是均勻的，但帶出來的遊戲結果卻不一定
08/21 23:50, 38F
→
08/21 23:50, , 39F
均勻，所以造成我模擬的結果與數學推論結果有很大差異
08/21 23:50, 39F
※ 編輯: hexjacal (114.26.137.84), 08/21/2014 23:52:49
→
08/22 00:05, , 40F
你沒考慮到亂數表是ABC的機率
08/22 00:05, 40F
→
08/22 00:06, , 41F
所以亂數要用srand初始化防止每次結果都是A
08/22 00:06, 41F
→
08/22 00:09, , 42F
此外樣本數越少本來就越容易和期望值差很遠
08/22 00:09, 42F
→
08/22 01:13, , 43F
請去找Randomness tests的資料來看
08/22 01:13, 43F
→
08/22 01:18, , 44F
你所謂 會造成遊戲結果差異的亂數 會有特定的pattern在
08/22 01:18, 44F
→
08/22 01:19, , 45F
很多test都不會過的
08/22 01:19, 45F
→
09/08 06:39, , 46F
UD 課本的程式碼 http://ppt.cc/gzB4
09/08 06:39, 46F
→
09/08 06:41, , 47F
兩隻Rand 就可以生山很多組的 亂數表了
09/08 06:41, 47F
→
09/08 06:42, , 48F
兩隻Rand 就可以生出很多組的 亂數表
09/08 06:42, 48F
→
09/08 08:44, , 49F
另一個網站 有一堆UD Code http://ppt.cc/zeJ7
09/08 08:44, 49F
→
09/08 09:15, , 50F
int r=(int)(L[i]*(double)(rand()+0.5)/(RAND_MAX+1.0));
09/08 09:15, 50F
→
09/08 09:17, , 51F
我猜你是要產生UD但你Rand出來的東西要加0.5才是UD
09/08 09:17, 51F
‣ 更多 hexjacal 的文章
文章代碼(AID): #1JysqI9D (C_and_CPP)
‣ 更多 hexjacal 的文章
文章代碼(AID): #1JysqI9D (C_and_CPP)