Лемма Ловаса и другие вероятностные доказательства существования

Общая информация
ЛекторА. Х. Шень
Семестрвесна 2015
Дата начала28.02.2015
Количество пар10
Язык курсарусский
Вопросы к экзамену
Аннотация

Бывают ситуации, когда существование объекта с какими-то свойствами доказать легко, но это доказательство неконструктивно (не даёт возможности предъявить такой объект). Например, можно установить, что число всех объектов определённого вида, не обладающих нужным свойством, меньше числа всех объектов этого вида. Это можно переформулировать в терминах вероятности, а также в терминах сложности описания (плохие объекты можно коротко описать, поэтому их мало). Мы рассмотрим простые примеры такого рода, а также более сложную вероятностную технику, называемую "леммой Ловаса", а также вероятностный алгоритм построения объектов, придуманный Мозером и модифицированный Тардошем, и его следствия (слова без запрещённых подслов и другие применения).

Задачи Вопросы по рассказанному и решения этих задач можно посылать по адресу sasha.shen@gmail.com — информацию о решённых задачах я перешлю в computer science center. (Предупреждение: несколько последних задач я решать не умею и потому особенно заинтересован в их решениях.)

  1. Докажите, что если множество $ A $ натуральных чисел неразрешимо, то вероятность события ``$ A $ сводится по Тьюрингу к случайной последовательности битов'' (т.е. существует машина с оракулом, которая разрешает $ A $, если использовать эту последовательность как оракул) равна $ 0 $.
  2. Пусть мы хотим применить критерий Миллера и других к построению последовательности в двоичном алфавите, не содержащей кубов слов длины $ n $ (это длина слова, куб имеет длину $ 3n $) и больше. При каких $ n $ это удастся сделать?
  3. Докажите, что если для каждого $ k $ алгоритмически указан список из не более чем $ 2^{0.99k} $ слов длины $ k $, то можно найти число $ N $ и вычислимую двустороннюю последовательность, в которой нет запрещённых слов длины $ N $ и более.
  4. Докажите, что если у степенного ряда для $ \frac{1}{1-2x+F_2x^2+F_3x^3+\ldots}, $ где $ F_2,F_3,\ldots $ --- количества запрещённых слов длин $ 2,3,\ldots $ (запрещённых слов меньших длин нет) все коэффициенты положительны, то существуют сколь угодно длинные слова без запрещённых подслов.
  5. (Продолжение) Можно ли как-то связать предыдущий критерий с критерием Миллера (в знаменателе как раз стоит то самое выражение!)?
  6. Попытаться вывести критерий Миллера (с тем же или более слабым условием) с помощью леммы Ловаса.
  7. Попытаться переформулировать доказательство алгоритма Мозера--Тардоша в общем (или чуть менее общем) случае в терминах сжатия случайных битов.

Ссылки

  1. http://arxiv.org/abs/1305.1535: бесконечная вычислимая лемма Ловаса (и изложение доказательства Мозера--Тардоша в общем случае), а также обсуждение задачи о фейрверках.
  2. http://www.lirmm.fr/~ashen/kolmbook.pdf: книжка по колмогоровской сложности, там есть классической доказательство леммы Ловаса (неконструкструктивное), критерия Миллера, доказательства со сжатием для случая $ n $-кнф и некоторая общая информация о вероятностных алгоритмах и выходных распределениях.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1
(28.02.2015 - 17:20 - 18:55)

Вероятностный метод: средние

Если среднее (математическое ожидание) больше $ \alpha $, то некоторые значения больше $ \alpha $

  • Если сумма десяти чисел больше $ 100 $, то сумма некоторых трёх из них больше $ 30 $
  • Вариант: если у дерева $ 1500 $ листьев, можно оборвать $ 800 $ из них так, чтобы осталось не меньше $ 7/15 $ тени. (С какой-то из московских олимпиад, кажется.)
  • Та же задача, если числа стоят по кругу и нужна сумма трёх соседних
  • Любой граф с $ E $ рёбрами можно разрезать на две части так, чтобы в разрез попало не меньше $ E/2 $ рёбер
  • В клетках шахматной доски написаны числа, сумма положительна. Докажите, что можно расставить ладьи, не бьющие друг друга, чтобы сумма была положительной
  • Для любой 3-кнф можно удовлетворить не менее $ 7/8 $ дизъюнктов
  • Поверхность тела меньше $ 4 $; докажите, что можно его повернуть так, чтобы тень была не больше $ 1 $ (на экране, перпендикулярном направлению света)
  • Фигуру площади $ n $ можно поместить на клетчатой бумаге так, чтобы она покрыла не менее $ n $ узлов, а можно так, чтоб не больше $ n $ узлов

