Как решать обобщенную проблему дней рождения

Vlad128

Типа есть N дней в «году». Есть распределение вероятностей дня рождения по этим N дням: p(z=k k = 1..N.
Есть выборка размером M. Надо определить вероятность попадания хотя бы двух точек из M в один день.
Есть аналитический метод?

griz_a

Боюсь, что сильно лучше чем
1-\sum_{i_1<i_2<...<i_M\le N} M! p_{i_1}...p_{i_M}
вряд ли что-то будет

Vlad128

ну еще есть уточнение, что распределение имеет некоторую структуру: все дни разделены на небольшое количество регионов, где-то 3-4 региона, в каждом из которых вероятности одинаковые. N ~ пара тысяч. M ~ пара сотен.

griz_a

Если точность большая не нужна, то я бы решал так. Посчитал бы вероятность попасть в каждый из регионов p_1,p_2,p_3,p_4. Считал бы, что в них попадает Mp_1,Mp_2,Mp_3,Mp_4 наблюдений. Для каждой группы бы считал вероятность того, что совпадений нет (это уже простая задача о днях рождениях)

griz_a

А если нужна точная формула, то сворачиваешь ту, которую я выше написал.
Там будет C_7^4=35 вариантов множителей, при каждом считается коэффициент (на самом деле принципиальных подсчетов будет не так много - либо все множители входят; либо один нет, а один в квадрате; либо два нет, а один в кубе; либо два нет, а два в квадрате; либо один множитель в 4ой).

Vlad128

хм, спасибо. Надо будет попробовать.
Оставить комментарий
Имя или ник:
Комментарий: