Заключительная лекция курса 6.1200 в Массачусетском технологическом институте (MIT) под руководством Бринмора Чепмена была посвящена подведению итогов изучения теории вероятностей и разбору так называемых «оценок хвостов» (tail bounds). Преподаватель продемонстрировал, как математические инструменты — от неравенства Маркова до границ Чернова — позволяют оценивать вероятность экстремальных отклонений случайных величин от их математического ожидания. На практических примерах, включая распределение мест в аудитории и результаты экзаменов, лектор наглядно показал, как добавление новой информации о дисперсии и независимости данных драматически повышает точность математических прогнозов.
📊 Введение в дисперсию и линейность 0:14
В начале занятия Бринмор Чепмен напомнил студентам базовые определения, необходимые для работы с оценками отклонений. Математический аппарат исследования случайных величин опирается на понятие дисперсии ($Variance$). Дисперсия случайной величины $R$ обозначается как $Var(R)$ и содержательно представляет собой математическое ожидание квадрата отклонения величины от её среднего значения:
$$Var(R) = E[(R - E[R])^2]$$
Стандартное (или среднеквадратичное) отклонение — это просто квадратный корень из дисперсии. В практических расчетах и статистических исследованиях оно используется даже чаще, поскольку измеряется в тех же единицах, что и сама случайная величина.
Для вывода последующих теорем лектор предложил использовать эквивалентную, но более удобную формулу дисперсии. Она формулируется как разность математического ожидания квадрата величины и квадрата её математического ожидания:
$$Var(R) = E[R^2] - (E[R])^2$$
Важным свойством дисперсии является её линейность, которая выполняется при определенных ограничениях. Чепмен обратился к аудитории с вопросом о том, какое условие необходимо для того, чтобы дисперсия суммы случайных величин была равна сумме их индивидуальных дисперсий. Студенты предположили, что величины должны быть взаимно независимыми (mutually independent).
Однако лектор уточнил, что математически можно использовать более слабое условие. Для линейности дисперсии достаточно попарной независимости (pairwise independence) случайных величин. Таким образом, если имеется набор попарно независимых величин $R_1, R_2, \dots, R_n$, то дисперсия их суммы строго равна сумме их дисперсий, что существенно упрощает анализ сложных систем.
🔍 Неравенство Маркова: интуиция и формальное доказательство 4:39
В качестве первого инструмента для оценки «хвостов» распределений было представлено неравенство Маркова. Чтобы подвести студентов к пониманию его сути, Чепмен предложил разобрать мысленный эксперимент с присутствующими в зале. Если выбрать случайного студента в аудитории, где всего насчитывается 21 ряд (от 0 до 20), и принять за случайную величину $R$ номер ряда, на котором он сидит, то среднее значение (математическое ожидание $E[R]$) можно условно принять равным 8.
Лектор задал вопрос: что можно сказать о вероятности того, что случайно выбранный студент окажется на 16-м ряду или еще дальше от сцены? Попытки студентов привязать решение к функции распределения (CDF) или дисперсии провалились, поскольку для этого требовались избыточные данные, которых у гипотетического наблюдателя нет. Предположение о равномерном распределении студентов по зале также оказалось неверным — на практике передние ряды всегда заполняются плотнее.
Решение кроется в базовой логике: число 16 ровно в два раза больше среднего значения 8, а номера рядов не могут быть отрицательными. Если бы более половины всех студентов сели на ряды от 16 до 20, то их вклад в среднее значение распределения автоматически поднял бы общее математическое ожидание выше 8. Следовательно, на задних рядах чисто физически может находиться не более половины аудитории.
Этот вывод формулируется как неравенство Маркова: если $R$ — неотрицательная случайная величина, то для любого положительного $x$ вероятность того, что $R$ превысит или сравняется с $x$, ограничивается сверху отношением математического ожидания к этому порогу:
$$P(R \ge x) \le \frac{E[R]}{x}$$
Для примера с рядами это дает:
$$P(R \ge 16) \le \frac{8}{16} = \frac{1}{2}$$
Для доказательства этого утверждения Чепмен применил закон полной вероятности для математического ожидания (Law of Total Expectation), разбив пространство исходов по условию отношения величины к порогу $x$:
$$E[R] = E[R \mid R \ge x] \cdot P(R \ge x) + E[R \mid R < x] \cdot P(R < x)$$
Лектор пошагово разобрал каждый элемент полученной суммы:
- Поскольку в первом слагаемом рассматривается условие $R \ge x$, математическое ожидание $E[R \mid R \ge x]$ гарантированно будет не меньше, чем $x$.
- Во втором слагаемом, в силу изначального условия неотрицательности случайной величины ($R \ge 0$), условное математическое ожидание $E[R \mid R < x]$ также не может упасть ниже 0.
Обнулив вторую часть уравнения ради получения нижней границы, математики приходят к выражению:
$$E[R] \ge x \cdot P(R \ge x)$$
Перенос переменной $x$ в левую часть (при условии $x > 0$) завершает доказательство неравенства Маркова. Существует также альтернативная форма записи этого правила, оперирующая масштабирующим коэффициентом $C$: вероятность того, что величина превысит свое среднее значение в $C$ раз, составляет не более $\frac{1}{C}$.
📈 Оптимизация границ Маркова с помощью сдвига и переворота переменной 17:07
При всей своей элегантности неравенство Маркова часто дает слишком грубые оценки. Тем не менее, Чепмен показал, как с помощью нехитрых математических трансформаций можно искусственно усилить этот инструмент. В качестве примера были взяты результаты гипотетического экзамена, где оценки студентов варьируются в диапазоне от 30% до 100%, а средний балл ($E[R]$) равен 75%. Задача — оценить вероятность того, что случайный студент набрал 90% или больше.
Прямое применение формулы Маркова показывает, что порог в 90% превышается с вероятностью не более $\frac{75}{90}$, что составляет примерно 83%. Однако мы знаем, что никто не может получить меньше 30%. Чтобы учесть эту информацию, лектор предложил ввести новую случайную величину $R' = R - 30$. Минимальное значение $R'$ теперь равно 0, что делает ее идеально подходящей для теоремы Маркова, а новое математическое ожидание, согласно принципу линейности, уменьшается до $75 - 30 = 45$.
Событие $R \ge 90$ эквивалентно событию $R' \ge 60$. Повторный расчет границы через модифицированную переменную дает принципиально иной результат:
$$P(R' \ge 60) \le \frac{E[R']}{60} = \frac{45}{60} = \frac{3}{4} = 75\%$$
Таким образом, простой сдвиг шкалы позволил снизить верхнюю границу вероятности с 83% до 75%, сделав математическое утверждение более сильным и строгим.
Аналогичный трюк («переворот» переменной) применим и для оценки нижних границ распределения. Если требуется узнать вероятность того, что студент сдал экзамен хуже чем на 65% ($P(R \le 65)$), прямое вычисление через дополнение ($P(R \ge 66)$) выдаст бессмысленную верхнюю границу больше единицы. Вместо этого вводится переменная потерь $S = 100 - R$, отражающая количество недобранных баллов. Она также неотрицательна, её среднее значение равняется $100 - 75 = 25$, а искомое условие превращается в $S \ge 35$. Расчет по Маркову дает изящное ограничение в $\frac{25}{35} = \frac{5}{7}$ (около 71,4%).
В завершение раздела Бринмор Чепмен продемонстрировал опасность игнорирования критерия неотрицательности величин. Если бы шкала оценок $T$ гипотетически уходила в отрицательную зону (от -30 до 100) при том же среднем значении 75, попытка рассчитать вероятность получения балла $\ge 90$ напрямую по формуле Маркова опять дала бы 83%. Но этот результат неверен, поскольку нарушено базовое допущение теоремы. Корректный подход требует предварительного сдвига в положительную зону: $T' = T + 30$, что после пересчета дает законную и безопасную, пусть и более слабую верхнюю границу в $\frac{105}{120} = \frac{7}{8}$ (87,5%).
Для наглядности лектор привел экстремальный контрпример: случайная величина $R$, принимающая значения $+1$ или $-1$ с равной вероятностью на основе подбрасывания монеты. Её математическое ожидание равно 0. Попытка узнать вероятность исхода $R \ge \frac{1}{2}$ без учета знака привела бы к абсурдному выводу, что порог достигается с вероятностью $\le 0$, хотя на самом деле правильный ответ — 50%.
🎯 Проверка на точность: когда неравенство Маркова бессильно 41:57
Естественным вопросом со стороны студентов стал вопрос о том, является ли граница Маркова «точечной» (tight), то есть существуют ли распределения, на которых она выполняется как строгое равенство. Лектор подтвердил: без привлечения дополнительных данных о структуре распределения улучшить эту оценку невозможно.
Для доказательства Чепмен обратился к классической задаче о проверке сотовых телефонов на крутящемся подносе «Ленивая Сьюзан» (Lazy Susan), на который люди складывают свои устройства, а затем забирают случайные обратно. Пусть $R$ — количество людей, получивших свой собственный телефон. Как было доказано ранее, математическое ожидание этой величины всегда равняется единице, независимо от общего числа участников $n$.
Если мы ищем вероятность идеального исхода, при котором все $n$ человек получат свои аппараты обратно ($P(R = n)$), неравенство Маркова устанавливает верхний предел:
$$P(R = n) \le \frac{E[R]}{n} = \frac{1}{n}$$
В сценарии с подносом «Ленивая Сьюзан» механика процесса такова, что поднос либо смещается идеально (и тогда все $n$ человек одновременно забирают свои телефоны), либо сдвигается неверно (и тогда результат равен нулю). Вероятность идеального совпадения в такой системе составляет ровно $\frac{1}{n}$, что в точности совпадает с верхней границей Маркова. Это доказывает, что в условиях абсолютного минимума информации формула работает идеально.
Ситуация кардинально меняется, если раздача телефонов происходит не через фиксированные сдвиги подноса, а путем полностью случайной перестановки (random permutation). Математическое ожидание $E[R]$ здесь по-прежнему равно 1, и Марков упрямо предсказывает предел в $\frac{1}{n}$. Однако реальная вероятность того, что случайная перестановка окажется строго тождественной, равна абсолютно другой величине — $\frac{1}{n!}$. В этом случае марковская оценка драматически промахивается, выдавая слишком завышенный и неэффективный прогноз.
📐 Неравенство Чебышева: сила знания дисперсии 47:50
Чтобы преодолеть слабость оценки Маркова в системах с низкой дисперсией, математики используют более продвинутый инструмент — неравенство Чебышева. Оно подключает к расчету информацию о разбросе данных и не накладывает никаких ограничений на знак случайной величины:
$$P(|R - E[R]| \ge x) \le \frac{Var(R)}{x^2}$$
Доказывается неравенство Чебышева изящным способом — через то же неравенство Маркова. Для этого исследователи конструируют искусственную неотрицательную величину $R' = (R - E[R])^2$. По определению, её математическое ожидание является дисперсией исходной системы ($Var(R)$). Событие отклонения величины от среднего значения на величину $x$ в абсолютном выражении полностью идентично событию, когда возведенное в квадрат отклонение превышает $x^2$. Применив формулу Маркова к переменной $R'$ с порогом $x^2$, ученые автоматически получают квадратичное убывание вероятности ошибки, сформулированное Чебышевым.
Бринмор Чепмен вернулся к примеру с результатами экзаменов, расширив вводные данные: средний балл равен 75, но теперь нам достоверно известна дисперсия системы, составляющая 25. Требуется заново оценить риск того, что студент наберет меньше 65 баллов.
Математический трюк заключается в переходе к симметричному отклонению. Вероятность провала ($R \le 65$) гарантированно меньше или равна вероятности объединения двух экстремальных событий: провала ниже 65 ИЛИ взлета выше 85. Это условие можно лаконично записать в терминах модуля отклонения от среднего: $|R - 75| \ge 10$.
Подставив значения в формулу Чебышева, лектор получил впечатляющий результат:
$$P(|R - 75| \ge 10) \le \frac{25}{10^2} = \frac{25}{100} = \frac{1}{4} = 25\%$$
Для сравнения, базовая модификация неравенства Маркова на тех же данных могла гарантировать лишь порог в 71,4%. Подключение фактора дисперсии позволило сузить неопределенность до 25%.
В терминах стандартных отклонений ($\sigma$) закон Чебышева декларирует, что вероятность выхода случайной величины за пределы двух стандартных отклонений ($2\sigma$) от математического ожидания никогда не превысит $\frac{1}{4}$ (или 25%).
По шутливому замечанию Чепмена, школьная статистика зачастую преподается ужасно, из-за чего у людей ломается понимание этих границ. Те, кто привык работать исключительно с нормальным (гауссовым) распределением, помнят, что выход за пределы $2\sigma$ там составляет всего пару процентов. Но нормальное распределение — это частный случай, где мы знаем о форме функции абсолютно все. Неравенство же Чебышева уникально тем, что оно работает вообще для любых распределений, гарантируя жесткий порог в 25% даже в самых непредсказуемых системах.
🚀 Граница Чернова: экспоненциальная точность взаимной независимости 1:01:35
Если Марков дает линейное убывание границы отклонения, а Чебышев — квадратичное, то вершиной эволюции tail bounds в рамках университетского курса является граница Чернова (Chernoff Bound). Она применима в ситуациях, когда случайная величина формируется как сумма большого числа независимых элементов.
Пусть случайная величина $T$ представляет собой сумму $T_1 + T_2 + \dots + T_n$, где все компоненты являются строго ограниченными и, что критически важно, взаимно независимыми (mutually independent) величинами. Для любого коэффициента порога $C \ge 1$ граница Чернова утверждает:
$$P(T \ge C \cdot E[T]) \le e^{-(C \ln C - C + 1) E[T]}$$
Несмотря на громоздкий вид степени, содержательно это означает, что с ростом масштаба системы вероятность критического отклонения падает не линейно и не квадратично, а обратно экспоненциально.
В рамках краткого эскиза доказательства Чепмен раскрыл главный секрет вывода этой формулы: исследуемая величина подвергается операции экспонирования. Математики конструируют новую переменную $T' = C^T$. Поскольку при $C \ge 1$ функция является монотонно возрастающей, исходное вероятностное неравенство можно безболезненно переписать в терминах степеней, после чего к ней применяется стандартное неравенство Маркова. За счет свойств экспоненты и взаимной независимости слагаемых, превращающей математическое ожидание произведения в произведение математических ожиданий, на выходе получается колоссальная математическая точность.
В финале лекции Бринмор Чепмен наглядно сопоставил эффективность всех трех инструментов на классической задаче о подбрасывании $n$ симметричных монет. Пусть случайная величина $R$ — это число выпавших орлов. Её математическое ожидание составляет $\frac{n}{2}$. Задача — оценить сверху вероятность получить аномально высокое число орлов, превышающее или равное $\frac{3n}{4}$.
Лектор поочередно применил все три методологии:
- Неравенство Маркова. Расчет строится как отношение среднего к порогу: $\frac{n/2}{3n/4}$. Результат равен стабильной константе $\frac{2}{3}$ (около 66,7%). Граница получается крайне слабой и никак не улучшается при увеличении числа бросков.
- Неравенство Чебышева. Поскольку броски независимы, дисперсия суммы равна сумме дисперсий индивидуальных бросков, что дает $Var(R) = \frac{n}{4}$. Величина требуемого отклонения от среднего составляет $\frac{n}{4}$. Подстановка в формулу Чебышева дает оценку $\frac{4}{n}$. Эта граница несравнимо лучше марковской: с ростом числа бросков $n$ вероятность получить аномалию уверенно стремится к нулю по линейному закону.
- Граница Чернова. Подставив коэффициент масштабирования $C = \frac{3}{2}$ в экспоненциальную формулу, математики получают выражение вида $e^{-\Omega(n)}$. Вероятность получить 75% орлов вместо положенных 50% исчезает с колоссальной скоростью, схлопываясь по экспоненте при наращивании серии экспериментов.
Завершая семестр, Бринмор Чепмен поблагодарил студентов за работу, переадресовал все лавры успеха команде ассистентов (особенно выделив учебного ассистента Лили) и пожелал аудитории удачи на финальном экзамене. К поздравлениям присоединился сопреподаватель курса Эрик Демейн, под аплодисменты аудитории закрыв учебный год.
