Board logo

標題: 點樣令java random number random d [打印本頁]
作者: twaiho2003    時間: 2016-6-10 18:21     標題: 點樣令java random number random d

本帖最後由 twaiho2003 於 2016-6-10 18:29 編輯

我發覺JAVA random number 成日gen好接近既數字,
所以我做左個實驗, 抽4個 9 000 000 以內既數字, 但我發覺成日有相同既最大位數 或者好接近既最大位數
例如,
1 xxx xxx, 1 xxx xxx, 8 xxx xxx, 9 xxx xxx
5 xxx xxx, 5 xxx xxx, 6 xxx xxx, 6 xxx xxx


如果按機率, 我抽一個數字,  例如 1 xxx xxx,   再抽多3個, 有相同最大位數既機率應該係 1/9 + 1/9 + 1/9 = 1/3
(有錯請指教)

如果我試100次,   照計得33次左右出現相同最大位數,但結果成日多個50次,
改做 1 000 000 000次,  不斷出result 5 390 xxx 次
  1.     public static void main(String[] args) {
  2.         Random random = new Random();
  3.         int repeat_count = 0;

  5.         Set<Integer> num_set = new HashSet<>();

  7.         for (int times=0;times<1000;times++) {
  8.             for (int i=0;i<4;i++) {
  9.                 int num = random.nextInt(9000000);
  10.                 num_set.add(num/1000000);
  11.                 System.out.println(num);
  12.             }
  13.             if (num_set.size() < 4) {
  14.                 repeat_count++;
  15.                 System.out.println("repeated");
  16.             }
  17.             num_set.clear();
  18.             System.out.println("");
  19.         }

  21.         System.out.println("Repeat Count:" + repeat_count);
  22.     }
複製代碼
作者: evec    時間: 2016-6-10 18:37

方向： 拿系統時間做SEED。
作者: ykmran    時間: 2016-6-10 18:45

如果你係*nix env，就直接係/dev/random讀個int出黎
windows就算把啦
作者: twaiho2003    時間: 2016-6-10 18:55

既然個result 係咁，我諗諗下，係咪0-8，抽4個， 有53.9%有重履呢
係咪我機率計錯
作者: EITCo    時間: 2016-6-10 19:13

本帖最後由 EITCo 於 2016-6-10 19:16 編輯

5390xxx次好吻合理論值，只係你對個機率有誤解

好多人以為隨機就係要各數值均勻輪住出
其實間中就有重覆都係正常現象
因為｢出過唔會咁快又出｣的話
咪即係有路捉，咁就唔係完全隨機啦

吹完水都要計計數，樓主問題等價於：
隨機抽由0至8的整數 (共9個可能)，抽4次，有幾大機率有重覆？

只抽左第一個數時，得一個數當然無重覆
抽第二個數時，唔撞第一個的機率係8/9
抽第三個數時，如果仲未有重覆，就一定要避開頭兩個，所以機率係7/9
抽第四個數時，如此類推係6/9
於是8/9 * 7/9 * 6/9就得約0.539095
其實好吻合實驗
作者: ethernor    時間: 2016-6-10 20:11

Random uses the system clock as the seed/or to generate the seed. So they can be reproduced easily if the attacker knows the time at which the seed was generated. But SecureRandom takes Random Data from your os(they can be interval between keystrokes etc - most os collect these data store them in files -/dev/random and /dev/urandom in case of linux/solaris) and uses that as the seed. 
作者: ethernor    時間: 2016-6-10 20:15

5390xxx次好吻合理論值，只係你對個機率有誤解

好多人以為隨機就係要各數值均勻輪住出
其實間中就有重覆都 ...
EITCo 發表於 2016-6-10 19:13
好多人以為隨機就係要各數值均勻輪住出
其實間中就有重覆都係正常現象
因為｢出過唔會咁快又出｣的話
咪即係有路捉，咁就唔係完全隨機啦

講得非常好，好多人都誤解以為 random 就要 evenly distributed, 咁 given range 1-1000, 第1000個 output 豈不是就會俾你捉到？全錯，咁只係打亂數列，唔係捉唔到路既隨機
作者: ykmran    時間: 2016-6-10 20:23

講得非常好，好多人都誤解以為 random 就要 evenly distributed, 咁 given range 1-1000, 第1000個 out ...
ethernor 發表於 2016-6-10 20:15



   
作者: twaiho2003    時間: 2016-6-10 20:31

回覆 5# EITCo

多謝咁詳細既解答 , 原來真係有咁大機會重履
  1.         Set<Integer> num_set = new HashSet<>();
  2.         int count = 0;
  3.         int repeat_count = 0;
  4.         for (int a=0;a<9;a++) {
  5.             for (int b=0;b<9;b++) {
  6.                 for (int c=0;c<9;c++) {
  7.                     for (int d=0;d<9;d++) {
  8.                         count++;
  9.                         num_set.add(a);
  10.                         num_set.add(b);
  11.                         num_set.add(c);
  12.                         num_set.add(d);

  14.                         if (num_set.size() < 4) {
  15.                             repeat_count++;
  16.                         }
  17.                         num_set.clear();
  18.                     }
  19.                 }
  20.             }
  21.         }
  22.         System.out.println((double) repeat_count / count); // 0.5390946502057613
  23.     }
複製代碼
不過都要加埋你個解答我先清楚D
作者: snoopy11hk    時間: 2016-6-10 22:12

本帖最後由 snoopy11hk 於 2016-6-10 22:17 編輯
5390xxx次好吻合理論值，只係你對個機率有誤解

好多人以為隨機就係要各數值均勻輪住出
其實間中就有重覆都 ...
EITCo 發表於 2016-6-10 19:13



    講起又講, 你咁講我又記番學 C 的時候, 講的 seeding 好似係shift個 nonuniform distribution 的 skewness
其實 random 真係唔等於 uniform distribution
作者: winstercafe    時間: 2016-6-10 22:51

講起又講, 你咁講我又記番學 C 的時候, 講的 seeding 好似係shift個 nonuniform distribution 的 sk ...
snoopy11hk 發表於 2016-6-10 22:12

平均均佈 = 越來越容易估到下一個出咩 = 距離隨機越來越遠
隨機 = 你估佢唔到
作者: snoopy11hk    時間: 2016-6-10 23:00

平均均佈 = 越來越容易估到下一個出咩 = 距離隨機越來越遠
隨機 = 你估佢唔到 ...
winstercafe 發表於 2016-6-10 22:51



    一陣先, 有 D concept 我唔太記得, 純靠我啱啱記得的野 stat 野黎討論
如果係 uniform distribution 的話, 你都唔會估到佢去邊 ga...

而家唔 uniform distribution 的係 expected value?
68% in 1 sigma

有錯請指出, 因為真係唔太記得
作者: gakko    時間: 2016-6-10 23:16

我自己用JAVA既感覺就係
RANDOM出0同1  然後將2位數轉番做你要既10位數
咁樣出黎既10位數就會好好多
同埋粒SEED都要轉
作者: twaiho2003    時間: 2016-6-11 01:32

回覆 5# EITCo


    我仲想知，
如果有n個數字，要gen幾多次先有99%機會出現曬n種
例如nextInt(100), 要gen幾多次先有99%機會出曬0-99
作者: winstercafe    時間: 2016-6-11 05:11

一陣先, 有 D concept 我唔太記得, 純靠我啱啱記得的野 stat 野黎討論
如果係 uniform distribution ...
snoopy11hk 發表於 2016-6-10 23:00



> 而家唔 uniform distribution 的係 expected value?
唔係好明呢句你問乜

> 68% in 1 sigma
呢句係講緊 normal distribution, 唔係 uniform distribution
作者: winstercafe    時間: 2016-6-11 05:12

回覆  EITCo


    我仲想知，
如果有n個數字，要gen幾多次先有99%機會出現曬n種
例如nextInt(100), 要gen ...
twaiho2003 發表於 2016-6-11 01:32



    你咁問
其實你係唔係想要 uniform distribution, 而唔係 random
作者: evec    時間: 2016-6-11 05:18

回覆  EITCo


    我仲想知，
如果有n個數字，要gen幾多次先有99%機會出現曬n種
例如nextInt(100), 要gen ...
twaiho2003 發表於 2016-6-11 01:32


無得計，計唔到，根本每抽一次都係獨立事件，前後根本無關係，
正如賭場有條Bar Show之前的號碼，其實無意義，因為每次均為一樣全新的事項。
作者: twaiho2003    時間: 2016-6-11 08:19

回覆 16# winstercafe


    我真係想知點計
作者: twaiho2003    時間: 2016-6-11 08:26

回覆 17# evec


    如果我又暴力撞的話實有答案
例如骰仔1-6，
順序列出抽6個的所有可能性， 將出現曬1-6既結果 除6^6
然後到7個， 出現1-6既結果除6^7

