Лекция профессора Анкура Моитры в рамках проекта MIT OpenCourseWare посвящена фундаментальным инструментам теории вероятностей — оценкам хвостов распределений и вероятностному методу. В ходе занятия подробно разбираются неравенства Маркова и Чебышёва, слабый закон больших чисел, а также демонстрируется их практическое применение в алгоритмах, криптографии и теории Рамсея. Главная идея заключается в том, что привлечение дополнительной информации о случайной величине позволяет получать экспоненциально более точные математические результаты для сложных комбинаторных структур.
🎯 Введение в оценки хвостов и неравенство Маркова 0:00
Прежде чем перейти к новым инструментам, профессор Моитра кратко возобновляет в памяти студентов базовые понятия теории вероятностей, пройденные на прошлых лекциях. Ранее аудитория уже ознакомилась со следующими фундаментальными элементами:
- Выборочное пространство (sample space) и подмножества событий.
- Понятие независимости и случайных величин как функций из выборочного пространства в вещественные числа.
- Математическое ожидание и дисперсия случайных величин.
- Условная вероятность, условное математическое ожидание и принцип включений-исключений.
Вводные лекции курса наглядно демонстрируют тесную связь между теорией вероятностей и методами подсчета (комбинаторикой), включая производящие функции. Однако центральной темой текущего занятия становятся оценки хвостов (tail bounds) — математические методы, позволяющие понять, насколько вероятно, что случайная величина значительно отклонится от своего математического ожидания.
Математическое ожидание показывает лишь среднее значение, но некоторые случайные величины имеют высокие средние показатели исключительно из-за ничтожно малой вероятности принять гигантское значение. Дисперсия частично описывает концентрацию распределения, но оценки хвостов призваны сделать этот контроль строгим и численным. Главный руководящий принцип лекции: чем больше информации о случайной величине известно исследователю, тем более строгие и узкие границы для ее отклонений он может установить.
Самым простым и базовым инструментом с минимальными требованиями к исходным данным является неравенство Маркова. Для его формулировки и доказательства необходимо лишь одно ключевое условие: случайная величина $X$ должна быть строго неотрицательной. Теорема утверждает, что для любой константы $C > 0$ справедливо следующее соотношение:
$$P(X \ge C) \le \frac{E[X]}{C}$$
Это интуитивно понятно: по мере роста $C$ мы уходим далеко в «хвосты» распределения, и вероятность того, что случайная величина окажется настолько большой, должна стремиться к нулю. Математическое ожидание в числителе выступает в качестве базовой линии: чем оно больше, тем слабее становится итоговая оценка отклонения.
Доказательство неравенства Маркова строится на разделении математического ожидания на отдельные составляющие через закон полного математического ожидания (law of total expectation). Профессор разбивает пространство на два сценария — когда событие $X \ge C$ наступает и когда оно не наступает:
$$E[X] = E[X \mid X \ge C] \cdot P(X \ge C) + E[X \mid X < C] \cdot P(X < C)$$
Эта конструкция аналогична классическому закону полной вероятности, который изучался ранее через формулу Байеса. Проанализировав обе части уравнения, можно заметить, что первое условное ожидание $E[X \mid X \ge C]$ гарантированно не меньше, чем $C$, поскольку в этом подпространстве $X$ всегда принимает значения равные или большие $C$. Вторую же часть уравнения — $E[X \mid X < C] \cdot P(X < C)$ — лектор предлагает просто отбросить. Поскольку $X$ неотрицательна, это слагаемое гарантированно больше или равно нулю, и его удаление лишь уменьшит правую часть, превратив равенство в неравенство:
$$E[X] \ge C \cdot P(X \ge C)$$
Простое алгебраическое перемещение константы $C$ в знаменатель завершает доказательство. Профессор Моитра акцентирует внимание студентов на том, что без условия неотрицательности случайной величины $X$ данный шаг был бы невозможен: если бы $X$ могла принимать отрицательные значения, отбрасываемое слагаемое могло оказаться меньше нуля, и знак неравенства бы не сохранился.
Из неравенства Маркова вытекает удобное следствие (corollary), которое представляет собой эквивалентную форму записи. Если заменить константу $C$ на произведение новой константы $C'$ и математического ожидания $E[X]$, то формула преобразуется к виду:
$$P(X \ge C' \cdot E[X]) \le \frac{1}{C'}$$
Такая интерпретация очень наглядна: вероятность того, что неотрицательная случайная величина превысит свое среднее значение, например, в 2 раза, никогда не может быть больше 0.5 (или 50%). Если бы эта вероятность оказалась выше, то само математическое ожидание распределения было бы рассчитано неверно.
📏 Границы применимости: рост человека и контрпримеры 10:55
Чтобы продемонстрировать, насколько грубой может быть оценка Маркова из-за минимума входящих данных, лектор вводит сквозной практический пример — распределение роста мужчин в США. Средний рост американского мужчины составляет примерно 69 дюймов (около 175 см).
Если применить следствие из неравенства Маркова для оценки вероятности встретить на улице человека, чей рост превышает средний в два раза, мы получим порог в 138 дюймов (11 футов 6 дюймов, или около 350 см). Математика Маркова утверждает: вероятность встретить в Бостоне мужчину с ростом выше 3.5 метров составляет не более 0.5. Очевидно, что в реальности эта вероятность равна нулю, что подчеркивает: неравенство Маркова дает лишь зачаточный, самый верхний ориентир. Оно абсолютно точно с точки зрения математического закона, но биологические и физические случайные величины обычно обладают гораздо большей информацией о своей внутренней структуре (например, известной дисперсией), что позволяет сжимать эти хвосты сильнее.
Для проверки понимания материала профессор Моитра задает аудитории диагностический вопрос: будет ли работать неравенство Маркова, если убрать требование о неотрицательности величины? Он заявляет, что без этого условия утверждение становится «катастрофически ложным», и предлагает построить простой тривиальный контрпример.
Представим случайную величину $X$, которая с вероятностью 0.5 принимает значение 1, а с вероятностью 0.5 принимает значение -1. Математическое ожидание такой величины симметрично и строго равно 0:
$$E[X] = 1 \cdot 0.5 + (-1) \cdot 0.5 = 0$$
Если мы попытаемся рассчитать вероятность того, что $X$ превысит свое математическое ожидание хотя бы в 3 раза (что все еще равно 0), то увидим, что $P(X \ge 0) = 0.5$. Однако по формуле Маркова мы должны были получить оценку меньше $1/3$. Таким образом, требование неотрицательности — это не просто формальность, а фундаментальный содержательный стержень всей теоремы.
📊 Неравенство Чебышёва и сила дисперсии 15:30
Следующим шагом в эволюции оценок хвостов становится неравенство Чебышёва, которое качественно отличается от неравенства Маркова тем, что применимо абсолютно к любым случайным величинам, включая те, что принимают отрицательные значения. Единственное требование — у исследователя должна быть возможность рассчитать или оценить дисперсию случайной величины.
Неравенство Чебышёва формулируется для абсолютного отклонения случайной величины от своего среднего значения на некоторую аддитивную константу $C$:
$$P(|X - E[X]| \ge C) \le \frac{Var(X)}{C^2}$$
Доказательство этого неравенства лаконично, но содержит в себе изящный математический трюк, который впоследствии открывает двери для построения еще более продвинутых оценок хвостов. Первый шаг заключается в том, что событие абсолютного отклонения $|X - E[X]| \ge C$ полностью тождественно событию, при котором квадрат этого отклонения превышает квадрат константы:
$$(X - E[X])^2 \ge C^2$$
Поскольку это одно и то же событие, их вероятности равны. Трюк заключается в искусственном конструировании новой вспомогательной случайной величины $Y$:
$$Y = (X - E[X])^2$$
Величина $Y$ по определению является строго неотрицательной, поскольку представляет собой квадрат вещественного числа, даже если исходная величина $X$ могла быть отрицательной. Раз $Y \ge 0$, мы имеем полное право применить к ней доказанное ранее неравенство Маркова. Записав неравенство Маркова для случайной величины $Y$ с порогом $C^2$, мы получаем:
$$P(Y \ge C^2) \le \frac{E[Y]}{C^2}$$
Вспомнив, что по определению математическое ожидание квадрата отклонения $E[(X - E[X])^2]$ — это и есть дисперсия случайной величины $X$, мы моментально приходим к финальной формуле Чебышёва.
Как и в случае с Марковым, неравенство Чебышёва имеет альтернативную форму записи через среднеквадратичное (стандартное) отклонение $\sigma(X)$, которое является квадратным корнем из дисперсии:
$$P(|X - E[X]| \ge C \cdot \sigma(X)) \le \frac{1}{C^2}$$
В такой трактовке закон Чебышёва звучит следующим образом: вероятность того, что случайная величина отклонится от своего математического ожидания более чем на 2 стандартных отклонения, никогда не превышает $1/2^{2} = 0.25$ (или 25%).
Если мы вернемся к сквозному примеру с ростом американских мужчин, добавив информацию о том, что стандартное отклонение этого распределения составляет примерно 2.7 дюйма, то сможем задействовать Чебышёва. Оценка вероятности того, что рост случайно выбранного мужчины отклонится от среднего (69 дюймов) более чем на два стандартных отклонения (то есть будет выше 6 футов 2.4 дюймов или ниже 5 футов 3.6 дюймов), составит не более 25%. Это все еще верхняя консервативная оценка, но она уже полностью избавлена от абсурдных трехметровых допущений, полученных по методу Маркова.
📈 Слабый закон больших чисел и электоральные опросы 24:41
Неравенство Чебышёва является не просто вычислительным инструментом, оно обладает колоссальной теоретической силой и позволяет доказать один из важнейших столпов теории вероятностей — слабый закон больших чисел (Weak Law of Large Numbers).
Формулировка теоремы требует строгого соблюдения порядка кванторов. Мы фиксируем сколь угодно малое положительное число $\epsilon > 0$, определяющее целевую точность приближения. Пусть случайные величины $X_1, X_2, \dots, X_n$ представляют собой независимые копии некоторой фиксированной базовой случайной величины $X$. Математическое ожидание $X$ равно некоторой константе $C$, а дисперсия является конечной величиной (не уходит в бесконечность). Определим новую случайную величину $S_n$ как их эмпирическое среднее арифметическое:
$$S_n = \frac{1}{n} \sum_{i=1}^{n} X_i$$
Слабый закон больших чисел утверждает, что при стремлении количества испытаний $n$ к бесконечности вероятность того, что среднее арифметическое отклонится от истинного математического ожидания $C$ более чем на $\epsilon$, стремится к нулю:
$$\lim_{n \to \infty} P(|S_n - C| \ge \epsilon) = 0$$
В качестве ментальной модели для понимания этого закона профессор Моитра приводит классический пример социологических электоральных опросов. Представьте, что нам нужно спрогнозировать исход выборов между кандидатом А и кандидатом Б. Истинная доля избирателей, готовых отдать голос за кандидата А, представляет собой скрытое математическое ожидание случайной величины $X$. Чтобы узнать его до выборов, мы совершаем случайные независимые звонки гражданам, фиксируя их ответы в виде реализаций случайных величин $X_i$. Наша стратегия — собрать ответы $n$ человек, посчитать их среднее значение $S_n$ и надеяться, что полученная цифра близка к истине.
Слабый закон больших чисел как раз и гарантирует: какую бы точность $\epsilon$ (например, 0.01 или 1% погрешности) мы ни заложили на старте, всегда можно подобрать такое достаточно большое количество опрошенных $n$, при котором вероятность промахнуться мимо этих границ будет ничтожно мала. Важно понимать, что сам по себе закон в его классической формулировке не дает конкретных цифр, но его доказательство через аппарат оценок хвостов скрывает в себе четкие количественные ориентиры.
Доказательство слабого закона больших чисел через неравенство Чебышёва выглядит прямолинейно. Сначала по линейности математического ожидания проверяется среднее значение величины $S_n$. Поскольку математическое ожидание суммы равно сумме математических ожиданий, среднее значение $S_n$ в точности совпадает с истинным значением $C$, что делает эту оценку несмещенной. Настоящая магия и ключевой фокус происходят при расчете дисперсии $S_n$:
$$Var(S_n) = Var\left(\frac{1}{n} \sum_{i=1}^{n} X_i\right) = \frac{1}{n^2} Var\left(\sum_{i=1}^{n} X_i\right)$$
Поскольку все $X_i$ независимы между собой, дисперсия их суммы строго равна сумме их дисперсий. Линейность дисперсии для суммы работает исключительно в условиях независимости случайных величин. Таким образом, мы получаем:
$$Var(S_n) = \frac{1}{n^2} \cdot n \cdot Var(X) = \frac{Var(X)}{n}$$
Именно этот результат — уменьшение дисперсии среднего значения в $n$ раз — гарантирует улучшение концентрации распределения по мере роста выборки. Профессор Моитра подчеркивает: если бы мы нарушили условие независимости и, к примеру, опрашивали одного и того же человека многократно, дисперсия бы не падала, и метод бы провалился.
Применив неравенство Чебышёва к величине $S_n$, мы получаем явную количественную оценку слабого закона больших чисел:
$$P(|S_n - C| \ge \epsilon) \le \frac{Var(S_n)}{\epsilon^2} = \frac{Var(X)}{n \cdot \epsilon^2}$$
Эта формула наглядно демонстрирует цену точности: если мы заходим зафиксировать ошибку в 5 раз жестче (уменьшить $\epsilon$ в 5 раз), то знаменатель $\epsilon^2$ уменьшится в 25 раз, а значит, нам потребуется собрать в 25 раз больше образцов $n$, чтобы удержать вероятность успеха на прежнем уровне.
🎰 Теория вероятностей в казино и алгоритмах 36:34
Разбирая практические следствия закона больших чисел, профессор Моитра делится со студентами забавной личной историей. При покупке дома в Белмонте его семья регулярно сталкивалась с тем, что на их адрес приходили анонимные дорогие подарки, экзотические фрукты и рождественские венки. Позже выяснилось, что прошлым владельцем здания был технический директор крупнейшей букмекерской компании DraftKings. Профессор шутит, что теперь получает дивиденды от азартных игр в виде бесплатных фруктов, однако с точки зрения математики за этим скрывается суровый закон, известный как «разорение игрока» (gambler's ruin).
Суть концепции заключается в том, что бесконечная игра со случайными исходами, имеющими отрицательное математическое ожидание, неизбежно приводит игрока к полному банкротству. В Лас-Вегасе практически все игры (за редким исключением блэкджека при подсчете карт) обладают отрицательным математическим ожиданием для посетителя.
Наименее агрессивной игрой с этой точки зрения считается крэпс (игра в кости). При определенной консервативной стратегии преимущество заведения (house edge) составляет всего 0.0141. Если упростить, то в каждом раунде игрок выигрывает 1 доллар с вероятностью $P = 0.4929$ и проигрывает 1 доллар в противном случае. Согласно слабому закону больших чисел, по мере увеличения количества раундов средний выигрыш за раунд будет неумолимо сближаться с отрицательным математическим ожиданием, и вероятность остаться в плюсе устремится к нулю. Игрок может временно поймать волну удачи, но на длинной дистанции казино математически гарантированно заберет все его деньги.
Куда более конструктивное применение оценки хвостов находят в сфере компьютерных наук и проектирования рандомизированных алгоритмов. Профессор рассматривает гипотетический рандомизированный алгоритм $A_q$ для работы со входными данными $q$. Алгоритм не является детерминированным, но обладает свойством выдавать правильный ответ чаще, чем ошибочный — например, с вероятностью успеха 2/3. Главный вопрос: сколько раз нужно перезапустить этот алгоритм, чтобы кардинально повысить общую надежность системы?
Такие задачи регулярно возникают в современной криптографии и секторе электронной коммерции при генерации открытых ключей шифрования, где требуется быстро проверять огромные случайные числа на простоту. Существующие эффективные тесты простоты чисел по своей природе являются рандомизированными. Если алгоритм с вероятностью 1/3 ошибется и примет составное число за простое, последствия будут катастрофическими — злоумышленники смогут взломать шифр и получить доступ к банковским счетам или номерам социального страхования. На вопрос профессора о приемлемом уровне риска студенты из аудитории называют цифру в $10^{-30}$.
Если попытаться рассчитать необходимое число повторений $n$ через аппарат неравенства Чебышёва, результат окажется крайне пессимистичным. Для индикаторной величины успеха одного раунда дисперсия составляет:
$$Var(X) = \frac{2}{3} - \frac{4}{9} = \frac{2}{9}$$
При целевом допуске $\epsilon = 1/9$, разделяющем границы успеха и провала, итоговое выражение вероятности ошибки по Чебышёву примет вид функции порядка $18/n$. Чтобы загнать вероятность ошибки под жесткое требование $10^{-10}$ или тем более $10^{-30}$, нам пришлось бы запустить алгоритм $10^{10}$ или $10^{30}$ раз соответственно. Компьютер просто намертво зависнет, выполняя простую операцию проверки ключа.
⚡ Граница Чернова и экспоненциальное ускорение 50:06
Главная слабость доказательства слабого закона больших чисел через неравенство Чебышёва кроется в том, что оно использует информацию о независимости случайных величин лишь частично. Для суммирования дисперсий достаточно, чтобы величины были попарно независимыми (pairwise independent). Алгоритм Чебышёва никак не учитывает, что в реальности наши испытания обладают гораздо более сильным свойством — взаимной (полной) независимостью (mutual independence) по всем подмножествам.
Игнорирование этой информации приводит к медленному полиномиальному затуханию ошибки. Чтобы исправить этот недостаток, лектор представляет фундаментальный инструмент, разработанный прямо в стенах MIT его бывшим коллегой Германом Черновым — границу Чернова (Chernoff bound).
Пусть $X_1, X_2, \dots, X_n$ — взаимно независимые случайные величины Бернулли, принимающие значения 1 или 0 с вероятностью $p_i$. Мы рассматриваем их сумму $X = \sum X_i$, чье суммарное математическое ожидание равно $\mu = \sum p_i$. Примечательно, что Чернов разрешает величинам иметь разные вероятности успеха $p_i$, что делает метод мощнее классического закона больших чисел. Одна из классических форм границы Чернова утверждает, что для любого отклонения $\delta$ вероятность ошибки падает экспоненциально:
$$P(|X - \mu| \ge \delta \mu) \le 2e^{-\frac{\mu \delta^2}{3}}$$
Экспоненциальная скорость падения хвоста принципиально меняет вычислительную сложность алгоритмов. Если мы пересчитаем задачу тестирования чисел на простоту с использованием границы Чернова, то обнаружим, что требуемое число повторений алгоритма $n$ теперь пропорционально не самой крошечной вероятности ошибки, а натуральному логарифму от нее:
$$n \sim O\left(\ln \frac{1}{P_{\text{ошибки}}}\right)$$
Для достижения фантастической надежности с вероятностью сбоя $10^{-10}$ нам потребуется всего лишь взять логарифм $\ln(10^{10}) \approx 23$ раунда, а для уровня защиты $10^{-30}$ — около 69 раундов. Экспоненциальная оценка хвостов позволяет снизить нагрузку на процессоры с астрономических миллиардов до нескольких десятков операций, гарантируя абсолютную безопасность транзакций в Сети.
🧩 Вероятностный метод и коды Библии 56:18
В финальной части лекции профессор Моитра переходит к демонстрации того, как инструменты теории вероятностей применяются в дискретной математике и комбинаторике для доказательства существования сложных структур. Этот подход называется вероятностным методом (probabilistic method). В его основе лежит парадоксальная концепция: вместо того чтобы конструировать экзотический математический объект со сложными свойствами своими руками, мы доказываем, что если выбрать объект абсолютно случайно, то он будет обладать нужными свойствами с вероятностью строго больше нуля.
Ярким примером области применения этого метода является теория Рамсея, изучающая неизбежное появление порядка в больших хаотичных системах. Классическая базовая теорема гласит: на любой вечеринке, где присутствуют как минимум 6 человек, обязательно найдутся либо 3 взаимных друга (все трое знают друг друга), либо 3 абсолютно незнакомых человека (никто из троих не знаком друг с другом).
Исторически этот феномен впервые зафиксировал венгерский социолог, заметивший, что в группах из 20 детей всегда выделяются устойчивые четверки, где либо все дружат, либо все обособлены. Первоначально это считалось особенностью детской психологии, однако великий математик Пауль Эрдеш и его коллеги доказали, что психология тут ни при чем — это жесткое внутреннее свойство графов. На языке теории графов это означает, что если мы возьмем полный граф из 6 вершин и произвольно раскрасим его ребра в два цвета (например, красный — дружба, синий — незнание), внутри обязательно возникнет либо полностью красный, либо полностью синий треугольник. Порядка невозможно избежать, если объект достаточно велик.
В качестве культурологического примера лектор вспоминает прогремевший в середине 1990-х годов феномен «Кодов Библии». Исследователи заявляли, что если взять оригинальный текст Торы на иврите и читать буквы с фиксированным арифметическим шагом (например, каждую 10-ю или 50-ю букву), то в тексте можно обнаружить зашифрованные имена известных раввинов и точные даты их убийств задолго до их рождения.
Вокруг этого строились конспирологические теории о предсказании будущего, однако математический анализ показал, что это была обычная демонстрация теории Рамсея. Текст Торы достаточно велик, чтобы в нем чистым комбинаторным образом возникали любые заданные буквосочетания с определенным шагом. Профессор Моитра отмечает, что оппоненты теории кодов провели аналогичный эксперимент с переводом романа Льва Толстого «Война и мир» на иврит и с тем же успехом обнаружили там аналогичные «пророчества».
🧮 Теорема Ван дер Вардена и нижние оценки 1:03:10
Чтобы строго проиллюстрировать работу вероятностного метода, профессор Моитра предлагает доказать нижнюю границу для теоремы Ван дер Вардена, оперирующей понятием арифметической прогрессии. Математический объект под названием «$k$-членная арифметическая прогрессия» представляет собой упорядоченный набор целых чисел вида:
$$Q_{ab} = {a, a+b, a+2b, \dots, a+(k-1)b}$$
Здесь $a$ выступает стартовым числом, а $b$ является фиксированным шагом. Именно такие цепочки букв искали энтузиасты в «Кодах Библии». Сама теорема Ван дер Вардена утверждает: для любого заданного числа $k$ существует такое достаточно большое число $N$, что при любой двухцветной раскраске (в красный и синий цвета) ряда натуральных чисел от 1 до $N$ внутри этого множества гарантированно найдется монохроматическая (полностью одноцветная) арифметическая прогрессия длиной $k$. Обозначим за $W(k)$ минимальное число $N$, при котором это свойство начинает выполняться железно.
Для небольших значений найти эту границу можно вручную. Например, легко доказать, что $W(3) \ge 9$. Для этого достаточно построить пример раскраски чисел от 1 до 8, где нет ни одной монохроматической тройной прогрессии. Если мы раскрасим числа в ряд по схеме «красный, красный, синий, синий, красный, красный, синий, синий», то перебором убедимся в отсутствии запрещенных троек. Однако доказать точные верхние границы для больших $k$ невероятно сложно, это требует колоссальных мощностей компьютерного перебора.
С помощью вероятностного метода профессору удается изящно доказать сильную нижнюю оценку для больших $k$:
$$W(k) \ge \sqrt{k-1} \cdot \frac{2^{\frac{k-1}{2}}}{2}$$
Стратегия доказательства строится вокруг подтверждения того, что случайная раскраска имеет ненулевую вероятность оказаться идеальной и вообще не содержать монохроматических прогрессий длиной $k$. Фундаментом стратегии служит простая и элегантная лемма: если $X$ — неотрицательная случайная величина, принимающая только целые значения, и ее математическое ожидание строго меньше единицы ($E[X] < 1$), то вероятность события $P(X=0)$ строго больше нуля.
Доказательство леммы строится в три строчки. Мы расписываем математическое ожидание по определению:
$$E[X] = \sum_{i=0}^{\infty} i \cdot P(X=i) = \sum_{i=1}^{\infty} i \cdot P(X=i)$$
Поскольку для всех индексов $i \ge 1$ коэффициент $i$ больше или равен 1, мы можем записать строгое неравенство:
$$E[X] \ge \sum_{i=1}^{\infty} P(X=i) = 1 - P(X=0)$$
Перенеся компоненты, мы получаем: $P(X=0) \ge 1 - E[X]$. Если по условию $E[X] < 1$, то правая часть выражения становится строго больше нуля, что и требовалось доказать.
Теперь профессор Моитра запускает этот механизм для нашей комбинаторной задачи. Пусть мы имеем отрезок чисел от 1 до $N$, и каждое число красится независимо в красный или синий цвет с равной вероятностью 0.5. Наша случайная величина $X$ будет просто подсчитывать суммарное количество получившихся монохроматических $k$-членных прогрессий.
Введем индикаторную случайную величину $I_{ab}$, которая равна 1, если конкретная прогрессия $Q_{ab}$ оказалась одноцветной, и 0 в противном случае. Общее число монохроматических прогрессий $X$ — это просто сумма всех таких индикаторов по всем допустимым парам стартового числа и шага. Математическое ожидание одного такого индикатора равно:
$$E[I_{ab}] = \frac{1}{2^{k-1}}$$
Это объясняется тем, что после того как первое число $a$ случайным образом получило свой цвет, все остальные $k-1$ чисел внутри этой прогрессии обязаны продублировать этот цвет, а вероятность совпадения для каждого шага равна 0.5.
Остается последний шаг — посчитать, сколько всего потенциальных пар $(a, b)$ может существовать внутри отрезка от 1 до $N$. Чтобы вся цепочка уместилась в рамках лимита $N$, стартовая точка $a$ не может превышать $N$, а шаг $b$ ограничен величиной $\frac{N}{k-1}$. Перемножив эти ограничения, мы получаем, что общее число валидных пар не превышает $\frac{N^2}{k-1}$.
Используя свойство линейности математического ожидания, мы суммируем показатели по всем парам:
$$E[X] = \sum E[I_{ab}] \le \frac{N^2}{k-1} \cdot \frac{1}{2^{k-1}}$$
Если мы подставим в качестве длины отрезка $N$ значение, меньшее объявленной ранее границы $\sqrt{k-1} \cdot 2^{\frac{k-1}{2}}$, то вся дробь гарантированно станет меньше единицы. А согласно доказанной лемме, если $E[X] < 1$, то вероятность $P(X=0) > 0$.
Это означает, что среди всех возможных вариантов раскрасок железно существует как минимум одна раскраска, в которой нет ни одной монохроматической прогрессии нужной длины. Вероятностный метод позволил доказать существование этого сложного, защищенного от регулярности объекта без необходимости собирать его вручную.
