Archive for Январь 2011

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

Январь 27, 2011

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

Пусть f \colon \{-1, 1\}^n \to \mathbb{R} — функция на булевом кубе (не обязательно булева). На пространстве таких функций можно ввести L^p-норму: \|f\|_p := \mathrm{E}[|f|^p]^{1/p}. Можно доказать, что L^p-норма неубывает при увеличении p.

Теперь определим оператор шума T_{\rho}: T_{\rho}f(x) = \mathrm{E}_{y \sim_{\rho} x} f(y), где запись y \sim_{\rho} x обозначает следующее: y получен из x независимой заменой каждой компоненты на противоположную с вероятностью (1 - \rho) / 2.

Можно интересоваться нормой T_{\rho} как оператора из L^p в L^q. Если, например, p = q, то понятно, что T_{\rho} является сжимающим, то есть \|T_{\rho}f\|_p \leq \|f\|_p. Однако, нам бы хотелось усилить это неравенство, увеличивая норму в левой части. Нам понадобится такая теорема:

Теорема. \|T_{1/2} f\|_2 \leq 2 \|f\|_{4/3}.

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

Лемма. T_{\rho}(\chi_{\alpha}) = \rho^{|\alpha|} \chi_{\alpha}.

Отсюда видим, что T_{\rho} f = \sum_{\alpha} \rho^{|\alpha|} \hat{f}_{\alpha} \chi_{\alpha}. Пользуясь равенством Парсеваля, видим, что нам нужно доказать такое неравенство: \sum_{\alpha} \hat{f}_{\alpha}^2 / 4^{|\alpha|} \leq 4 \|f\|_{4/3}^2.

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

Лемма. Пусть f — полилинейный многочлен степени не больше d. Тогда \|f\|_4 \leq 3^{d/2} \cdot \|f\|_2.

Доказательство. Требуемое утверждение можно переписать как \mathrm{E}[f^4] \leq 9^d \cdot \mathrm{E}[f^2]^2. Теперь будем доказывать утверждение индукцией по n и d. Если d = 0, то утверждение очевидно.

Разложим f по x_1: f = x_1 p + q, где p, q — многочлены от x_2, \ldots, x_n. Степень p не превосходит d - 1, а qd. Теперь распишем \mathrm{E}[f^4]:
\mathrm{E}[f^4] = \mathrm{E}[p^4] + 6 \cdot \mathrm{E}[p^2 q^2] + \mathrm{E}[q^4]

Первое и третье слагаемые оцениваем по индукции: \mathrm{E}[p^4] \leq 9^{d-1} \cdot \mathrm{E}[p^2]^2, \mathrm{E}[q^4] \leq 9^{d} \cdot \mathrm{E}[q^2]^2.

Второе слагаемое оцениваем, пользуясь неравенством Коши-Буняковского:
\mathrm{E}[p^2 q^2] \leq \sqrt{\mathrm{E}[p^4] \cdot \mathrm{E}[q^4]} \leq 3^{2d - 1} \cdot \mathrm{E}[p^2] \cdot \mathrm{E}[q^2]

Итого, получаем:
\mathrm{E}[f^4] \leq 9^d \cdot (\mathrm{E}[p^2]^2 + \mathrm{E}[q^2]^2 + 2 \cdot \mathrm{E}[p^2] \cdot \mathrm{E}[q^2]) =
= 9^d \cdot (\mathrm{E}[p^2] + \mathrm{E}[q^2])^2 = 9^d \cdot \mathrm{E}[f^2]^2.

Следствие. Если f — полилинейный многочлен степени не больше d, то \|f\|_2 \leq 3^{d/2} \|f\|_{4/3}.
Доказательство. Воспользуемся неравенством Гельдера:
\|f\|_2^2 = \mathrm{E}[f \cdot f] \leq \|f\|_4 \cdot \|f\|_{4/3} \leq 3^{d/2} \cdot \|f\|_2 \cdot \|f\|_{4/3}.

Доказательство теоремы. Напомним, что нам нужно доказать, что \sum_{\alpha} \hat{f}_{\alpha}^2 / 4^{|\alpha|} \leq 4 \|f\|_{4/3}^2. Используя следствие из леммы, это сделать совсем несложно. Пользуясь следствием, видим, что \sum_{|\alpha| = d} \hat{f}_{\alpha}^2 \leq 3^d \|f\|_{4/3}^2. Делим это равенство на 4^d, а потом складываем по всем d.
\sum_{\alpha} \hat{f}_{\alpha}^2 / 4^{|\alpha|} \leq \|f\|_{4/3}^2 \cdot \sum_{d = 0}^{\infty} (3/4)^d. Суммируя ряд справа, замечаем, что мы получили ровно то, что нам нужно.

