Теория вероятностей
Вероятностный метод
Числа Рамсея $R(k,k)$ - наименьший $n$ такой, что любая 2-раскраска $K_n$ содержит монохроматическую $K_k$. Точные значения известны только для малых $k$: $R(3,3)=6$, $R(4,4)=18$. Эрдёш в 1947 году доказал $R(k,k) > 2^{k/2}$ - без единой конструкции, просто показав, что случайная раскраска работает с положительной вероятностью.
- Разреженные хэши в алгоритмах: вероятностный метод доказывает существование хэш-функций с малым числом коллизий - используется в Cuckoo Hashing и Bloom-фильтрах.
- Derandomization: алгоритм LLL (Lovász Local Lemma) даёт конструктивный поиск объектов, существование которых доказано вероятностным методом. Mitzenmacher-Upfal (алгоритм 2010) даёт полиномиальное время для LLL.
- Случайные графы (Erdos-Renyi $G(n,p)$): порог связности $p = \log n / n$, порог появления треугольника $p = 1/n$ - все выводятся через первый и второй моменты.
Цели урока
- Применять метод первого момента (наивный вероятностный метод) для нижних оценок комбинаторных величин
- Использовать метод второго момента для порогов фазового перехода в случайных графах
- Формулировать и применять локальную лемму Ловаса (LLL)
Предварительные знания
- Линейность математического ожидания и индикаторные переменные
- Дискретная вероятность: формула включений-исключений
- Теория графов: раскраски, клики, независимые множества
Метод первого момента: существование через среднее
Метод первого момента: $\mathbb{E}[X] > 0 \Rightarrow P(X > 0) > 0 \Rightarrow$ существует исход с $X > 0$. Применение к числам Рамсея: $P(K_n$ без монохроматической $K_k) > 0$ при $n < 2^{k/2}$. Вычисление: $\mathbb{E}[\text{число моно-клик}] = \binom{n}{k} 2^{1-\binom{k}{2}}$. При $n = 2^{k/2}$: ожидание $< 1$, но это не завершает доказательство. Вероятностный метод: хотим $\mathbb{E} < 1$, значит с ненулевой вероятностью нет ни одной - и такая раскраска существует.
Локальная лемма Ловаса (LLL): пусть $A_1, \ldots, A_m$ - события, каждое зависит не более чем от $d$ других, и $P(A_i) \leq p$ для всех $i$. Если $ep(d+1) \leq 1$ (где $e = 2.718...$), то $P(\bigcap \bar A_i) > 0$ - можно избежать всех плохих событий одновременно. Применение: существование $(k,2)$-раскраски при $n < k^2 \cdot 2^{k-3}$ (сильнее наивного метода).
Вероятностный метод доказывает существование, но не даёт конструкции. Для алгоритмических задач нужна дерандомизация. Алгоритм Мозера-Тардоса (2010) конструктивно реализует LLL за полиномиальное время: он 'разрешает' нарушения итеративно, и анализ корректности сам использует вероятностный метод.
Пол Эрдёш и Альфред Реньи основали теорию случайных графов в 1959-1960 годах, из
Пол Эрдёш и Альфред Реньи основали теорию случайных графов в 1959-1960 годах, изучая пороговые явления. Сам вероятностный метод Эрдёш применял с 1947 года. Локальную лемму Ловаша доказали Эрдёш и Ловас в 1975 году. Конструктивная версия LLL (Мозер-Тардос, 2010) стала прорывом в алгоритмической теории случайных структур.
Аргумент первого момента и числа Рамсея
Пал Эрдёш в 1947 году опубликовал заметку всего на 3 страницы, доказав нижнюю оценку $R(k,k) > 2^{k/2}$ через случайную раскраску - без единого явно построенного графа. Эта работа породила целую область вероятностной комбинаторики: лучшая известная нижняя оценка для $R(k,k)$ остаётся в пределах константного множителя от первоначального результата Эрдёша уже 78 лет.
Вероятностный метод доказывает $R(4,4) > 2^2 = 4$. Что именно следует из этого?
Метод второго момента и пороги в случайных графах
Эрдёш и Реньи в 1959 году исследовали модель $G(n,p)$ и обнаружили резкие пороговые феномены: при переходе $p$ через $1/n$ доля графов с треугольником подскакивает от 0 до 1 в окне ширины $\Theta(1/n)$. Современные сети из 4.6 миллиардов IP-узлов демонстрируют ту же картину: связность появляется на критическом $p_c$ почти ступенькой.
В $G(n,p)$ число треугольников $X$ имеет $E[X] = c$ и $\mathrm{Var}(X)/(E[X])^2 \to 0$. Какое заключение даёт метод второго момента?
Локальная лемма Ловаса
Ласло Ловас в 1975 году доказал локальную лемму, обходящую слабость границы объединения при многих, но слабо зависимых плохих событиях. В 2010 году Робин Мозер и Габор Тардош построили алгоритмическую версию: для 3-SAT с не более чем 3 вхождениями каждой переменной выполняющее присвоение находится за $O(n)$ шагов в среднем.
ЛЛЛ (симметричная): плохие события с $P(A_i) \le 0.01$, каждое зависит не более чем от $d = 4$ других. Применима ли лемма?
Метод второго момента: порог треугольника
В $G(n,p)$ пусть $X$ - число треугольников. $\mathbb{E}[X] = \binom{n}{3}p^3 \sim n^3 p^3/6$. Порог: $\mathbb{E}[X] = 1$ при $p = n^{-1}$. Второй момент: $\mathbb{E}[X^2] = \mathbb{E}[X]^2 + O(n^3 p^4 + n^4 p^5)$. По второму методу Пейли-Зигмунда: $P(X > 0) \geq (\mathbb{E}[X])^2/\mathbb{E}[X^2]$. При $p \gg n^{-1}$: $P(X>0) \to 1$. Это доказывает резкий порог: при $p = cn^{-1}$ треугольник есть или нет с вероятностями $1-e^{-c^3/6}$ и $e^{-c^3/6}$.
Итоги
- Метод первого момента: $\mathbb{E}[X] < 1$ при подходящих параметрах доказывает существование желаемого объекта.
- Метод второго момента даёт нижние оценки на вероятность.
- LLL обрабатывает зависимые события при условии слабой зависимости.
- Все три метода нашли применение в алгоритмах через дерандомизацию.
Связь с другими темами
Дискретная вероятность (dm-17) - источник идей для вероятностного метода. Концентрация меры (prob-22) усиливает вероятностный метод, давая оценки на вероятность отклонения. В криптографии вероятностный метод обосновывает существование хэш-функций с малой вероятностью коллизий.
- Dm 17 — связан
- Prob 22 — связан
Вопросы для размышления
- LLL утверждает $P(\bigcap \bar A_i) > 0$ при $ep(d+1) \leq 1$. Постройте пример с $d = 100$ плохими событиями и верификацией условия LLL. Как условие LLL деградирует к наивному union bound при $d = 0$ (независимые события)?