E8 Вероятностный метод (Эрдёш)

Идея метода: чтобы доказать, что объект с нужным свойством существует, введём случайную модель и покажем, что нужное свойство выполняется с положительной вероятностью. Раз вероятность > 0, такой объект обязан существовать.

Метод изобретён Полом Эрдёшем и стал революцией в комбинаторике: он доказывает существование, не конструируя объект явно. Аналогия: вы утверждаете, что в ящике есть красный шар, потому что случайно выбранный шар оказывается красным с вероятностью $1/3 > 0$ — значит, хотя бы один красный шар там есть.

Ключевые приёмы:
- Линейность математического ожидания: $\mathbb{E}[X+Y] = \mathbb{E}[X] + \mathbb{E}[Y]$ (без предположения о независимости) — это позволяет считать ожидание сложных случайных величин.
- Первый момент (метод первого момента): если $\mathbb{E}[X] > 0$, то $X > 0$ с положительной вероятностью.
- Изменение знака ожидания: если $\mathbb{E}[X] < n$, то $X < n$ с положительной вероятностью — что-то можно улучшить.

Метод работает особенно хорошо для задач о раскрасках графов, турнирах, гиперграфах и разбиениях, где конструктивный подход крайне сложен.

• Метод первого момента (First Moment Method): Если $\mathbb{E}[X] > 0$, то $\mathrm{P}(X > 0) > 0$, значит существует исход, при котором $X > 0$. Условие: $X \geq 0$ — неотрицательная случайная величина. Когда использовать: доказать существование объекта, считая его ожидаемое количество > 0.

• Марковское неравенство: $\mathrm{P}(X \geq a) \leq \dfrac{\mathbb{E}[X]}{a}$ для $a > 0$, $X \geq 0$. Когда использовать: показать, что случайная конфигурация с малым количеством «плохих» элементов существует.

• Линейность ожидания: $\mathbb{E}\left[\sum_{i=1}^n X_i\right] = \sum_{i=1}^n \mathbb{E}[X_i]$ — без условий на независимость. Когда использовать: считать суммарное число «плохих» пар/рёбер/событий через индикаторы.

• Метод Лавасса (Lovász Local Lemma, LLL): Если каждое «плохое событие» $A_i$ зависит не более чем от $d$ других событий, $\mathrm{P}(A_i) \leq p$, и $ep(d+1) \leq 1$, то все хорошие события реализуются одновременно с положительной вероятностью. Когда использовать: задачи о раскрасках с локальными ограничениями (продвинутый уровень).

• Случайная раскраска: Раскрасим элементы независимо и равновероятно в 2 цвета. Для каждого «плохого» подмножества $S$ размера $k$ вероятность монохромности $2^{1-k}$. Когда использовать: задачи о разбиениях множеств, $k$-раскрасках рёбер.

• Случайная равновероятная раскраска: каждый элемент множества красится в один из 2 цветов с вероятностью $1/2$. Суммируем вклад «плохих» конфигураций через линейность ожидания.

• Случайная перестановка: выбираем случайный порядок элементов и считаем ожидаемое число «хороших» позиций.

• Удаление плохих элементов: показываем, что $\mathbb{E}[\text{число плохих}] < 1$. Удаляем все плохие элементы. Оставшееся $\geq \mathbb{E}[X] - \mathbb{E}[\text{плохих}] > 0$.

• Альтернирование знаков: вместо $\mathbb{E}[X] > 0$ используем $\mathbb{E}[X] < n$ — значит, найдётся конфигурация с $X < n$.

• Индикаторные случайные величины: для каждого «плохого» объекта $i$ вводим $\mathbf{1}_{A_i}$ и суммируем $\mathbb{E}[\mathbf{1}_{A_i}] = \mathrm{P}(A_i)$.

Поверхностные признаки (что буквально написано):
- «Докажите, что существует раскраска/разбиение/расстановка с таким-то свойством».
- «Докажите, что найдётся множество размера $\geq k$ с таким-то свойством».
- «Докажите существование турнира/графа, в котором...».

Структурные признаки (форма выражения, объекты):
- Задача о существовании объекта с глобальным свойством, когда конструктивный подход неочевиден.
- Нижняя оценка на размер независимого множества, число рёбер нужного цвета, длину пути.
- Большое число объектов, среди которых «в среднем» нужное свойство выполняется.

Цель задачи (что от тебя хотят):
- Доказать существование (не найти явно) объекта с заданным свойством.
- Получить нижнюю оценку на максимальный размер структуры (независимое множество, антицепь).
- Показать, что «случайный» выбор с высокой вероятностью или с положительной вероятностью даёт нужное.

Задача 1. Двухраскраска без монохромного подмножества

Условие: Дано $n$ элементов и $m$ подмножеств, каждое размера $k$. Докажите, что если $m < 2^{k-1}$, то существует двухраскраска элементов в цвета «красный» и «синий» такая, что ни одно из $m$ подмножеств не монохромно.

Источник: классическая задача Эрдёша (вероятностный метод, 1963)