Реклама

Теорема Канна-Калаи-Линиала

Январь 27, 2011

Пусть f \colon \{-1, 1\}^n \to \{-1, 1\} — сбалансированная булева функция (то есть |f^{-1}(-1)| = |f^{-1}(1)| = 2^{n-1}). Влиянием i-й переменной \mathrm{inf}_i(f) назовем вероятность того, что при случайном выборе x f поменяет значение, если переключить значение x_i. Несложно видеть, что \sum_i \mathrm{inf}_i(f) = \mathrm{as}(f), где \mathrm{as}(f) обозначает среднюю чувствительность f (что это такое, можно посмотреть здесь).

Так как мы знаем, что \mathrm{as}(f) \geq 1, то найдется переменная с \mathrm{inf}_i(f) \geq 1 / n.

Знаменитая теорема Канна-Калаи-Линиала утверждает, что найдется переменная с большим влиянием — \Omega(\log n / n). Это исторически первый пример применения анализа Фурье к изучению булевых функций. Доказательство теоремы достаточно сложное, поэтому ему будет посвящена целая серия постов.

Из этой теоремы, в частности, несложно следует, что найдется маленькая коалиция переменных (размера O(n / \log n)), которая с вероятностью близкой к единице сможет повлиять на значение f.

Идея доказательства леммы Джонсона-Линденштраусса

Январь 11, 2011

Хотелось бы объяснить идею доказательства леммы Джонсона-Линденштраусса о понижении размерности.

Основная лемма, которую нужно доказывать такая: пусть у нас есть единичная сфера в \mathbb{R}^N. Мы выбираем на ней случайную точку, а потом оставляем от нее лишь первые K координат. Мы хотим доказать, что квадрат длины полученого вектора сильно сконцентрирован вокруг математического ожидания.

Хорошо известно, что равномерное распределение на сфере проще всего моделировать как \frac{1}{\sqrt{X_1^2 + X_2^2 + \ldots + X_N^2}} \cdot (X_1, X_2, \ldots, X_N), где X_i \sim N(0, 1) и независимы. Таким образом, нам нужно доказать, что величина \frac{X_1^2 + X_2^2 + \ldots + X_K^2}{X_1^2 + X_2^2 + \ldots + X_N^2} сильно сконцентрирована вокруг математического ожидания (которое, как несложно видеть, равно K / N).

Это делается стандартными методами: нужно оценить экспоненциальную производящую функцию в правильно выбранной точке с помощью неравенства Маркова.

Вложение метрических пространств в l^1

Январь 9, 2011

В посте про разреженный разрез осталась недоказанной теорема Бургейна про вложение метрик в \ell^1.

Пусть у нас есть конечное метрическое пространство X (метрику на нем обозначим d), состоящее из n точек. Мы покажем, что существует вложение \sigma \colon X \to \mathbb{R}^{O(\log^2 n)} такое, что для любых двух точек x, y \in X выполняются такие неравенства: d(x, y) \cdot \Omega(\log n) \leq \|\sigma(x) - \sigma(y)\|_{\ell^1} \leq d(x, y) \cdot O(\log^2 n).

Конструкция будет вероятностная: мы будем выбирать подмножества S_{ij} \subseteq X, где i = 1, 2, \ldots, \log n j = 1, 2, \ldots, M (M — некоторый параметр, который мы выберем позже), случайно. \mathrm{Pr}[x \in S_{ij}] = 2^{-i}, и все эти события независимы. Отображение \sigma будет действовать из X в \mathbb{R}^{M \log n}: (\sigma(x))_{ij} := d(x, S_{ij}), где d(x, A) обозначает расстояние от точки до множества. Мы докажем, что это отображение требуемое с вероятностью не меньше 1/2 при M = O(\log n).

Сразу заметим, что соотношение \|\sigma(x) - \sigma(y)\|_{\ell^1} \leq d(x, y) \cdot O(\log^2 n) очевидно (оно следует из аддитивности \ell^1-нормы по координатам и неравенства треугольника). Таким образом, нам остается доказать нижнюю оценку.

