некоторое множество с элементов, и 1 , 2 , . , , , М фиксированные положительные целые числа меньше или равно п .
С элементами быть с равной вероятностью, образцы отдельно и независимо друг от друга взяты из без замены, размер которых 1 , а 2 , . , , , М , соответственно.
Мощность пересечения образцов имеет, в общем, поддерживают равным , но какой дистрибутив следует?
combinatorics
Прохладная вода
источник
источник
Ответы:
Вот еще один подход, который не предполагает рекурсии. Тем не менее, он по-прежнему использует суммы и продукты, длина которых зависит от параметров. Сначала я дам выражение, потом объясню.
У нас есть
РЕДАКТИРОВАТЬ: В конце написания всего этого я понял, что мы можем немного консолидировать вышеприведенное выражение, комбинируя биномиальные коэффициенты в гипергеометрические вероятности и триномиальные коэффициенты. Что бы это ни стоило, пересмотренное выражение выглядит так: Здесь является гипергеометрической случайной величиной, где отрисовки взяты из совокупности размера имеющей состояний успеха.
отвлечение
Давайте получим некоторые обозначения, чтобы сделать комбинаторные аргументы немного легче для отслеживания (надеюсь). Повсюду мы рассматриваем и фиксированными. Мы будем использовать для обозначения набора упорядоченных кортежей , где каждый , удовлетворяющийS a1,…,am C(I) m (L1,…,Lm) Li⊆S
Мы также будем использовать для идентичной коллекции, за исключением того, что нам требуется вместо равенства.C′(I) L1∩⋯∩Lm⊇I
Ключевое наблюдение заключается в том, что относительно легко сосчитать. Это потому, что условие эквивалентно для всех , поэтому в некотором смысле это устраняет взаимодействия между различными значениями . Для каждого число удовлетворяющих требованию, равно , поскольку мы можем построить такое , выбрав подмножество размераа затем unioning с . Это следует из тогоC′(I) L1∩⋯∩Lm⊇I Li⊇I i i i Li (|S|−|I|ai−|I|) Li S∖I ai−|I| I
Теперь наша первоначальная вероятность может быть выражена через следующим образом:C
Мы можем сделать два упрощения здесь прямо сейчас. Во-первых, знаменатель такой же, как Во-вторых, аргумент перестановки показывает, чтозависит только от через кардинальность, Поскольку существуют подмножества в имеющие мощность , из этого следует, что где - произвольное фиксированное подмножество имеющее мощность
Сделав шаг назад, мы теперь сократили проблему до показа, что
Пусть будут различными подмножествами образованными путем добавления ровно одного элемента в . Тогда (Это просто говорит о том, что если , то содержит но также не содержит никаких дополнительных элементов.) Теперь мы преобразовали проблему -counting в проблему -counting, которую мы знаем больше, как ее решить. Более конкретно, у нас естьJ1,…,Jn−k S I0
Мы можем применить включение-исключение, чтобы обработать размер выражения объединения выше. Здесь решающее значение имеет то, что для любого непустого , Это потому, что если содержит число , то оно также содержит их объединение. Также отметим, что множество имеет размер, СледовательноI⊆{1,…,n−k}
Наконец, подставляя выражение в конце в уравнение дляВыше и, суммируя сумму, получаем как заявлено.|C(I0)|
источник
Я не знаю аналитического способа решения этой проблемы, но вот рекурсивный способ вычисления результата.
Для вы выбираете элементов из из которых были выбраны ранее. Вероятность выбора элементов, которые пересекаются с в вашем втором розыгрыше, определяется гипергеометрическим распределением:m=2 a2 n, a1 k≤min{a1,a2} L1
Мы можем назвать результатМы можем использовать ту же логику, чтобы найти где - мощность пересечения трех выборок. Затем,b2. P(b3=k∣n,b2,a3), b3
Найдите это для каждого . Последнее вычисление не является численно сложным, поскольку является просто результатом предыдущего вычисления, а является вызовом гипергеометрическое распределение.k∈{0,1,2,…,min(a1,a2,a3)} P(b2=l∣n,a1,a2) P(b3=k∣n,b2=l,a3)
В общем, чтобы найти вы можете применить следующие рекурсивные формулы: для и есть просто сказать, чтоP(bm)
Вот это в R:
источник