生日悖論

Question

我想模擬java中的生日悖論。出於某種原因，我的輸出（概率）一直非常接近1模擬（10） - > 0,9268。在開始，你可以看到我的模擬應該接近的概率。我一直在尋找我的代碼中的一個錯誤，因此我希望你們中的任何一個能夠幫助我。我查了其他生日悖論的代碼，但他們沒有一個能夠幫助我處理奇怪的輸出。 p.s.你可以忽略// TODO，一旦我得到代碼並運行，就會解決這個問題。 謝謝先進！

static final int DAYS_IN_YEAR = 365; 
static final int NUMBER_OF_SIMULATIONS = 500; 

LCG random; 
HashSet<Integer> birthdaySet = new HashSet<Integer>(); 

BirthdayProblem2(){ 
    birthdaySet.clear(); 
    random = new LCG(); //random numbers between 0 and 1 
} 

int generateBirthday(){ //generates random birthday 
    return (int) Math.round(Math.random()*DAYS_IN_YEAR); //TODO use LGC 
} 

double iteration(int numberOfStudents){ //one iteration from the simulation 
    int sameBirthdays = 0; 

    for (int i = 0; i < numberOfStudents; i++){ 
     int bd = generateBirthday(); 

     if (birthdaySet.contains(bd)){ 
      sameBirthdays++; 
     } else { 
      birthdaySet.add(bd); 
     }   
    } 
    return (double) sameBirthdays/numberOfStudents; //probability of two students having the same birthday 
} 

void simulation(int numberOfStudents){ 
    double probabilitySum = 0; 
    for (int i = 0; i < NUMBER_OF_SIMULATIONS; i++){ 
     probabilitySum += iteration(numberOfStudents); 
    } 
    System.out.printf("For n=%d -> P=%.4f \n", numberOfStudents, probabilitySum/NUMBER_OF_SIMULATIONS); 
} 

private void start() { 

    simulation(10); //should be about 0.1 
    simulation(20); //should be about 0.4 
    simulation(23); //should be about 0.5 
    simulation(35); //should be about 0.8 
} 

public static void main(String[] argv) { 
    new BirthdayProblem2().start(); 
} 

}

Answer 1

您還沒有清除迭代之間的birthdaySet。將其從一個字段更改爲一個局部變量將防止類似的錯誤，因爲爲什麼你首先需要它作爲一個字段？

在不同的筆記上，generateBirthday應該使用Random.nextInt(DAYS_IN_YEAR)。 Random的實例是領域的主要候選人。無論如何，LCG random;是什麼？

UPDATE

方法iteration()應該返回boolean值，對於是否有學生同一天生日。返回的真值數除以呼叫數等於概率。

由於是在一年內相對較小的天數，一個布爾數組會比Set快，所以這裏是更新的代碼：

private static final int DAYS_IN_YEAR = 365; 
private static final int NUMBER_OF_SIMULATIONS = 500; 
private Random rnd = new Random(); 
private int generateBirthday() { 
    return this.rnd.nextInt(DAYS_IN_YEAR); 
} 
private boolean iteration(int numberOfStudents) { //one iteration from the simulation 
    boolean[] present = new boolean[DAYS_IN_YEAR]; 
    for (int i = 0; i < numberOfStudents; i++) { 
     int birthday = generateBirthday(); 
     if (present[birthday]) 
      return true; 
     present[birthday] = true; 
    } 
    return false; 
} 
void simulation(int numberOfStudents){ 
    int count = 0; 
    for (int i = 0; i < NUMBER_OF_SIMULATIONS; i++) 
     if (iteration(numberOfStudents)) 
      count++; 
    System.out.printf("For n=%d -> P=%.4f%n", numberOfStudents, (double)count/NUMBER_OF_SIMULATIONS); 
} 

樣本輸出

For n=10 -> P=0.1340 
For n=20 -> P=0.4120 
For n=23 -> P=0.5080 
For n=35 -> P=0.8160 

For n=10 -> P=0.1200 
For n=20 -> P=0.4120 
For n=23 -> P=0.5260 
For n=35 -> P=0.8140 

For n=10 -> P=0.1260 
For n=20 -> P=0.3920 
For n=23 -> P=0.5080 
For n=35 -> P=0.7920 

將NUMBER_OF_SIMULATIONS增加到5_000_000：

For n=10 -> P=0.1167 
For n=20 -> P=0.4113 
For n=23 -> P=0.5075 
For n=35 -> P=0.8145 

For n=10 -> P=0.1168 
For n=20 -> P=0.4113 
For n=23 -> P=0.5072 
For n=35 -> P=0.8142 

Answer 2

由於已經規定，birthdaySet應該迭代或設定會從以前的模擬包含數據之間被清除安德烈亞斯

但是有一個在你的設計中的另一個致命的缺陷，看到它看維基百科頁面：

在概率論中，生日問題或生日悖論涉及在一組n個隨機選擇的人中，其中一些人有t他同樣的生日。

這是有至少兩個同一生日的人的機會。這意味着只要2相等，就應該返回1。

我把它概括在下面的代碼

import java.util.HashSet; 
import java.util.Random; 

public class BirthdayProblem2 { 
    static final int DAYS_IN_YEAR = 365; 
    static final int NUMBER_OF_SIMULATIONS = 500; 

    Random random; 
    HashSet<Integer> birthdaySet = new HashSet<Integer>(); 

    BirthdayProblem2() { random = new Random(); } 

    int generateBirthday() { return random.nextInt(DAYS_IN_YEAR); } 

    double iteration(int numberOfStudents) { //one iteration from the simulation 
     birthdaySet.clear(); 

     for (int i = 0; i < numberOfStudents; i++) { 
      int bd = generateBirthday(); 

      if (birthdaySet.contains(bd)) { 
       return 1.0; 
      } 

      birthdaySet.add(bd); 
     } 

     return 0.0; 
    } 

    void simulation(int numberOfStudents) { 
     double probabilitySum = 0; 

     for (int i = 0; i < NUMBER_OF_SIMULATIONS; i++) { 
      probabilitySum += iteration(numberOfStudents); 
     } 

     System.out.printf("For n = %d -> P = %.4f \n", numberOfStudents, probabilitySum/NUMBER_OF_SIMULATIONS); 
    } 

    private void start() { 
     simulation(10); //should be about 0.1 
     simulation(20); //should be about 0.4 
     simulation(23); //should be about 0.5 
     simulation(35); //should be about 0.8 
    } 

    public static void main(String... whatever) { new BirthdayProblem2().start(); } 
}