Парадокс дня рождения

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

}

Источник

2 ответа

Решение

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

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

ОБНОВИТЬ

метод 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
Источник

Поскольку andreas уже заявляет, BirthdaySet должен быть очищен между итерациями, или набор будет содержать данные из предыдущего моделирования

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

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

Это шанс, что существует как минимум 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(); }
}
Источник
Другие вопросы по тегам