以C++內建隨機演算法討論在規模為K之下的隨機次數之機率準確度

最近好像有關於遊戲抽獎機率問題的爭議。

雖然知道隨機有時是不準的,但我仍想用C++(僅梅克森旋轉演算法)親自嘗試。

以下為測試用程式碼。

#include<bits/stdc++.h>
using namespace std;

//隨機樹使用參數為時間(毫秒)
unsigned seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(seed);
//平均分布
uniform_int_distribution<int> dis(1,100);

long long RandomNumber(){
    return dis(rng);
}

void TestRamdon(int K){
    int mx=0,mn=100000000;
    for(int i=0;i<100000;++i){
        int ct=0;
        for(int j=0;j<K;++j){
            int tp=RandomNumber();
//          1~100 理論隨機 <=10 機率為 0.1(10%)
            if(tp<=10){
                ct++;
            }
        }
        mx=max(ct,mx);
        mn=min(ct,mn);
    }

    long double maxRate=1.0*mx/K;
    long double minRate=1.0*mn/K;

    cout<<"Max Rate In 10^5 Times "<<K<<" Times Random : "<<maxRate<<"\n";
    cout<<"Min Rate In 10^5 Times "<<K<<" Times Random : "<<minRate<<"\n";
    cout<<endl;
}

int main(){
    // test if random K times is enough to get reality rate

    const int K=400;
    const int TestTime=10;

    for(int i=0;i<TestTime;++i){
        TestRamdon(K);
    }
}

經過我實測,在理論機率為 10% 時,測試400次最悽慘的機率約莫落在 0.04(4%) ,而最佳機率則約為 0.17 (17%)

測試結果 K=400

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.0375 

Max Rate In 10^5 Times 400 Times Random : 0.1775
Min Rate In 10^5 Times 400 Times Random : 0.0425 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.04   

Max Rate In 10^5 Times 400 Times Random : 0.1675
Min Rate In 10^5 Times 400 Times Random : 0.0325 

Max Rate In 10^5 Times 400 Times Random : 0.165
Min Rate In 10^5 Times 400 Times Random : 0.0375 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.0375 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.0425 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.045  

Max Rate In 10^5 Times 400 Times Random : 0.165
Min Rate In 10^5 Times 400 Times Random : 0.0425 

Max Rate In 10^5 Times 400 Times Random : 0.17
Min Rate In 10^5 Times 400 Times Random : 0.0375

而到底應該要幾次以上才會到min=0.09(9%)呢?歡迎各位親自嘗試。以下是關於我有測試的次數

K=10

Max Rate In 10^5 Times 10 Times Random : 0.6
Min Rate In 10^5 Times 10 Times Random : 0  

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0  

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.6
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.8
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.7
Min Rate In 10^5 Times 10 Times Random : 0

Max Rate In 10^5 Times 10 Times Random : 0.6
Min Rate In 10^5 Times 10 Times Random : 0

K=100

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.26
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0      

Max Rate In 10^5 Times 100 Times Random : 0.25
Min Rate In 10^5 Times 100 Times Random : 0

K=1000

Max Rate In 10^5 Times 1000 Times Random : 0.148
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.143
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.143
Min Rate In 10^5 Times 1000 Times Random : 0.063 

Max Rate In 10^5 Times 1000 Times Random : 0.147
Min Rate In 10^5 Times 1000 Times Random : 0.063 

Max Rate In 10^5 Times 1000 Times Random : 0.143
Min Rate In 10^5 Times 1000 Times Random : 0.063 

Max Rate In 10^5 Times 1000 Times Random : 0.144
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.146
Min Rate In 10^5 Times 1000 Times Random : 0.055 

Max Rate In 10^5 Times 1000 Times Random : 0.144
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.145
Min Rate In 10^5 Times 1000 Times Random : 0.061 

Max Rate In 10^5 Times 1000 Times Random : 0.142
Min Rate In 10^5 Times 1000 Times Random : 0.061

但是剛剛測測試次數皆為10^5,若換成10^6呢?

Max Rate In 10^6 Times 400 Times Random : 0.1775
Min Rate In 10^6 Times 400 Times Random : 0.03

變成 0.03(3%) !

不得不說,跟我想的好像不一樣。希望大家自己測試,筆者因為電腦不夠好(i5古早版本)只能做到這了。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *