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

[hexjacal (黑麻糬)]

開發平台(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
推 EdisonX: 我不建議你再研究這問題，答案是它的周期約是 21 億個數,
→ EdisonX: 解決它的方法是換一個亂數產生器,若願意從dev-c++跳出來
→ EdisonX: 的話，有其他周期較長，基本上不會讓你重覆的。
→ hexjacal: 那請問 Visual C++ 會有比較可行的方案嗎? 感謝您。
推 Leadgen: 只要你用的亂數源的Bit數有限，總有一天會再重覆的。
→ azureblaze: 比較新的編譯器能用Mersenne twister
推 johnjohnlin: C++11 有比較好用的 random
※ 編輯: hexjacal (1.165.185.171), 08/20/2014 14:27:05
推 yvb: 亂數 "分給五個袋子使用" 會 "不均勻"? 是你的實測還是推測?
→ yvb: 我稍微測一下, 且即使把rand()換成MSVC的實作(#1JLwsGtg推文)
→ yvb: 不管是一組或分多組, 每球被抽出的計次看來差異不大...
→ yvb:                    ^同組內的
推 EdisonX: google C++11 mt19937,它的週期絕對讓你夠用.
→ EdisonX: 原理如 az~ 大所言，用的是梅森旋轉法.
→ hexjacal: 分組不會影響均勻度，如果袋子的球數差異性很大呢?
→ azureblaze: 品質好的亂數產生器不會因為分組產生差別
→ azureblaze: 會有問題我覺得是程式寫法或統計的問題
→ hexjacal: 我在同張亂數表連取五數下對 21~25 取餘數作取球
→ hexjacal: 總感覺袋子間取的號碼不獨立，想分開來取試試看
→ azureblaze: "感覺"是什麼? 有數據嗎? 低樣本數看起來有模式很正常
→ wope: 如果是要數學上的均勻分布U(0,1)  有標準的演算方法
→ wope: 然後設v抽出來的值,取f(v)=(b-a)v+a
→ wope: f(v)=U(a,b),這樣就有a到b的均勻分布
→ wope: 最後 如果要1,2,3,4,5均勻抽樣 就設a=0.5,b=5.5,f(v)四捨五
→ wope: 入就是標準解
推 wope: 如果你要抽的不是uniform,要抽的pdf,g1(v),
→ wope: 就先對g1(v)積分得到G1(v),其反函數為G1-1(v)
→ wope: 所以抽出值為v=G1-1(U(0,1)),就會是你要的pdf
→ wope: 最後在高維度抽樣,f(v1,v2,...,vn),做法一樣
→ wope: 先求出邊際pdf f1(v1),f2(v2),...,fn(vn),積分得F1,F2,...,F
→ wope: ...,Fn 按照Fn的值取P個分割,所以全域有P^n
→ wope: 最後先抽U(0.5,P^n+0.5)決定在哪個分割,在分割內再
→ wope: 各變數自己抽,vi=U(Low Bounded ,Up Bounded)
→ wope: 這裡的Low或Up都是指vi這個分割內的上下界
→ wope: 另外,有另一種方法是在v方向做分割在值的方向
→ wope: 放機率(想成求期望值),這樣就可以得到抽樣結果(以pdf表示)
→ wope: 以上是之前處理10k個隨機變數的心得
→ hexjacal: 我的問題應該是模擬過程中，給定亂數表帶來的毛病，
→ hexjacal: 同張表出現的亂數是均勻的，但帶出來的遊戲結果卻不一定
→ hexjacal: 均勻，所以造成我模擬的結果與數學推論結果有很大差異
※ 編輯: hexjacal (114.26.137.84), 08/21/2014 23:52:49
→ azureblaze: 你沒考慮到亂數表是ABC的機率
→ azureblaze: 所以亂數要用srand初始化防止每次結果都是A
→ azureblaze: 此外樣本數越少本來就越容易和期望值差很遠
→ mike0227: 請去找Randomness tests的資料來看
→ mike0227: 你所謂 會造成遊戲結果差異的亂數 會有特定的pattern在
→ mike0227: 很多test都不會過的
→ wope: UD 課本的程式碼 http://ppt.cc/gzB4
→ wope: 兩隻Rand 就可以生山很多組的 亂數表了
→ wope: 兩隻Rand 就可以生出很多組的 亂數表
→ wope: 另一個網站 有一堆UD Code http://ppt.cc/zeJ7
→ wope: int r=(int)(L[i]*(double)(rand()+0.5)/(RAND_MAX+1.0));
→ wope: 我猜你是要產生UD但你Rand出來的東西要加0.5才是UD