Есть два множества. В первом К1 элементов (все различные), во втором - К2 (и тут тоже все различны). Пересечение этих множеств непусто и его мощность равняется Х элементов. Из первого множества наугад тянут n элементов. Из второго наугад тянут m элементов. Какова вероятность того, что среди вытянутых элементов k совпадут?

Свои идеи?

Идея следующая рассмотреть несколько гипотез:
Гипотеза 1: выбрав из K1 n элементов мы получим только 1 элемент из X, выбрав из K2 m элементов мы получим 1 элемент из X
Гипотеза 2: выбрав из K1 n элементов мы получим только 1 элемент из X, выбрав из K2 m элементов мы получим 2 элемент из X
...
Гипотеза : выбрав из K1 n элементов мы получим только 2 элемента из X, выбрав из K2 m элементов мы получим 1 элемент из X
...

Дальше для каждой гипотезы оценить вероятность совпадения k элементов. Здесь тоже возникает вопрос как это сделать. А дальше по формуле полной вероятности.

Прокатит такой подход?

А смысл в таких гипотезах? При Гипотезе 1 совпадет максимум 1 элемент, а нужно, чтобы совпало k. Рассмотрите варианты: сколько нужно выбрать из X в первый набор, сколько из них должно попасть во второй набор.

Правильно ли я понял идею: нужно рассматривать следующие гипотезы:

Гипотеза 1: Выбрав n элементов из K1 k из них оказалось из X, выбрав m элементов из K2 k из них оказались в {n} (выбранными из первого набора).
Гипотеза 2: Выбрав n элементов из K1 k+1 из них оказалось из X, выбрав m элементов из K2 k из них оказались в {n} (выбранными из первого набора).
Гипотеза 3: Выбрав n элементов из K1 k+2 из них оказалось из X, выбрав m элементов из K2 k из них оказались в {n} (выбранными из первого набора).
...
Гипотеза последняя: Выбрав n элементов из K1 max{n, X} из них оказалось из X, выбрав m элементов из K2 k из них оказались в {n} (выбранными из первого набора).

В этом случае событие
Выбрав n элементов из K1 k+i из них оказались из X будет иметь вероятность
C(k+i, X)*C(n-(k+i)), K1-X)/C(n, K1)
C(k+i, X) - количество способов вытащить k+i элементов из X
C(n-(k+i), K1-X) - количество способов вытащить остальные элементы из K1
C(n, K1) - общее количество комбинаций.

а событие
выбрав m элементов из K2 k из них оказались в {n} будет иметь вероятность
C(k, k+i)*C(m-k, K2- (k+i))/C(k,X)

Тогда ответ:

sum(
C(k+i, X)*C(n-(k+i)), K1-X)/C(n, K1) *
C(k, k+i)*C(m-k, K2- (k+i))/C(k,X),
i = 0...max{n, X}
)
Подскажите, пожалуйста, размышления верны?

Ну да, ровно так. И вряд ли этот ответ можно упростить.

Спасибо за помощь!

Теперь мне нужно решить в некотором смысле обратную задачу:
Есть два множества К1 и К2 с непустым пересечением Х (Х неизвестно). Из К1 выбрали n элементов, из К2 - m. Нашли пересечение выборок - k. Требуется оценить Х (количество элементов).

Единстенный подход к решению, который мне приходит в голову, найти распределение Х и мат. ожидание. Но это очень алгоритмически трудоемко, т.к. Количество элементов в К1 и К2 несколько десятков тысяч. Есть ли какой-то более гуманный способ решения данной проблемы?
Спасибо.

Это более простая задача. Средние вообще считаются легче, чем распределения. Оценка метода моментов для Х пойдёт?

Пусть все элементы пронумерованы, в первом множестве шарики с номерами 1,...,K1-X,K1-X+1,...,K1, во втором - шарики с номерами K1-X+1,...,K1, K1+1,...,K1-X+K2. Здесь жирным выделены шары в количестве Х штук, общие для двух множеств.
И есть первый набор - X1,...,Xn со значениями 1,...,K1, и второй набор - Y1,...,Ym со значениями K1-X+1,...,K1-X+K2.

Найдём математическое ожидание числа совпадений Xi с Yj: величина I(Xi = Yj) принимает значения 1 или 0 в зависимости от того, случилось совпадение или нет, и имеет распределение Бернулли с параметром p=P(Xi = Yj)=P(X1=Y1)=P(X1=K1-X+1, Y1=K1-X+1)+...+P(X1=K1,Y1=K1) = X*1/K1*1/K2 = X/(K1*K2).

Тогда матожидание числа совпадений есть
E(sum[i,j] I(Xi = Yj)) = sum[i,j] E I(Xi = Yj) = sum[i,j] P(Xi = Yj) = n*m*X/(K1*K2).

Поэтому оценку метода моментов Х' для Х ищем, приравнивая полученное число совпадений k к его среднему: k=n*m*X'/(K1*K2), X' = k*K1*K2 / nm.

Это состоятельная, несмещённая, асимптотически нормальная оценка.

Спасибо. Мне казалось, что решение будет немного сложнее ;-).

Возможно ли решить более обобщенную задачу:

Есть n множеств K1, K2, ..., Kn. Из каждого из них выбирают случайно элементы m1, m2, ..., mk соответсвенно. Известны все пересечения выборок (попарные, каждой тройки, каждой четверки и тд) k_ij, k_ijl, ...
Требуется определить количество элементов в объединении K1, K2, ..., Kn (Естественно, в объединении каждый элемент будет встречаться только один раз).

По аналогии с предыдущим объяснение решить не получилось. Здесь нужно применять другой подход?
Спасибо.

Может, в пересечении?

Именно в объединении. В предыдущей задача нужно было пересечкние для того, чтобы его потом вычесть ;-).

Тогда формула включения-исключения и такие же оценки метода моментов. Но прежде чем писать какие-то формулы, хочу поинтересоваться происхождением задачи и тем, как и где предполагается использовать полученные оценки.