Вероятность повторения элементов при случайной выборке

[Foobar]

Допустим есть множество, содержащее n элементов, мы случайным образом пригоршней отбираем m элементов, запоминаем выбранные и кладем их обратно. Причем делаем это k раз. Каждый раз значение m одно и то же. Спрашивается: какова вероятность, что в этих k выборках будет хотя бы одно повторение хотя бы одного элемента? Допустим у нас 3 элемента, мы 2 раза отбираем 1 элемент. Тогда вероятность повторения элемента $(\frac{m}{n})^k=(\frac{1}{3})^2$. Но как это посчитать в общем случае? Вот допустим у нас 10 элементов, мы 3 раза отбираем 2 элемента, какова вероятность наличия хотя бы одного повторения хотя бы одного элемента? Или, наоборот, какова вероятность, что все k раз выбранные элементы будут уникальные? Первый раз выбрать конкретные 2 элемента из 10 мы можем с вероятностью $\frac{1}{5}$, второй раз вероятность не выбрать уже выбранные $\frac{C_{10}^2 - (9+8)}{C_{10}^2}$, третий раз не выбрать уже выбранные вероятность $\frac{C_{10}^2 - (9+8+7+6)}{C_{10}^2}$. Тоесть, если мои рассуждения верны, то вероятность 3 раза выбрать 2 элемента из 10 уникальным образом:
$\frac{1}{5}\cdot\frac{C_{10}^2 - (9+8)}{C_{10}^2}\cdot\frac{C_{10}^2 - (9+8+7+6)}{C_{10}^2}=\frac{1}{5}\cdot\frac{28}{45}\cdot\frac{15}{45}=\frac{84}{2025}$, но это явно как-то мало, интуиция говорит, что вероятность должна быть заметно больше. Помогите?

[Foobar]

Смоделировал ситуацию на питоне:

Используется синтаксис Python

import random

results = dict(unique=0, not_unique=0)

# n - кол-во элементов
# m - сколько отбираем за раз
# k - число выборок
def get_samples(n, m, k):
    results = []
    # исходный массив
    alist = [x for x in range(1, n+1)]
    # k раз делаем выборки:
    for i in range(k):
        sample = random.sample(alist, m)
        for x in sample:
            results.append(x)
   # делаю сет из листа (в сете остаются только уникальные элементы)
    set_res = set(results)
    if len(results) == len(set_res):
        return 'unique'
    else:
        return 'not_unique'

for x in range(100000):
    results[get_samples(10, 2, 3)] += 1

print(results['unique']/100000)
 

В случае если мы рандомно выбираем 3 раза по 2 элемента из 10 элементов получается, что вероятность, что все выборки уникальны, даваемая прогой где-то 0.2. Тоесть ответ правильный наверно $\frac{C_{10}^2 - (9+8)}{C_{10}^2}\cdot\frac{C_{10}^2 - (9+8+7+6)}{C_{10}^2}=\frac{28}{45}\cdot\frac{15}{45}=\frac{84}{405}=0.207$. Но почему так, непонятно.

[NSKuber]

Для начала, вот это:

Foobar в сообщении #1135312 писал(а):

Допустим у нас 3 элемента, мы 2 раза отбираем 1 элемент. Тогда вероятность повторения элемента $(\frac{m}{n})^k=(\frac{1}{3})^2$.

неверно. Можете тоже смоделировать, а лучше ручками перебрать и понять ошибку.
В общем случае легче найти вероятность того, что все элементы во всех выборах будут уникальными, а из неё уже вероятность повторения. Знаете задачу про вероятность совпадения дней рождения? Тут всё точно так же делается.

[Евгений Машеров]

Ну, проще искать вероятность того, что ни одного повторения не будет $P_0=1-P_1$
После первого отбора у нас m помеченных, вероятность того, что ни один из них не будет отобран при втором отборе - вероятность выбрать из n элементов $n-m$ непомеченных, при третьем - $n-2m$ и т.п., и эти вероятности перемножаются. Далее умолкаю, а то решение совсем близко...

[DeBill]

Евгений Машеров в сообщении #1135423 писал(а):

, при третьем - $n-2m$

Э, нет. ТС хочет, чтобы один и тот же элемент встретился во ВСЕХ выборках...
Может, делать так: посчитать вер-ть того, что эл-т нумеро 1 встретился во всех выборках; для нумеро 2, и т.д....
Что эл-ты нумеро 1 и 2 встретились во всех выборках, и т.д. А потом по формуле включений-исключений, сосчитать то что надо...

[Евгений Машеров]

Ну, может быть, Ваши способности к телепатии выше моих.
Я понял

Цитата:

вероятность, что в этих k выборках будет хотя бы одно повторение хотя бы одного элемента

как вероятность того, что хотя бы один элемент после k выборок окажется дважды и более выбранным.
Возможно, Ваша трактовка правильнее - но пусть ТС ответит, что он имел в виду.

[Foobar]

Цитата:

как вероятность того, что хотя бы один элемент после k выборок окажется дважды и более выбранным.

да, именно так

-- 03.07.2016, 13:30 --

Цитата:

неверно. Можете тоже смоделировать, а лучше ручками перебрать и понять ошибку.

Да, понял, $\frac{1}{9}$ это будет вероятность того, что только 1 элемент повторится дважды (из случая когда выбираем 2 раза 1 элемент из 3). А у меня 3 элемента, значит вероятность повторения любого из элементов $\frac{1}{3}$. А в примере с 10-ю элементами получается что надо $\frac{1}{5}$ тоже умножить на 5 и как раз получается в ответе вероятность уникальных элементов 0.207, вроде разобрался, спасибо.