Предсказание последовательности с помощью экспертов

Представьте себе конечную последовательность нулей и единиц, которая появляется бит за битом. Перед появлением очередного бита мы хотим его предсказать. Для этого у нас есть экспертов: каждый из них перед появлением бита говорит, чему по его мнению он будет равен. Пусть — число ошибок -го эксперта. Если бы мы заранее знали, какой эксперт самый хороший, то мы бы могли обойтись ошибками. Однако, даже без такого априорного знания мы можем обойтись

ошибками, где — сколько угодно маленькая положительная константа.

Алгоритм очень простой. Давайте приписывать экспертам веса . Изначально положим все единицам. Биты предсказывать будем так: посчитаем сумму весов экспертов, которые проголосовали за ноль, и сумму тех, кто проголосовал за единицу. Назовем значение, суммарный вес которого больше. После того, как мы узнали настоящее значение бита, умножим веса всех экспертов, которые ошиблись, на .

Докажем, что количество ошибок при такой стратегии ограничено (1). Будем следить за потенциалом . Изначально . Докажем, что при каждой нашей ошибке домножается не более, чем на . Действительно, при нашей ошибке суммарный вес экспертов, которые ошиблись, составляет по крайней мере . Значит, после обновления весов экспертов новое значение не превзойдет

Таким образом, если мы сделали ошибок, то . Но так как в каждый момент , то имеем

для любого . Отсюда после несложных преобразований получаем (1).

Частный случай теоремы Дворецкого

Мы докажем частный случай теоремы Дворецкого для пространств .

Theorem 1 Для любого в найдется подпространство размерности , где -норма ведет себя практически как : существует такая константа , что для любого имеют место неравенства .

Proof: Это утверждение можно переформулировать так: рассмотрим куб . Тогда у него найдется центральное сечение размерности такое, что , где — единичный евклидов шар, а — некоторая константа. То есть у куба есть центральные почти сферические сечения логарифмической размерности!

Для начала заметим, что шар в этом рассуждении можно заменить на эллипсоид. Действительно, если у нас есть эллипс размерности с центром в нуле, то у него есть центральное сферическое сечение размерности . Понять это можно так. Пусть наш эллипсоид имеет вид

где . Тогда наше искомое подпространство размерности будет задаваться линейным уравнением, -е из которых выглядит так:

Уравнения подобраны так, что если точка удовлетворяет им, то она лежит в нашем эллипсоиде тогда и только тогда, когда ее -норма не превосходит .

Таким образом, если мы построим центральное сечение куба размерности , которое является почти эллипсоидом, то из предыдущего рассуждения следует, что существует сечение размерности , которая является почти сферическим. Итак, нам достаточно построить центральное сечение размерности такое, что

где — линейное отображение .

Мы будем рассматривать тела вида , где .

Во-первых, такие тела можно линейно отобразить в центральные сечения : действительно, рассмотрим отображение

Во-вторых, такие тела содержат . В-третьих, ясно, что тело такого вида лежит в тогда и только тогда, когда для каждого найдется такое, что . Задача свелась к такой: покрыть как можно меньшим количеством шапочек (множеств вида ). Для этого достаточно построить -сеть на . Рассуждениями аналогичными доказательству теоремы Варшамова-Гилберта можно показать, что существует сеть размера .

Элементарное доказательство неравенства Крафта-Макмиллана

Когда-то я писал доказательство неравенства Крафта-Макмиллана, которое использует производящие функции и комплексный анализ. В этом посте написано то же самое доказательство, но на элементарном языке.

Theorem 1 Если — длины слов однозначного кода, то

Proof: Для удобства будем считать, что слова у нас не в алфавите , а в алфавите . Выберем некоторое натуральное число и запишем формальную сумму:

где — наши слова. Например, если код состоит из слов , то сумма будет выглядеть так:

Теперь сделаем еще более странное действие — раскроем скобки (считая, что умножение слов — это конкатенация). Например,

Заметим, что слова в правой части не повторяются, так как наш код однозначный.