Как думать (рассуждение ученика$):
1. $Что вижу? Нужно доказать существование раскраски — без явного построения. Триггер: вероятностный метод.$2. *$Первый ход: красим каждый элемент случайно: с вероятностью $1/2$ в красный, с вероятностью $1/2$ в синий, независимо.$3. *$Ключевая идея: для каждого подмножества $S$ размера $k$ вероятность монохромности (все красные или все синие) равна $2 \cdot (1/2)^k = 2^{1-k}$.$4. *$Подсчёт: ожидаемое число монохромных подмножеств $\leq m \cdot 2^{1-k} < 2^{k-1} \cdot 2^{1-k} = 1$.$5. *$Вывод: ожидаемое число «плохих» подмножеств $< 1$, значит существует раскраска с 0 монохромных подмножеств.

Решение:

Красим каждый из $n$ элементов независимо и равновероятно в один из двух цветов. Для подмножества $S_i$ ($|S_i| = k$) введём индикатор $X_i = 1$, если $S_i$ монохромно. Тогда$$\mathrm{P}(X_i = 1) = \mathrm{P}(\text{все красные}) + \mathrm{P}(\text{все синие}) = \left(\frac{1}{2}\right)^k + \left(\frac{1}{2}\right)^k = 2^{1-k}.$$

По линейности ожидания:$$\mathbb{E}\left[\sum_{i=1}^m X_i\right] = \sum_{i=1}^m \mathrm{P}(X_i=1) = m \cdot 2^{1-k} < 2^{k-1} \cdot 2^{1-k} = 1.$$

Значит, $\mathrm{P}\left(\sum X_i = 0\right) > 0$ — существует раскраска без монохромных подмножеств.

Ответ: Требуемая раскраска существует.

Что главное: вероятность «плохой» конфигурации $< 1$ при оценке через линейность ожидания — вот и всё.

Задача 2. Нижняя оценка на независимое множество

Условие: Граф $G$ имеет $n$ вершин и $m$ рёбер. Докажите, что граф содержит независимое множество размера $\geq \dfrac{n^2}{2n + 4m - 2}$ (оценка Турана в вероятностной форме для разреженных графов).

Источник: классическая оценка (Турниры, Физтех, 10-11 класс)

Как думать (рассуждение ученика$):
1. $Что вижу? Нижняя оценка на независимое множество. Конструктивный подход сложен — пробую вероятностный метод.$2. *$Первый ход: включаю каждую вершину в случайное множество $S$ с вероятностью $p$ независимо. Оцениваю ожидаемый размер независимого множества после удаления «плохих» рёбер.$3. *$Ключевая схема: $\mathbb{E}[|S|] = np$. Для каждого ребра $\{u,v\}$ вероятность, что оба в $S$: $p^2$. Удаляем одну вершину от каждой «плохой» пары. Оставшееся множество независимо, его ожидаемый размер $\geq np - mp^2$. Максимизируем по $p$.

Решение:

Включаем каждую вершину в $S$ с вероятностью $p$. Из каждого ребра $\{u,v\} \subset S$ удаляем вершину (одну из двух). Обозначим $I$ — итоговое независимое множество. Тогда $\mathbb{E}[|I|] \geq np - mp^2$. Максимум по $p$: $p^* = \frac{n}{2m}$ (если $\leq 1$), откуда $\mathbb{E}[|I|] \geq \frac{n^2}{4m}$. Для общего случая аккуратная оценка даёт $\geq \frac{n^2}{2n+4m-2}$.

Ответ: Независимое множество размера $\geq \dfrac{n^2}{2n+4m-2}$ гарантированно существует.

Что главное: максимизация по параметру $p$ позволяет получить оптимальную оценку из вероятностного рассуждения.

• Ошибка: $\mathbb{E}[X] > 0$ не означает, что $X > 0$ всегда. Это означает только существование исхода с $X > 0$. Для доказательства существования этого достаточно, но не утверждайте «всегда». Как избежать: формулируйте вывод: «существует конфигурация, при которой $X > 0$».

• Ошибка: путают $\mathbb{E}[X] < 1$ и $X = 0$ с вероятностью 1. $\mathbb{E}[X] < 1$ означает $X = 0$ с положительной вероятностью, но не обязательно с вероятностью $1. *$Как избежать:* аккуратно формулируйте: «$\mathrm{P}(X=0) > 0$, значит такой объект существует».

• Ошибка: не проверяют, что случайная величина неотрицательна. Метод первого момента работает для $X \geq 0$. Как избежать: убедитесь, что $X$ — это число «плохих» объектов (всегда $\geq 0$).

• Ошибка: линейность ожидания применяется только для независимых переменных. Это неверно: линейность верна всегда. Как избежать: напомните себе: $\mathbb{E}[X+Y] = \mathbb{E}[X]+\mathbb{E}[Y]$ без каких-либо условий.

• Ошибка: не оптимизируют параметр вероятности $p$. Берут $p = 1/2$ «по умолчанию» вместо оптимального $p^*$. Как избежать: записывайте ожидание как функцию $p$, находите максимум дифференцированием или AM-GM.