В лекции профессора Массачусетского технологического института (MIT), опубликованной в рамках проекта OpenCourseWare, подробно рассматриваются фундаментальные комбинаторные и теоретические инструменты теории вероятностей. Автор разбирает классические вероятностные задачи, такие как распределение проверенных работ и сбор купонов, чтобы подвести слушателей к пониманию принципа включений-исключений, линейности ожидания и свойств независимых случайных величин. Главной целью материала становится переход от базовых интуитивных оценок к строгому контролю поведения случайных факторов с помощью дисперсии и оценок хвостов распределений.
📑 Задача о проверке работ: в поисках полной неудачи 0:38
В качестве главной мотивирующей проблемы лектор предлагает рассмотреть классическую задачу, которая ранее часто встречалась на собеседованиях в ведущих технологических и финансовых компаниях. Представьте класс из $n$ студентов, каждый из которых сдает свою письменную работу преподавателю. После проверки все работы перемешиваются, и преподаватель случайным образом раздает их обратно, не пытаясь сопоставить имена. Ключевой вероятностный вопрос заключается в следующем: какова вероятность того, что абсолютно все студенты получат чужие работы, то есть ни один человек в аудитории не получит свой собственный результат?.
Для решения этой сложной аналитической задачи её необходимо разбить на более простые составляющие. Автор вводит вспомогательные события $A_i$, обозначающие, что $i$-й студент получил свою собственную работу обратно. В таком контексте искомая вероятность полной ошибки выражается как пересечение дополнений этих событий:
$$P(\overline{A_1} \cap \overline{A_2} \cap \dots \cap \overline{A_n})$$
Для удобства вычислений это выражение можно переписать через закон дополнения как единица минус вероятность того, что хотя бы один студент получит свою работу правильно:
$$1 - P(A_1 \cup A_2 \cup \dots \cup A_n)$$
Именно точное вычисление вероятности объединения этих зависимых событий становится главной математической целью занятия.
📊 Геометрическая интуиция: диаграммы Венна для малых классов 3:40
Для построения базовой интуиции лектор предлагает вернуться к наглядным геометрическим образам и рассмотреть простейшие случаи для малых значений $n$. Начнем с класса, состоящего всего из двух студентов ($n = 2$). Вероятность объединения двух событий $P(A_1 \cup A_2)$ геометрически представляет собой площадь двух пересекающихся кругов на плоскости исходов. Если просто сложить вероятности $P(A_1)$ и $P(A_2)$, результат окажется неверным, поскольку область их пересечения будет учтена дважды. Чтобы скорректировать этот избыточный подсчет, необходимо вычесть область их совместного наступления:
$$P(A_1 \cup A_2) = P(A_1) + P(A_2) - P(A_1 \cap A_2)$$
В данной задаче вероятность $P(A_1)$ равна $1/2$, как и $P(A_2)$. Однако пересечение $P(A_1 \cap A_2)$ требует осторожности: если первый студент получил свою работу, то у второго просто нет иного выбора, кроме как получить свою. Следовательно, условная вероятность $P(A_2 \mid A_1)$ равна $1$, а вероятность пересечения составляет $1/2$, а не $1/4$, как могло бы показаться в случае ложного предположения о независимости событий.
Ситуация усложняется для трех студентов ($n = 3$). Попытка сложить индивидуальные вероятности и вычесть попарные пересечения снова приводит к ошибке. Анализ диаграммы Венна показывает, что при вычитании трех «лепестков» попарных пересечений центральная область — где пересекаются все три круга — вычитается полностью. Для восстановления баланса центральную область необходимо прибавить обратно:
$$P(A_1 \cup A_2 \cup A_3) = P(A_1) + P(A_2) + P(A_3) - P(A_1 \cap A_2) - P(A_1 \cap A_3) - P(A_2 \cap A_3) + P(A_1 \cap A_2 \cap A_3)$$
Для трех студентов индивидуальные вероятности равны $1/3$, попарные — $1/6$, а тройное пересечение — также $1/6$. Итоговая вероятность того, что хотя бы один студент получит свою работу, составляет $2/3$.
🧮 Общая формула включений-исключений и магия числа e 12:43
Обобщая замеченную закономерность, профессор формулирует общее правило включений-исключений, справедливое для любого количества событий. Процесс представляет собой последовательное приближение к истинной вероятности через чередование знаков: сначала идет наивное суммирование индивидуальных вероятностей (пересчет), затем вычитание попарных пересечений (недосчет), добавление тройных пересечений и так далее. Последний член формулы имеет знак $(-1)^{n+1}$.
Чтобы применить эту формулу к задаче о студентах, необходимо использовать аппарат комбинаторики и ввести понятие биномиального коэффициента $\binom{n}{r}$, определяющего количество способов выбрать $r$ элементов из $n$. Количество попарных пересечений задается формулой:
$$\binom{n}{2} = \frac{n(n-1)}{2}$$
В общем случае для $r$ событий формула биномиального коэффициента выглядит как:
$$\binom{n}{r} = \frac{n(n-1)\dots(n-r+1)}{r!}$$
Подставляя вычисленные вероятности пересечений для нашей задачи (где для пары вероятность равна $\frac{1}{n(n-1)}$, для тройки — $\frac{1}{n(n-1)(n-2)}$), мы сталкиваемся с массовым сокращением элементов в формуле. Итоговое выражение для вероятности того, что никто не получит свою работу, принимает вид знаки-чередующегося ряда:
$$1 - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + \dots$$
Из математического анализа известно, что этот бесконечный ряд сходится к значению $1/e$. Профессор отмечает изящество этого результата: фундаментальная математическая константа возникает в простой комбинаторной задаче. Более того, существует эвристическое объяснение: при больших $n$ события становятся «почти независимыми». Вероятность не получить свою работу для каждого студента стремится к $1 - 1/n$, а для всего класса — к $(1 - 1/n)^n$, что в пределе дает то же самое значение $1/e$.
📐 Строгое доказательство методом математической индукции 26:18
Хотя формула включений-исключений выглядит интуитивно понятной, она требует строгого математического доказательства, которое профессор проводит методом математической индукции. Базовый случай для $n=1$ и $n=2$ уже доказан геометрически с помощью диаграмм Венна. На индуктивном шаге предполагается, что формула верна для некоторого значения $n$, и требуется доказать её справедливость для размера $n+1$.
Суть доказательства заключается в искусной группировке членов выражения для $n+1$ элементов. Профессор разделяет все слагаемые на две группы:
- Члены, которые не включают в себя элемент с индексом $n+1$ (по предположению индукции эта группа сводится к вероятности объединения первых $n$ событий).
- Члены, содержащие элемент $n+1$ в различных пересечениях.
Для работы со второй группой вводятся вспомогательные события $B_i = A_i \cap A_{n+1}$. Пересечение этих вспомогательных событий $B_i \cap B_j$ эквивалентно тройному пересечению $A_i \cap A_j \cap A_{n+1}$, поскольку повторение элемента $A_{n+1}$ не меняет состав множества. Это позволяет переписать всю вторую группу как формулу включений-исключений для новых событий $B_i$, что представляет собой вероятность объединения множеств $B_1 \cup B_2 \cup \dots \cup B_n$.
Используя законы де Моргана, данное объединение сводится к пересечению объединения первых $n$ событий (обозначим его за $C$) с событием $A_{n+1}$. В итоге вся громоздкая формула для шага $n+1$ сводится к базовому случаю для двух событий — $C$ и $A_{n+1}$:
$$P(C) + P(A_{n+1}) - P(C \cap A_{n+1}) = P(C \cup A_{n+1})$$
Это полностью доказывает универсальную формулу включений-исключений для любого числа событий.
⚖️ Сила линейности математического ожидания 38:26
Переходя ко второму сюжету лекции, преподаватель демонстрирует удивительный контраст между вычислением точных вероятностей и подсчетом математического ожидания. Если поиск вероятности полной ошибки потребовал доказательства сложнейшей теоремы, то ответ на вопрос «сколько в среднем студентов получат свои работы обратно?» занимает всего несколько строчек на доске. Помогает в этом свойство линейности математического ожидания, согласно которому математическое ожидание суммы случайных величин всегда равно сумме их математических ожиданий.
Для расчета вводится случайная величина количества правильных совпадений, которая представляется в виде суммы индикаторных переменных $I(A_i)$ для каждого студента:
$$X = \sum_{i=1}^n I(A_i)$$
Индикаторная переменная принимает значение $1$, если событие произошло, и $0$ в противном случае. Математическое ожидание индикатора события в точности равно вероятности этого события. Поскольку вероятность для каждого студента получить именно свою работу составляет $1/n$, мы получаем сумму из $n$ слагаемых, каждое из которых равно $1/n$:
$$E[X] = \sum_{i=1}^n \frac{1}{n} = 1$$
Таким образом, среднее количество студентов, получивших свои работы, всегда равно единице, независимо от общего размера класса. Профессор подчеркивает уникальность линейности математического ожидания: это свойство работает всегда, вне зависимости от того, являются ли исследуемые события независимыми или сильно связанными друг с другом.
🎟️ Задача о коллекционере купонов и распределение дней рождения 41:32
В качестве развития темы математического ожидания профессор предлагает разобрать более сложную прикладную задачу, известную в теории вероятностей как «задача о коллекционере купонов» (Coupon Collector's Problem). В условиях лекции она формулируется через опрос студентов в большой аудитории: сколько человек нужно спросить об их дне рождения, чтобы собрать все 365 дней в году?. Предполагается, что дни рождения распределены равномерно по всему календарю.
Решение этой задачи в лоб крайне затруднительно, но применение трюка с декомпозицией случайной величины делает его тривиальным. Общее время (или количество студентов) $T$ разбивается на сумму интервалов $T = T_0 + T_1 + \dots + T_{364}$, где каждое $T_i$ — это количество шагов, необходимых для перехода от $i$ уже собранных уникальных дней рождения к $i+1$ уникальному дню.
В самом начале процесс идет мгновенно: первый же спрошенный студент дает новый день рождения ($T_0 = 1$). Однако ближе к концу, когда в коллекции уже есть 364 дня, найти студента с последним оставшимся днем рождения становится очень трудно. Вероятность успеха на каждом шаге $i$ составляет:
$$P_i = \frac{365 - i}{365}$$
Опираясь на ранее изученную модель «среднего времени до отказа» (Mean Time to Failure, MTTF), где математическое ожидание геометрического распределения равно $1/p$, мы находим среднее время для каждого интервала как $1/P_i$. Применяя линейность математического ожидания, получаем сумму:
$$E[T] = \frac{365}{365} + \frac{365}{364} + \dots + \frac{365}{1} = 365 \sum_{i=1}^{365} \frac{1}{i}$$
Данная сумма представляет собой произведение числа $n$ на $n$-е гармоническое число, которое ведет себя как $n \ln n$. Численный расчет показывает, что для сбора всех 365 дней потребуется опросить примерно в $6.47$ раза больше людей, чем дней в году (около 2360 студентов).
📉 Независимость случайных величин и математическая природа дисперсии 52:13
В финальной части лекции профессор переходит к строгому определению независимости случайных величин, которое значительно строже независимости простых событий. Две случайные величины $f$ и $g$ называются независимыми, если для любых действительных чисел $\alpha$ и $\beta$ индуцированные ими события ${x \mid f(x) = \alpha}$ и ${x \mid g(x) = \beta}$ являются независимыми в классическом смысле. Важнейшая лемма гласит: если случайные величины независимы, то математическое ожидание их произведения равно произведению их математических ожиданий.
Доказательство этой леммы строится на разбиении пространства исходов по значениям $\alpha$ и $\beta$, вынесении констант за знак суммы и использовании свойства независимости вероятностей их пересечения. В качестве контрпримера, показывающего важность условия независимости, профессор приводит индикатор события $A$ и индикатор его дополнения. Их произведение всегда равно нулю (так как событие и его дополнение не могут произойти одновременно), в то время как произведение их математических ожиданий отлично от нуля.
Понятие независимости критически важно для работы с дисперсией — мерой того, насколько сильно случайная величина отклоняется от своего среднего значения. Формально дисперсия определяется как:
$$\text{Var}(f) = E[(f - E[f])^2]$$
Существует альтернативная, часто более удобная для вычислений формула дисперсии:
$$\text{Var}(f) = E[f^2] - (E[f])^2$$
В отличие от математического ожидания, дисперсия суммы случайных величин равна сумме их дисперсий только в случае их полной независимости. При доказательстве этого факта квадрат суммы раскрывается с образованием перекрестных членов. Благодаря независимости величин эти перекрестные члены превращаются в произведение двух нулевых смещений и полностью исчезают. Профессор завершает лекцию примером из социологии и политологии: именно это свойство аддитивности дисперсии независимых величин объясняет, почему крупномасштабные социологические опросы и предвыборное моделирование (polling) способны невероятно быстро сходиться к истинным средним показателям по популяции.