Теперь будем подставлять в это выражение . Слева получится , а справа — не более, чем , так как для любого справа не более, чем слов длины (так как все слова различны).

Предположим теперь, что . Тогда левая часть растет экспоненциально при росте , а правая — линейно. Противоречие.

Неравенство Чернова

Рассмотрим случайное блуждание. Частица в начальный момент времени находится в точке ноль, а в каждый следующий момент с вероятностью сдвигается либо на единицу вправо, либо на единицу влево. При этом, эти сдвиги независимы. Мы хотим доказать, что после шагов частица будет с высокой вероятностью на расстоянии порядка от начала.

Обозначим случайные величины соответствующие сдвигам , а — положение частицы после шагов. Мы хотим доказать, что достаточно сильно сконцентрирована вокруг своего математического ожидания (которое, как несложно заметить, равно нулю). Центральная предельная теорема говорит нам, что

где сходимость понимается как сходимость по распределению при . То есть в пределе отклоняется от нуля не более, чем на , с вероятностью порядка . К сожалению, центральная предельная теорема ничего не говорит о скорости сходимости, а в приложениях часто полезно иметь аналогичные утверждения для конечного . Есть варианты центральной предельной теоремы (например, теорема Берри-Эссеена), которые дают какую-то оценку на скорость сходимости при некоторых дополнительных условиях (конечность третьего момента). Но для доказать сильную концентрацию вокруг нуля проще непосредственно.

Самый простой способ доказать, что случайная величина сильно сконцентрирована вокруг математического ожидания — это неравенство Чебышева. Напомним его (для случая ).

Theorem 1

Proof: Действительно,

Можно пойти дальше и воспользоваться четвертым моментом .

Theorem 2

Proof: Действительно,

Дальше можно воспользоваться шестым моментом и получить оценку и т. д. Но центральная предельная теорема в пределе дает нам оценку порядка , которую никакой константный момент обеспечить не в состоянии. Поэтому нам нужен какой-то новый трюк.

Рассмотрим преобразование Лапласа . Оказывается, что используя его, можно получить хорошую оценку на концентрацию .

Theorem 3

Proof: Введем параметр , который мы зафиксируем позднее. Тогда

Вычислим . Вспомним, что , где — независимые сдвиги. Отсюда получаем

Для дальнейшей оценки нам понадобится техническая лемма.

Lemma 4

Proof:

Продолжим доказательство теоремы.

Видно, что правая часть минимальна, если выбрать . Итого, получаем

Теорема~3 называется неравенством Чернова. Поймем, почему удобнее пользоваться преобразованием Лапласа, чем моментами.

Во-первых, преобразование Лапласа для проще вычислять. Действительно, пользуясь теоремой о математическом ожидании произведения независимых величин, мы сразу сводим подсчет к подсчету преобразования Лапласа . Во-вторых, так как

то мы используем сразу все моменты при оценке.

С другой стороны, моменты применимы в некоторых ситуациях, когда преобразование Лапласа не применимо. Например, пусть известно, что — попарно независимы, а не независимы в совокупности (это гораздо более слабое условие, например, для того, чтобы сгенерировать попарно независимых битов, достаточно всего истинно независимых битов). Тогда оценка по-прежнему имеет место, так как все, что мы используем, — это равенство . Аналогично, если — 4-независимые, то имеет место оценка и т. д.

Количество пересечений при укладках графов на плоскость

Пусть — простой ненаправленный граф. Будем интересоваться его укладками на плоскости, а точнее, минимально возможным количеством пересечений при укладке. Обозначим эту величину . Например, для планарных графов . Обозначим , .

Теорема. .

Сначала докажем более слабую оценку, а потом воспользуемся ей для доказательства более сильной.

Докажем сначала, что . Это совсем просто — в планарных графах количество ребер не больше , а любой граф можно превратить в планарный, удалив ребер.