Вероятностный метод: оценка суммы

Если сумма вероятностей событий меньше $ 1 $, то иногда ни одного из них не происходит.

  • В окружность, где не более $ 30\% $ грязные, можно вписать правильный треугольник с чистыми вершинами. (Рассуждение со средними и с вероятностью.)
  • В сферу, где не больше $ 10\% $ поверхности грязные, можно вписать куб с чистыми вершинами
  • Числа Рамсея
    • $ R(k,l) $: сколько вершин нужно в графе, чтобы гарантировать или независимое множество из $ k $, или клику из $ l $;
    • оценка $ R(3,3)=6 $;
    • верхняя оценка $ R(k,l)\le R(k-1,l)+R(k,l-1) $
    • оценка $ R(n,n)\le 2^{2n} $ (биномиальные коэффициенты)
    • нижняя оценка: случайный граф
    • оценка вероятности
    • пересказ в виде оценки количеств
    • пересказ в виде сжатия: если в графе из $ n $ вершин есть монохроматический граф размера $ k $, то можно вместо $ k(k-1)/2 $ битов обойтись $ 1+k\log n $ битами, получаем выигрыш при $ k>\log n/2 $ (примерно)
  • Обход лабиринта на шахматной доске: существует последовательность команд (влево, вправо, вверх, вниз), при исполнении которой (невыполнимые команды пропускаются) мы обойдём доступную часть любого лабиринта на доске $ 8\times 8 $ (при любом начальном положении).
    • есть такое $ N $, что вероятность обхода за $ N $ случайных шагов положительна (для всех досок) --- не меньше $ \varepsilon $;
    • вероятность не обойти (данный лабиринт с данным началом) за $ N $ шагов не больше $ (1-\varepsilon) $;
    • вероятность не обойти (данный лабиринт с данным началом) за $ kN $ шагов не больше $ (1-\varepsilon)^k $;
    • при большом $ k $ произведение $ (1-\varepsilon)^k $ на число лабиринтов будет меньше $ 1 $.
  • Монотонная схема полиномиального размера и логарифмической глубины для функции majority:
    • Постановка задачи: схемы, глубина, размер, монотонные схемы, универсальность, монотонная универсальность.
    • Достаточно логарифмической глубины
    • Схема: дерево с элементами $ \mathrm{MAJ}_3 $ логарифмической глубины и случайными переменными на листьях
    • Оценка вероятности: функция $ p\mapsto 3p^2-2p^3 $ и её итерации. $ O(\log n) $ шагов, чтобы отойти от середины; $ O(1) $ шагов чтобы дойти до края; $ O(\log n) $ чтобы сойтись к краю на расстояние $ 2^{-n} $
https://www.youtube.com/watch?v=lfqx2cROIDA
2. Лекция 2
(28.02.2015 - 19:15 - 20:50)

https://www.youtube.com/watch?v=03GXsxk76TQ
3. Лекция 3
(01.03.2015 - 11:15 - 12:50)

Вероятностные оценки: метод сжатия

  • Один пример такого рода (для чисел Рамсея) уже был
  • Другой пример: закон больших чисел для вероятности $ 1/2 $
    • Среднее $ 1/2 $
    • Среднее квадратичное отклонение и оценки с неравенством Чебышёва
    • Экспоненциальная оценка методом сжатия: арифметическое кодирование требует $ nH(p) $ битов
    • Для информации: неравенство Чернова и Азумы--Хёфдинга
  • Сильно непериодическое слово: расположить по кругу $ n $ битов так, чтобы любой поворот менял как минимум $ 10\% $ битов (при достаточно большом $ n $)
  • Тот же вопрос для $ 49\% $ изменённых битов (усреднение!)

Ещё о вероятностных доказательствах

  • Задача о коробке: если одна прямоугольная коробка помещается в другую, то сумма измерений первой не больше, чем у второй. (Можно ли перехитрить метро?). Решение: сумма измерений пропорциональная средней ширине коробки в случайном направлении
  • Задача о несравнимых множествах: антицепь в семействе подмножеств $ 2n $-элементного множества (порядок по включению) содержит не более $ \binom{2n}{n} $ элементов. Доказательство: рассмотрим случайный процесс добавления элементов (в случайном порядке), события <<пройти через данный элемент антицепи>> несравнимы, значит, суммы их вероятностей не больше $ 1 $, а они минимально возможные, когда размер ровно половинный
  • Игры с полной информацией: существование выигрышной стратегии у одного из игроков. Следствие: если есть вероятностная стратегия для одного из игроков, гарантирующая положительную вероятность выигрыша (против любой детерминированной стратегии второго), то есть и детерминированная стратегия. Пример: игра против начальника: подчинённые разных рангов ($ 0,1,2,\ldots $) делятся на две группы, начальник увольняет по своему выбору одну, но уменьшает ранги всех членов второй на $ 1 $; задача подчинённых --- чтобы кто-то достиг ранга $ 0 $. Вероятностная стратегия начальника: выбирать случайную группу. Вероятность выжить для ранга $ k $ равна $ 2^{-k} $, если сумма меньше $ 1 $, то есть вероятность извести всех (а значит, есть и детерминированная стратегия извести всех)
  • Бесконечные пространства и события меры $ 0 $: построение иммунного множества с иммунным дополнением, построение двух несравнимых степеней по Тьюрингу

Дерандомизация

  • Игра против начальника: выбираем ту группу, где сумма $ 2^{-k} $ меньше, она будет меньше $ 1/2 $, после повышения рангов в сумме будет меньше $ 1 $, то есть ранг $ 0 $ недостижим
  • Разрез не менее чем половины рёбер: поддерживаем условное математическое ожидание не меньше $ E/2 $: получаем жадный алгоритм (более половины новых рёбер разноцветные)
  • Отыскание выполняющего набора для 3-кнф, где не меньше $ 7/8 $ условий выполнены
https://www.youtube.com/watch?v=ZBk_ow6QUkI
4. Лекция 4
(01.03.2015 - 13:00 - 14:35)

https://www.youtube.com/watch?v=mFyyZ6UkRjA
5. Лекция 5
(01.03.2015 - 15:35 - 17:10)

https://www.youtube.com/watch?v=RskSP-iOmfI
6. Лекция 6
(07.03.2015 - 17:20 - 18:55)

Лемма Ловаса: формулировка

  • Мотивировочный пример: последовательность символов, на каждой границе $ 1\% $ пар комбинаций запрещён, доказать существование последовательности
  • Решение: индукцией строим начало, которое блокирует не более $ 10\% $ вариантов следующей буквы. (Фубини: блокирующих более $ 10\% $ не более $ 10\% $, если произведение меньше $ 1\% $.)
  • Формулировка леммы Ловаса: события $ A_1,\ldots,A_n $, граф соседства (не обязательно симметричный; $ N(i) $ --- соседи $ i $), независимость со всеми не-соседями сразу, для некоторых положительных чисел $ \varepsilon_i<1 $ выполнено
    $$\Pr[A_i]\le \varepsilon_i \prod_{j\ne i, j\in N(i)} (1-\varepsilon_j).$$
    Тогда
    $$\Pr[\lnot A_1 \land \ldots\land \lnot A_n]\ge \prod_i (1-\varepsilon_i)>0.$$
  • Частный случай независимых событий, сравнение с union bound
  • Применение к задаче о запрещённых парах соседей в последовательности: $ \Pr[A_i]<\varepsilon(1-\varepsilon)^2 $. Наилучшая оценка: $ \varepsilon=1/3 $, получается $ 4/27 $

Доказательство леммы Ловаса

  • По индукции надо доказывать два семейства неравенств:
    $$ \Pr[A_i | \lnot A_j \land \lnot A_k \land...]\le \varepsilon_i.$$
    $$\Pr[\lnot A_i \land \lnot A_j\land\ldots| \lnot A_p\land \lnot A_q\lnot\ldots]\ge (1-\varepsilon_i)(1-\varepsilon_j)\ldots$$
  • первое --- частный случай второго (одно событие слева от черты);
  • второе следует из первого по индукции (произведение нескольких условных вероятностей);
  • первое можно вывести из второго \emph{для меньшего числа переменных}: разделим в условии на соседей $ N $ и несоседей $ O $, получим
    $$\Pr[A_i|N\land O]=\frac{\Pr[A_i\land N\land O]}{\Pr[N\land O]}\le \frac{\Pr[A_i\land O]}{\Pr[N|O]\Pr[O]}.$$
    Остаётся воспользоваться независимостью в числителе, оценкой $ \Pr[N|O]\ge \prod_{j\in N(i)}(1-\varepsilon_j) $ и условием для $ \Pr[A_i] $
  • важно, что нет порочного круга: мы сводим в этом месте к утверждению для меньшего числа событий (без $ A_i $)
