2016-01-06 11 views
0

Я хочу имитировать парадокс дня рождения в java. По какой-то причине мой результат (вероятность) продолжает очень близко приближаться к 1, например. моделирование (10) -> 0,9268. В начале вы можете увидеть вероятности, по которым мои симуляции должны быть близки. Я давно искал ошибку в своем коде, поэтому надеюсь, что кто-то из вас сможет мне помочь. Я искал другие коды парадоксальности дня рождения, но ни один из них, похоже, не смог помочь мне с моим странным выходом. стр. вы можете игнорировать // 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(); 
} 

}

+1

метода 'итерации()' должно возвращать логическое значение, для того, или нет, есть студенты с таким же днем ​​рождения. Количество возвращаемых истинных значений, деленное на количество вызовов, равно вероятности. – Andreas

ответ

4

Вы не очищая birthdaySet между итераций. Измените его с поля на локальную переменную, чтобы предотвратить такие ошибки, потому что зачем вам это нужно в качестве поля в первую очередь?

С другой стороны, generateBirthday следует использовать Random.nextInt(DAYS_IN_YEAR). Экземпляр Random является основным кандидатом в качестве поля. Что это такое? LCG random; строка в любом случае?

UPDATE

Метод iteration() должен возвращать логическое значение, для того, или нет, есть студенты с таким же днем ​​рождения. Количество возвращаемых истинных значений, деленное на количество вызовов, равно вероятности.

Поскольку существует относительное малое число дней в году, булево массив будет быстрее, чем 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 
+0

Спасибо за вашу помощь, изменили его на локальную переменную, чтобы обновить каждую итерацию. После этого все получилось! LCG означает линейный конгруэнтный генератор, это способ создания случайных чисел. Потому что я должен был внедрить его в парадокс дня рождения, часть его кода уже была там. – Marnix

1

Как Андреаса уже штаты birthdaySet должны быть очищены от итераций или набора будет содержать данные из предыдущего моделирования

Однако есть еще один фатальный недостаток в дизайне, чтобы увидеть это посмотреть на на странице википедии:

В теории вероятностей проблема рождения или парадоксальный день рождения связана с вероятностью того, что в наборе из n случайно выбранных людей некоторые пары из них будут иметь t он тот же день рождения.

Это шанс, что существует как минимум 2 человека с тем же днем ​​рождения. Это означает, что как только 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(); } 
} 
+0

Спасибо, я тоже неправильно интерпретировал парадокс дня рождения. Я обновил свой код, и он работает! – Marnix