如此類推，
佢一係就升到某個% limit 左
一係就不斷上，直到我想要既答案

我想求數學解法
作者: 燕飛    時間: 2016-6-11 08:28

有 pseudo random 同 random之分 基本上電腦用既 library gen出黎既都係 pseudo random.

via HKEPC Reader for Android
作者: henrywho    時間: 2016-6-11 08:51

其實隨便將 (pseudo) random number 去除或者攞餘數, 更容易唔覺意整到個 distribution skew 咗.
作者: EITCo    時間: 2016-6-11 11:41

無得計，計唔到，根本每抽一次都係獨立事件，前後根本無關係，
正如賭場有條Bar Show之前的號碼，其實無 ...
evec 發表於 2016-6-11 05:18



如果問抽幾多次可以保證出晒n個數，咁就唔得
不過佢咁問：抽幾多次可以令出晒n個數的機率有99%，咁就有得計

當然每次抽係獨立事件就同意
作者: EITCo    時間: 2016-6-11 11:45

講起又講, 你咁講我又記番學 C 的時候, 講的 seeding 好似係shift個 nonuniform distribution 的 sk ...
snoopy11hk 發表於 2016-6-10 22:12



我無讀過C lib seeding點做所以唔清楚呀
不過做得lib，都唔得抽1至10都抽唔勻咁廢

除非你需要的entropy實在太大
佢個pseudo randomness先會唔夠用
作者: winstercafe    時間: 2016-6-11 12:00

其實呢個問題成日會遇到
嗰時我做 IVRS 抽獎
跟住 user (marketing dept) 話佢地睇番數據
話唔夠 random
問我個 random 係點做
我咪抄啲 research paper reference
結果佢自己諗啲又身份證又每小時計算既 "random" formula
我唔會再同佢多費唇舌
就按佢意思 implement

講到尾佢需要既係 uniform distribution, not random
作者: snoopy11hk    時間: 2016-6-11 12:37

其實呢個問題成日會遇到
嗰時我做 IVRS 抽獎
跟住 user (marketing dept) 話佢地睇番數據
話唔夠 random
...
winstercafe 發表於 2016-6-11 12:00


呢個就係我的意思, 好多事做野就係 expect 左係 uniform distribution, 唔係 random
即係去到大的數, 應該個個數的出現的次數係差唔多一樣
作者: winstercafe    時間: 2016-6-11 13:07

呢個就係我的意思, 好多事做野就係 expect 左係 uniform distribution, 唔係 random
即係去到大的數, 應 ...
snoopy11hk 發表於 2016-6-11 12:37

轉左工
我已經好多年唔使接觸啲不學無術既 marketing user
不過下次聽到有 layman 話想要 random
專業既 Programmer 有責任要問清楚 requirement:
你想要 true random / pseudo random 定係 uniform distribution?
作者: 燕飛    時間: 2016-6-11 13:10

回復 25 #snoopy11hk

用得既Pseudo random repeat cycle at least 2^31 你要既uniform 會出現係每一個 repeat cycle

via HKEPC Reader for Android
作者: EITCo    時間: 2016-6-11 13:12

其實呢個問題成日會遇到
嗰時我做 IVRS 抽獎
跟住 user (marketing dept) 話佢地睇番數據
話唔夠 random
...
winstercafe 發表於 2016-6-11 12:00



係呀好似iPod shuffle咁
如果真係隨機抽歌，係應該會有歌重覆，聽晒都無重覆先奇

不過聽晒先再重覆咁應該叫做在permutation set上用uniform distribution抽
咁講精確D
作者: snoopy11hk    時間: 2016-6-11 13:27

回復 snoopy11hk

用得既Pseudo random repeat cycle at least 2^31 你要既uniform 會出現係每一個 repeat  ...
燕飛 發表於 2016-6-11 13:10



    咁就大鑊啦, let say 我係 一個 pool 400 個波 抽 40000 次, 每次抽完都放番落去
正路就 expect 係 每個波都大約抽到 100 次
但你個 result 唔係, 唔係 uniform distribution
作者: EITCo    時間: 2016-6-11 14:15

本帖最後由 EITCo 於 2016-6-11 14:18 編輯
回覆  EITCo


    我仲想知，
如果有n個數字，要gen幾多次先有99%機會出現曬n種
例如nextInt(100), 要gen ...
twaiho2003 發表於 2016-6-11 01:32


先諗隨機抽1至n的整數，抽r次，問1至n全部都出現過的機率
可以用[attach]1896619[/attach]計
解釋起來太麻煩，唔講解了

