Два внешне похожих способа случайной рассылки дают разные вероятности при конечном числе адресатов. При этом математическое ожидание числа совпадений и предельная вероятность совпадения оказываются одинаковыми.
Условие: бумажные письма
У Дон Жуана n знакомых женщин с разными именами. Он пишет каждой отдельное письмо, но случайно раскладывает письма в конверты: ровно по одному письму в каждый. Найдите вероятность, что хотя бы одно письмо попадёт правильному адресату, её предел при n → ∞ и ожидаемое число правильных доставок.
Считаем все n! перестановок равновероятными; n ≥ 1.
Вероятность хотя бы одного совпадения
Пусть Aᵢ — событие, что письмо i попало своему адресату. Вероятность совпадения для заданных k адресатов равна (n − k)!/n!: остальные письма можно переставлять произвольно.
Набор этих адресатов выбирается C(n, k) способами. Поэтому сумма вероятностей всех k-кратных пересечений равна C(n, k)(n − k)!/n! = 1/k!.
По формуле включений и исключений:
P(хотя бы одно совпадение) = 1 − 1/2! + 1/3! − … + (−1)n + 1/n!.
Единица минус эта вероятность — вероятность перестановки без неподвижных точек, которую называют беспорядком.
Предел и математическое ожидание
Используя ряд для e−1, получаем:
lim P(хотя бы одно совпадение) = 1 − 1/e ≈ 0,6321.
Для каждого адресата вероятность правильного письма равна 1/n. Число правильных доставок — сумма n индикаторов, поэтому по линейности ожидания:
E(число совпадений) = n · (1/n) = 1.
Независимость этих индикаторов не нужна. Для бумажных писем они, вообще говоря, зависимы.
Вторая модель: сообщения в Telegram
Теперь для каждой женщины независимо выбирается одно случайное сообщение из общего файла с n сообщениями. Каждая получает одно сообщение, но одинаковое сообщение может уйти нескольким адресатам.
В источнике для этой модели указано, что предел и ожидание остаются прежними. Полную формулу для конечного n добавим отдельно: каждый адресат получает чужое сообщение с вероятностью 1 − 1/n, а выборы независимы.
P(хотя бы одно совпадение) = 1 − (1 − 1/n)n.
Её предел снова 1 − 1/e, а ожидание числа совпадений снова 1.
Почему модели нельзя смешивать
Например, при n = 3 бумажные письма дают вероятность 2/3, независимые сообщения — 19/27. Для писем выбор одного конверта меняет возможные варианты остальных; для независимой рассылки повторения разрешены.
Ответы о пределах и ожиданиях совпадают не потому, что модели одинаковы. Важно проверять, разрешено ли повторное использование одного объекта.
Связанные материалы
Дискретная математика и теория вероятностей · Математика.
Борис Демешев и участники probability_pro · задача 3.5 · CC BY 4.0. Адаптировано; добавлены выводы и конечная формула второй модели.