Рассмотрим две точки x, y \in X. Мы хотим доказать, что \sigma не очень сильно уменьшает расстояние между ними. Обозначим B(x, r) замкнутый шар с центром в x и радиусом r, а B_0(x, r) аналогичный открытый шар. Обозначим r_i минимальный радиус такой, что |B(x, r_i)| \geq 2^i и |B(y, r_i)| \geq 2^i. Пусть t — минимальное число такое, что r_t + r_{t-1} \geq d(x, y). Переобозначим r_t := d(x, y) - r_{t-1}.

Мы докажем, что для каждого i = 1, 2, \ldots, t выполняется неравенство \mathrm{Pr}[|d(x, S_{ij}) - d(y, S_{ij})| \geq r_i - r_{i-1}] \geq c_1, где c_1 — некоторая абсолютная положительная константа. Вспоминая определение r_i, заметим, что не умаляя общности можно считать, что |B_0(x, r_i)| < 2^i. По определению r_{i-1} имеем, что |B(y, r_{i-1})| \geq 2^{i-1}. Так как r_{i-1} + r_i \leq d(x, y), то шары B_0(x, r_i) и B(y, r_{i-1}) не пересекаются. Отсюда легко видеть, что вероятность того, что S_{ij} не заденет B_0(x, r_i) и заденет B(y, r_{i-1}) отделена от нуля. А значит и вероятность того, что |d(x, S_{ij}) - d(y, S_{ij})| \geq r_i - r_{i-1} отделена от нуля.

Теперь, применяя неравенство Чернова, видим, что можно выбрать M = O(\log n) так, что для любого i = 1, 2, \ldots, \log n выполняется \mathrm{Pr}[\sum_{j=1}^M |d(x, S_{ij}) - d(y, S_{ij})| \geq \Omega(M) \cdot (r_i - r_{i-1})] \geq 1 - 1 / n^3. Пользуясь неравенством объединения, получаем, что вероятность того, что для любой пары x, y \in X будет выполняться неравенство \sum_{i=1}^t \sum_{j=1}^M |d(x, S_{ij}) - d(y, S_{ij})| \geq \Omega(\log n) \cdot \sum_{i=1}^t (r_i - r_{i-1}), не меньше 1 - \log n / n. Но так как \sum_{i=1}^t (r_i - r_{i-1}) = r_t \geq d(x, y) / 2, то мы получаем требуемое.

Равномерная распределенность точек на окружности

Январь 2, 2011

Пусть \alpha — иррациональное число. Рассмотрим последовательность \{n \alpha\} (фигурные скобки обозначают дробную часть числа). Можно рассматривать ее как последовательность точек окружности единичной длины. Легко доказать, что эти точки всюду плотны на окружности, но, оказывается, верно более сильное утверждение: точки распределены равномерно. В этом посте я бы хотел объяснить очень простое доказательство этого факта, которое узнал от Саши Шеня.

Равномерная распределенность означает, что для любых 0 \leq a < b \leq 1 выполняется такое равенство:
\lim_{N \to \infty} \frac{1}{N} \sum_{n = 1}^N \chi_{[a,b]}(\{n \alpha\}) = b - a
(здесь \chi_{[a,b]} — характеристическая функция отрезка).

Докажем сначала, что если f \in C[0, 1] и f(0) = f(1), то верно такое равенство:
\lim_{N \to \infty} \frac{1}{N} \sum_{n = 1}^N f(n \alpha) = \int_0^1 f(x) dx
(вне [0, 1] доопределяем f периодически).

Доказательство выглядит так:

  • Приблизив равномерно f тригонометрическим многочленом с точностью \epsilon, обе части желаемого равенства изменятся не более, чем на \epsilon,
  • Таким образом, нам остается проверить равенство для одной экспоненты e^{2 \pi i k x}. Проверка очевидна (тут мы как раз используем, что \alpha иррационально).

Теперь мы хотим доказать исходное утверждение про характеристические функции. Они не являются непрерывными, но их можно приблизить последовательностями непрерывных функций f_n и g_n, которые сходятся к \chi_{[a,b]} по норме L^1[0,1], и для которых выполняются поточечные неравенства f_n \leq \chi_{[a,b]} \leq g_n.

Вот что мы имеем:
\int_0^1 f_n(x) dx = \lim_{N \to \infty} \frac{1}{N} \sum_{k=1}^N f_n(k \alpha) \leq
\lim_{N \to \infty} \frac{1}{N} \sum_{k=1}^N \chi_{[a,b]}(\{k \alpha\}) \leq \lim_{N \to \infty} \frac{1}{N} \sum_{k=1}^N g_n(k \alpha) =
\int_0^1 g_n(x) dx

Но крайние интегралы сходятся к b - a. Утверждение доказано.