不過我唔知條式仲有無得化簡
暫時要解機率幾時>=0.99就要用電腦計或列表

例如抽1至100，要抽916次，先可以令1至100都出現過的機率有99%起
  1. n=100

  3. r                  prob
  4. 100                9.33262*10^-43
  5. 101                4.71297*10^-41
  6. 102                1.20581*10^-39
  7. ...
  8. 496                0.497437
  9. 497                0.500985
  10. 498                0.50452
  11. ...
  12. 914                0.989801
  13. 915                0.989902
  14. 916                0.990003
  15. 917                0.990102
  16. 918                0.990201
複製代碼
作者: 燕飛    時間: 2016-6-11 14:29

回復 29 #snoopy11hk

實驗概率=/=理論概率 邊個教你數學？

via HKEPC Reader for Android
作者: henrywho    時間: 2016-6-11 14:44

你哋好似講緊 "randomized order" 而唔係 "uniform distribution".  
作者: twaiho2003    時間: 2016-6-11 17:48

回覆 30# EITCo

搞掂, 既然要用電腦計, 照寫出黎
  1.     public static void main(String[] args) {
  2.         int n = 100;
  3.         int r = 100;
  4.         Pow pow = new Pow();
  5.         double result = 0.0;

  7.         while (result < 0.99) {
  8.             double initial_result = 1.0;
  9.             for (int i=1;i<n+1;i++) {

  11.                 if (i%2 != 0) {
  12.                     initial_result -= pow.value((double)(n-i) / n,(double) r) * CombinatoricsUtils.binomialCoefficientDouble(n, i);
  13.                 } else {

  15.                     initial_result += pow.value((double)(n-i) / n,(double) r) * CombinatoricsUtils.binomialCoefficientDouble(n, i);
  16.                 }

  18.             }
  19.             result = initial_result;
  20.             System.out.println(r + " " + result);
  21.             r++;
  22.         }
  23.     }
複製代碼
作者: twaiho2003    時間: 2016-6-11 18:10

我仲諗到個好玩D既問題,   但又係唔識計
1-100, gen N個數字,    平均出到幾多個unique number
作者: snoopy11hk    時間: 2016-6-11 18:17

本帖最後由 snoopy11hk 於 2016-6-11 18:24 編輯
回復 snoopy11hk

實驗概率=/=理論概率 邊個教你數學？

via HKEPC Reader for Android
燕飛 發表於 2016-6-11 14:29

呢個好明顥係 stat...

Chebyshev's inequality
作者: EITCo    時間: 2016-6-11 21:02

我仲諗到個好玩D既問題,   但又係唔識計
1-100, gen N個數字,    平均出到幾多個unique number ...
twaiho2003 發表於 2016-6-11 18:10



呢題有簡潔解
http://math.stackexchange.com/qu ... random-numbers-fill
http://math.stackexchange.com/qu ... ng-with-replacement

抽1至n，抽r次，期望有
r ( 1 - (1- 1/r)^n )
個獨特數值

如果 n=r 而又夠大
r ( 1 - (1- 1/r)^n )
會好接近 r (1 - 1/e) (e係natural log base)
作者: EITCo    時間: 2016-6-11 21:13

本帖最後由 EITCo 於 2016-6-11 21:14 編輯
我仲諗到個好玩D既問題,   但又係唔識計
1-100, gen N個數字,    平均出到幾多個unique number ...
twaiho2003 發表於 2016-6-11 18:10


而如果掉轉問
抽1至n，抽到晒全部n個數先停手，期望要抽幾次？

咁仲易解：
1  #第一個獨特數值要抽1次
+ n/(n-1)  #之後有(n-1)/n機會唔撞第一個，所以第二個獨特數值期望要抽n/(n-1)次
+ n/(n-2)  #之後有(n-2)/n機會唔撞頭兩個，所以第三個獨特數值期望要抽n/(n-2)次
+ ...
+ n/1

例如n=10時，就1 + 10/9 + 10/8 + ... + 10/1
呢招計扭蛋要扭幾次先儲齊一套之類好有用 (當無得偷睇下隻蛋係咩)
作者: twaiho2003    時間: 2016-6-13 22:57

回覆 37# EITCo


    一時加一時乘,睇到一舊雲, 睇黎我都要讀返中學數先




歡迎光臨 電腦領域 HKEPC Hardware (https://h0.hkepc.com/forum/) Powered by Discuz! 7.2