Теперь докажем оценку из условия теоремы. Будем делать это вероятностным методом. Рассмотрим какую-то укладку с пересечениями. Рассмотрим подграф индуцированный случайным подмножеством . Каждая вершина входит в это множество независимо с вероятностью , которую мы выберем позднее. Тогда в среднем останется вершин, ребер и пересечений. Пользуясь слабой оценкой, получаем, что . Теперь будем оптимизировать . Если , то оценка очевидна, а если , то доставляет оптимум.

Контрольный вопрос: где мы пользовались тем, что граф простой?

Сечения куба и проблема Басманна-Петти

Представьте себе, что у нас есть два выпуклых центрально-симметричных относительно нуля компакта . Кроме того, для любой гиперплоскости , которая проходит через ноль, мера не превосходит меры . Верно ли, что мера не превосходит меры ?

Оказывается, что ответ на этот вопрос принципиально зависит от : для ответ утвердительный, для — отрицательный.
Мы покажем, что ответ отрицательный при больших .

Рассмотрим шар и куб единичного объема. Путем несложных подсчетов легко убедиться, что мера любого сечения шара равна . Оказывается, что мера всех сечений куба не превосходит . Если мы это докажем, то дело сделано, так как можно слегка уменьшить шар и получить отрицательный ответ на изначальный вопрос.

Итак, осталось доказать, что все сечения куба не превосходят . На удивление, это весьма нетривиальный результат, который был получен лишь в 1989 году Боллом (см. [1]).

Итак, пусть задан единичный вектор , и мы хотим посчитать меру сечения куба гиперплоскостью , то есть интеграл

.

С виду совершенно непонятно, как считать такой интеграл, но, оказывается, что в данном случае нам поможет преобразование Фурье. Слегка обобщим нашу задачу: будем рассматривать не только центральные сечения, но и сечения аффинными плоскостями вида . Обозначим

.

Вычислим преобразование Фурье :

.

Теперь воспользуемся обратным преобразованием Фурье и вычислим , то есть меру искомого сечения.

Таким образом, осталось доказать, что для любого единичного имеет место неравенство . Рассмотрим два случая.

Пусть существует такое, что (не умаляя общности, будем считать, что ). Тогда мера проекции сечения на гиперплоскость с одной стороны равна мере исходного сечения умножить на , а, с другой стороны, очевидно, что не превосходит единицы. Отсюда все получается.

Пусть теперь для всех выполнено . Тогда воспользуемся неравенством Гельдера:

, где .

Нетривиальный факт состоит в том, что
, если . Это неравенство называется интегральным неравенством Болла и доказывается довольно тяжелыми вычислениями (самое простое доказательство см. в [2]). Но видно, что если его доказать, то все получается.

Частичные порядки и геометрия

Представьте себе, что у нас есть частичный порядок на . Будем интересоваться множеством полных порядков, которые согласованы с (обозначим это множество ). Например, если , , то в содержатся два элемента — и .

С можно связать политоп , который устроен так: . Важное свойство состоит в том, что его объем равен . Это можно понять, к примеру, так. Рассмотрим полный порядок . Ему соответствует симплекс . Очевидны следующие утверждения:

1. ,
2. объем равен ,
3. объединение всех в точности равно .

Пользуясь формулой для объема можно получить следующие забавные факты.

Во-первых, задача подсчета трудная: более формально, -трудная (см. [1]). Но, оказывается, для этой задачи есть FPRAS (то есть алгоритм, который по , и выдает число между и с вероятностью и работает за время ). Действительно, достаточно построить FPRAS для подсчета объема , а для этого можно воспользоваться FPRAS для оценки объема выпуклого компакта (см. [2]).

Во-вторых, можно рассмотреть такую задачу. Пусть на есть какой-то полный порядок , который мы не знаем, но хотим узнать. Все, что мы знаем — это некоторый частичный порядок , который согласован с . Пусть есть оракул, у которого можно спрашивать результаты сравнений элементов. Мы хотим за минимальное число вопросов восстановить . Очевидно, что необходимо вопросов, так как всего возможно вариантов для . Забавный факт состоит в том, что вопросов достаточно. Это можно понять так. Сравнения элементам соответствуют разрезам специального вида. Таким образом, достаточно доказать, что один из этих разрезов разбивает на части примерно одинакового объема. Это несложно делается с помощью неравенства Брунна-Минковского (см. [3]).