https://www.youtube.com/watch?v=_7gZ9VfR5fA
7. Лекция 7
(07.03.2015 - 19:15 - 20:50)

https://www.youtube.com/watch?v=Z6zh7W0DPL4
8. Лекция 8
(08.03.2015 - 11:15 - 12:50)

Применения леммы Ловаса

  • Гарантированная выполнимость кнф
    • Достаточно: каждое условие на $ n $ переменных и имеет не более $ N=2^n/4 $ соседей (с общими переменными). Видно, что $ 2^n/4 $ нельзя заменить на $ 2^n $
    • подбор $ \varepsilon $: надо $ 2^{-n}<\varepsilon (1-\varepsilon)^{N} $, максимум достигается, когда $ \varepsilon=1/(N+1) $, то есть $ N\approx 2^n/e $
  • Возможность заполнения двумерной таблицы, если на каждом ребре запрещён $ 1\% $ пар. (Уже непонятно, как без леммы Ловаса)
  • Отступление: переход от заполнения сколь угодно большой таблицы к заполнению бесконечной (компактность, лемма Кёнига, теорема Гёделя о полноте)
  • Почему это рассуждение не эффективизируется: пример бесконечного разрешимого поддерева полного двоичного дерева без вычислимой бесконечной ветви
  • Двоичные слова без (достаточно длинных квадратов). Обобщение: задача о запрещённых подсловах, если запрещено $ F_k $ слов длины $ k $, при этом $ F_k<2^{\alpha k} $ при $ \alpha<1 $, то есть бесконечная последовательность без длинных запрещённых подслов
  • Суперслучайная и потому неслучайная последовательность с несжимаемыми подсловами
  • Проверка выполнения леммы: $ \varepsilon_k=2^{-\beta k} $ для слов длины $ k $ (выбор константы: $ \alpha<\beta<1 $)

