В современной теории вероятностей и комбинаторике существует мощный инструмент, позволяющий предсказывать поведение сложных систем, даже если мы не знаем всех деталей их внутреннего устройства. Речь идет о неравенстве ограниченных разностей (Bounded Differences Inequality), также известном как неравенство Азумы — Хёфдинга. Этот метод доказывает, что если результат сложной функции зависит от множества независимых факторов, и ни один из этих факторов не может в одиночку радикально изменить итоговый результат, то значение функции будет очень близко к своему среднему показателю.
🧱 Суть неравенства ограниченных разностей 0:11
Неравенство Азумы — Хёфдинга (Azuma-Hoeffding Inequality) утверждает, что функции от независимых случайных величин обладают свойством концентрации вокруг своего математического ожидания, если они удовлетворяют условию «гладкости» .
Ключевые условия применимости теоремы:
- Независимость переменных: Мы имеем на входе набор случайных величин $X_1, X_2, \dots, X_n$, которые обязательно должны быть независимыми .
- Ограниченность изменений: Функция $f$, принимающая эти переменные, должна обладать важным свойством: при изменении значения только одной входной координаты результат функции должен изменяться не более чем на фиксированную константу (в базовом примере — на 1) .
Если эти условия соблюдены, то случайная величина $Z$, полученная в результате вычисления функции, будет демонстрировать очень быструю экспоненциальную убыль вероятности при отклонении от среднего значения . Это означает, что «хвосты» распределения (вероятность того, что значение окажется намного больше или намного меньше среднего) исчезают крайне быстро по мере роста отклонения $\Lambda$ .
🪙 Пример 1: Сумма подбрасываний монеты 3:42
Самый простой пример применения этого неравенства — обычное суммирование независимых булевых величин (0 или 1), что эквивалентно подсчету количества «орлов» при серии бросков монеты .
В данном случае:
- Функция просто складывает значения всех $n$ испытаний .
- Изменение одного входного значения (замена 0 на 1 или наоборот) меняет общую сумму ровно на 1 .
- Применяя неравенство ограниченных разностей к этой функции, мы получаем границы отклонения для биномиального распределения .
Этот частный случай также известен как граница Чернова (Chernoff bound). По словам лектора, доказательство неравенства ограниченных разностей во многом опирается на те же идеи, что и вывод границы Чернова . Математическое ожидание в этом случае равно $n/2$, и вероятность значительного отклонения от него крайне мала.
🎟️ Пример 2: Задаче о коллекционере купонов 5:49
Второй пример касается более сложной, нелинейной функции — задачи о коллекционере купонов. Представьте, что в коробке есть $n$ видов различных купонов. Вы последовательно достаете $n$ купонов, каждый раз возвращая их обратно .
Случайная величина $Z$ в данном сценарии — это количество купонов, которые вы так и не увидели после всех попыток (недостающие купоны) . Хотя эта функция сложнее простого суммирования, она все равно удовлетворяет условию ограниченных разностей: если вы измените результат всего одного вытягивания из коробки, общее количество недостающих купонов в коллекции изменится не более чем на 1 .
Основные факты об этой задаче:
- Ожидаемое количество недостающих купонов составляет примерно $n/e$ (где $e$ — основание натурального логарифма) .
- Неравенство Азумы — Хёфдинга позволяет строго доказать, что реальное количество отсутствующих купонов будет очень близко к этому числу .
🕸️ Пример 3: Хроматическое число случайного графа 9:53
Наиболее глубокое применение неравенства демонстрируется на классической теореме Шамира и Спенсера (1980-е годы), касающейся теории графов . Речь идет о хроматическом числе случайного графа Эрдёша — Реньи $G(n, p)$.
Хроматическое число — это минимальное количество цветов, необходимых для раскраски вершин графа так, чтобы никакие две соединенные вершины не имели одинаковый цвет . Это сложная, трудновычисляемая величина, зависящая от наличия или отсутствия множества ребер.
Тонкость применения неравенства здесь заключается в правильном выборе независимых переменных:
- Наивный подход: Рассматривать каждое возможное ребро как отдельную переменную. Всего таких ребер $n(n-1)/2$. Однако это дает слишком слабые границы .
- Эффективный подход (Кластеризация): Лектор объясняет метод группировки переменных по вершинам. Мы представляем граф как последовательность наборов ребер, идущих от каждой вершины $i$ к вершинам с меньшими номерами .
Ключевой аргумент Шамира и Спенсера заключается в том, что если мы изменим все ребра, инцидентные одной конкретной вершине, хроматическое число графа изменится не более чем на 1 . Это объясняется тем, что в худшем случае нам просто понадобится один дополнительный цвет для этой конкретной измененной вершины .
Благодаря такой формулировке, мы можем рассматривать хроматическое число как функцию от всего лишь $n$ независимых «блоков» переменных и применить неравенство Азумы — Хёфдинга . Это доказывает, что хроматическое число случайного графа крайне сильно сконцентрировано вокруг своего среднего значения, даже если мы не знаем точно, чему это среднее равно .