Минимальная несбалансированность

Представьте себе двудольный граф, в каждой доле которого ровно вершин. Напишем на вершинах левой доли плюс-минус единицы. Теперь для каждой вершины правой доли посчитаем модуль суммы чисел соседей. Среди этих модулей выберем максимальный. Будем интересоваться разметкой плюс-минус единицами, которая минимизирует этот максимум.

С помощью вероятностного метода легко доказать, что существует разметка такая, что максимум модуля равен . С помощью опять же вероятностного метода легко показать, что найдется граф такой, что этот максимум при любой разметке равен . Таким образом, остается небольшой зазор между нижней и верхней оценками.

Оказывается, что точный ответ — . Это знаменитая теорема Спенсера (1985 год). Хорошо написанное доказательство (которое использует забавные теоретико-информационные соображения) есть в Алоне-Спенсере. Доказательство неконструктивное, то есть оно не дает полиномиального (вероятностного) алгоритма для построения такой разметки.

Недавно Bansal (FOCS ’10) восполнил этот пробел — в статье «Constructive Algorithms for Discrepancy Minimization» приведен полиномиальный алгоритм для поиска таких разметок. К сожалению, на первый взгляд он довольно сложен.

Теоретико-информационное доказательство изопериметрического неравенства на булевом кубе

Ранее мы доказывали изопериметрическое неравенство на булевом кубе с помощью преобразования Фурье. Сейчас мы докажем его, используя теоретико-информационные соображения (а именно, понятие энтропии дискретного распределения).

Итак, пусть . Мы хотим оценить количество ребер куба, ровно один конец которых лежит в (обозначим это количество ). Мы докажем, что .

Возьмем случайный элемент . Обозначим полученную случайную величину .

Во-первых, очевидно, что .

Во-вторых, несложно понять, что .

Теперь делаем финальную выкладку:

Отсюда получаем искомое неравенство.

Норма оператора шума

Для доказательства теоремы Канна-Калаи-Линиала нам понадобится важный технический результат о норме оператора шума.

Пусть — функция на булевом кубе (не обязательно булева). На пространстве таких функций можно ввести -норму: . Можно доказать, что -норма неубывает при увеличении .

Теперь определим оператор шума : , где запись обозначает следующее: получен из независимой заменой каждой компоненты на противоположную с вероятностью .

Можно интересоваться нормой как оператора из в . Если, например, , то понятно, что является сжимающим, то есть . Однако, нам бы хотелось усилить это неравенство, увеличивая норму в левой части. Нам понадобится такая теорема:

Теорема. .

Для доказательства теоремы нам понадобятся две леммы.

Лемма. .

Отсюда видим, что . Пользуясь равенством Парсеваля, видим, что нам нужно доказать такое неравенство: .

Теперь сформулируем и докажем вторую лемму.

Лемма. Пусть — полилинейный многочлен степени не больше . Тогда .

Доказательство. Требуемое утверждение можно переписать как . Теперь будем доказывать утверждение индукцией по и . Если , то утверждение очевидно.

Разложим по : , где — многочлены от . Степень не превосходит , а — . Теперь распишем :

Первое и третье слагаемые оцениваем по индукции: , .

Второе слагаемое оцениваем, пользуясь неравенством Коши-Буняковского:

Итого, получаем:

.

Следствие. Если — полилинейный многочлен степени не больше , то .
Доказательство. Воспользуемся неравенством Гельдера:
.

Доказательство теоремы. Напомним, что нам нужно доказать, что . Используя следствие из леммы, это сделать совсем несложно. Пользуясь следствием, видим, что . Делим это равенство на , а потом складываем по всем .
. Суммируя ряд справа, замечаем, что мы получили ровно то, что нам нужно.