Ещё о запрещённых подсловах

  • Метод потенциала по Миллеру
    • Идея: насколько мы близки к краю
    • Число запрещённых вхождений в уже построенный участок, но учитываем также и возможные вхождения, пересекающие уже построенный участок (в виде математического ожидания: если не хватает $ s $ букв, то с весом $ 2^{-s} $. Обозначаем $ D(x) $ и получаем формулу:
      $$D(x)+\sum_k F_k /2^k=\tfrac{1}{2}D(x0)+\tfrac{1}{2}D(x1)$$
      (левая часть учитывает ещё и матожидание сразу справа от конца $ x $)
    • чисто формально можно подсчитывать вхождения, пересекающиеся с $ x $, но выходящие за пределы $ x $ на $ k $ букв, с весом $ c^{-k} $. Если слово $ x $ не содержит запрещённых вхождений, то верно аналогичное равенство:
      $$D(x)+\sum_k F_k c^k=c D(x0)+ c D(x1)$$
      Мы хотим поддерживать $ D(x)<1 $, увеличивая $ x $ (заметим, что в этом случае нет вхождений в $ x $, так что можно применить равенство --- это сработает, если
      $$1+\sum\k F_k c^k < 2c,$$
      то есть если
      $$\sum_k F_k c^k < 2c-1$$
      при некотором положительном $ c $ (больше $ 1/2 $, иначе правая часть отрицательна)
    • Даёт вычислимую ветвь, если множество $ F_k $ разрешимо и ряд вычислимо сходится. (чего можно добиться, немного уменьшив $ c $ без нарушения условия)
  • Рассуждение со сжатием (вариант алгоритма Мозера для данного конкретного случая).
    • Процесс: добавляем случайные биты, когда появляется запрещённое слово, оно пропадает (<<тетрис>>-алгоритм, только игрок лишь наблюдает); удаляется только одно слово (второе удалилось бы раньше)
    • Протокол: на каждом шаге записываем, что произошло. Два варианта: либо просто добавление бита (и тогда мы не записываем, какой бит добавили), либо добавление бита со схлопыванием слова (и тогда записываем, какое слово)
    • Надо доказать,что длина текущего слова не может оставаться ограниченной (точнее, что вероятность этого мала)
    • Наблюдение: по протоколу и тому, какие биты остались на данный момент, можно восстановить все использованные случайные биты (обратный ход)
    • Если мы научимся кодировать протокол экономно (меньше одного бита на операцию), то видно, что биты будут накапливаться (иначе оставалось бы ограниченное количество битов, а протокол кодируется короче, чем случайная последовательность)
    • Для протокола используется арифметическое кодирование: добавление без схлопывание имеет вес $ p_0 $, добавление со схлопыванием слова длины $ k $ имеет вес $ p_k/F_k $ (все слова поровну и $ p_k $ на всех)
    • Мы выбираем $ p_0>1/2 $, тогда на добавление уходит меньше $ 1 $ бита, и можно оставлять (для амортизационного анализа) запас $ z>0 $, который затем можно расходовать на кодирование схлопывания (без этого там не обойтись: схлопываться могут самые разные слова)
    • Необходимые неравенства:
      $$\log (1/p_0)\le 1-z;$$
      $$\log(1/p_k)+\log F_k \le 1+z(k-1);$$
      $$\sum_k p_k<1$$
      (строгое неравенство в последнем случае создаёт необходимый запас)
    • можно считать, что в первых двух случаях равенства, и получится как раз условие Миллера

Выполнимость $ n $-кнф с $ 2^{n-3} $ соседей у каждого клоза

  • алгоритм: поочерёдное исправление всех клозов, если они не выполнены;
  • исправление одного клоза (известно, что он не выполнен): перерандомизация плюс рекурсивный вызов для всех соседей (если к моменту вызова клоз выполнен, он пропускается);
  • достаточно доказать, что исправление кончается за полиномиальное время (с вероятностью почти $ 1 $);
  • случайные биты в процессе исправления одного клоза можно восстановить по последовательности вызовов и по текущим битам (обратный ход);
  • последовательность вызовов --- обход дерева рекурсии, каждый шаг записываем битами: вверх или вниз, если вверх, то по какой ветви ($ n-3 $ битов), ещё один бит надо запасти для амортизационного анализа на выполнение шага вниз, получается $ n-1 $ на вызов вместо $ n $, так что долго так быть не может

Общий алгоритм Мозера--Тардоша и его оценка

  • Собственно алгоритм: выбор нарушенного условия по какому-то правилу и его перерандомизация
  • Утверждение: если выполнено условие леммы Ловаса, то математическое ожидание количества исправлений $ i $-го условия не больше $ \varepsilon_i/(1-\varepsilon_i) $
  • Деревья зависимостей и их свойства
  • Оценка вероятности появления данного дерева (запасённые переменные)
  • Сравнение с вероятностью в процессе Гальтона--Уотсона и окончание доказательства

Вероятностные алгоритмы для бесконечных задач

  • Массовые проблемы, сводимость
  • Вероятностно разрешимые массовые проблемы (в сильном и слабом смысле)
  • Получение невычислимой последовательности (разрешимая проблема)
  • Получение конкретной невычислимой последовательности: теорема Мура--де Леу--Шеннона--Шапиро: доказательство с теоремой Лебега о плотности
  • Выходные меры вероятностных алгоритмов: описание. Доказательство с полумерой
  • Отступление: максимальная полумера, неслучайные последовательности и почему они имеют меру нуль
  • Задача о фейерверках
  • Слабая разрешимость о построении последовательности натуральных чисел, не мажорируемой никакой тотальной вычислимой функцией

Машины с переписыванием ответа

  • Определение, эквивалентность покоординатному
  • Для одного бита: вычислимые точки в пространстве измеримых множеств
  • Если такая машина даёт элемент замкнутого множества с положительной вероятностью, то это замкнутое множество имеет вычислимую точку
  • Бесконечный вариант задачи о запрещённых словах и прямоугольниках
https://www.youtube.com/watch?v=oaT9cGaexm4
9. Лекция 9
(08.03.2015 - 13:00 - 14:35)

https://www.youtube.com/watch?v=7AlRlkA7YzM
10. Лекция 10
(08.03.2015 - 15:35 - 17:10)

https://www.youtube.com/watch?v=ZG4XmA3_9k0
Ваша оценка: Пусто Средняя: 5 (2 голосов)
Share |
Александр Шень
Александр Шень
Александр Шень и студенты
Перерыв
Александр Шень
Александр Шень