Archive for Ноябрь 2010

Изопериметрическая задача на булевом кубе

Ноябрь 17, 2010

В прошлом посте мы рассматривали изопериметрическую задачу на плоскости. Теперь рассмотрим некоторый ее дискретный аналог, в котором тоже помогает преобразование Фурье (на этот раз на булевом кубе, см. [1], [2]).

Рассмотрим булев куб \{0, 1\}^n. Будем рассматривать его как граф — ребра соединяют вершины, которые отличаются ровно в одной позиции. Таким образом, из каждой вершины выходит n ребер. Мы хотим разбить куб на две равные части (по 2^{n-1} вершин) так, чтобы между ними было минимальное количество ребер. Рассмотрев разбиение \{0, 1\}^n = \{x \mid x_1 = 0\} \cup \{x \mid x_1 = 1\}, видно, что можно обойтись 2^{n-1} ребрами. Оказывается, что меньше ребер не бывает. Более того, минимум достигается только на множествах такого вида.

Задачу удобно переформулировать в терминах булевых функций. Как всегда при этом перейдем от \{0, 1\} к \{-1, 1\}. Назовем чувствительностью функции f \colon \{-1, 1\}^n \to \{-1, 1\} на входе x мощность множества \{i \mid f(x) \ne f(x e_i)\}, где e_i — вектор с единственной -1 в позиции i. Назовем средней чувствительностью функции f (и обозначим \mathrm{as}(f)) математическое ожидание ее чувствительности по всем входам. Примеры: \mathrm{as}(1) = 0, \mathrm{as}(x_i) = 1, \mathrm{as}(x_1 x_2 \ldots x_n) = n, \mathrm{as}(\mathrm{maj}_n) = \Theta(\sqrt{n}).

Несложно видеть, что нашу задачу можно переформулировать так: нужно доказать, что если \mathrm{Pr}[f(x) = -1] = \mathrm{Pr}[f(x) = 1] = 1/2, то \mathrm{as}(f) \geq 1. А если при этом \mathrm{as}(f) = 1, то имеет вид f(x) = x_i или f(x) = -x_i.

Это довольно просто сделать, воспользовавшись преобразованием Фурье на булевом кубе. Проделав выкладку в стиле [1] или [2], несложно видеть, что \mathrm{as}(f) = \sum_{\alpha} |\alpha| \hat{f}^2_{\alpha}. Условие \mathrm{Pr}[f(x) = -1] = \mathrm{Pr}[f(x) = 1] = 1/2 дает нам \hat{f}_{\emptyset} = 0. Отсюда следует, что \mathrm{as}(f) \geq \sum_{\alpha} \hat{f}^2_{\alpha} = 1. Первая часть желаемого утверждения доказана.

Если мы знаем, что \mathrm{as}(f) = 1, то ясно, что спектр f лежит в \{\alpha \mid |\alpha| = 1\}. Так как мы знаем, что f булева, то ясно, что она может иметь вид только f(x) = x_i или f(x) = -x_i.

Таким образом, в изопериметрической задаче на булевом кубе нам опять помогло преобразование Фурье. Интересно, то что в обеих задачах возникло преобразование Фурье — это совпадение или нет?

Реклама

Изопериметрическая задача на плоскости

Ноябрь 17, 2010

Широко известен такой факт: среди всех плоских кривых длины L наибольшую площадь ограничивает окружность. Мы его докажем для случая C^1-гладких кривых. Более того, мы покажем, что окружность — единственный глобальный максимум.

Сначала докажем вспомогательную лемму. Если fC^1-гладкая функция на [0, 2\pi] такая, что выполняется условие \int_0^{2\pi} f(x) dx = 0, то верно такое неравенство: \int_0^{2\pi} f^2(x) dx \leq \int_0^{2\pi} (f')^2(x) dx. При этом, равенство достигается на функциях вида f(x) = \alpha \sin x + \beta \cos x.

Лемма доказывается разложением f в ряд Фурье и применение равенства Парсеваля. Подробности оставляем читателю в качестве упражнения.

Пусть у нас есть кривая длины L. Параметризуем ее длиной: получатся две L-периодические функции x(s) и y(s). Так как s — длина, то будет выполняться соотношение (x')^2 + (y')^2 = 1. Перейдем от L-периодических функций к 2\pi-периодическим, сделав линейную замену переменных. Получим две 2\pi-периодические функции f(t) и g(t), которые связаны соотношением (f')^2 + (g')^2 = L^2 / 4 \pi^2. Теперь оценим площадь S, которую ограничивает наша кривая. Из формулы Грина следует, что S = \int_0^{2\pi} f g' dt. Теперь преобразуем этот интеграл:
\int_0^{2\pi} f g' dt = 1/2 \cdot \int_0^{2\pi} (f^2 + (g')^2 - (f - g')^2) dt \leq 1/2 \int_0^{2\pi} (f^2 + (g')^2) dt. Заметим, что сдвинув кривую, можно считать, что \int_0^{2\pi} f(t) dt = 0. Пользуясь леммой, делаем решающий рывок:
S \leq 1/2 \int_0^{2\pi} (f^2 + (g')^2) dt \leq 1/2 \int_0^{2\pi} ((f')^2 + (g')^2) dt = L^2 / 4\pi.

Видно, что равенство достигается лишь на окружности.

Вот так метод Фурье мистически помогает в изопериметрической задаче. Далее мы рассмотрим изопериметрическую задачу на булевом кубе, и, оказывается, там тоже оказывается полезным преобразование Фурье.

Нетривиальный спектральный зазор графа

Ноябрь 7, 2010

Этот пост является продолжением поста про собственные числа и случайные блуждания. Рекомендуется сначала прочитать его.

Пусть G = (V, E) — ненаправленный d-регулярный связный граф, в каждой вершине которого есть петля. Пусть \lambda_2 — второе по абсолютной величине собственное число нормализованной матрицы смежности. Мы докажем, что |\lambda_2| = 1 - \Omega(1 / n^2). Из этой оценки, как мы знаем, следует, что случайное блуждание из O(n^3 \log^2 n) шагов с высокой вероятностью посещает все вершины графа.

Вспомним, что |\lambda_2| = \lambda(G) = \max_{\|u\|_{\ell_2} = 1, u \bot \mathbf{1}} \|Au\|_{\ell_2}. Пусть \|u\|_{\ell_2} = 1, u \bot \mathbf{1}, v = Au. Мы хотим доказать, что \|v\|_{\ell_2} = 1 - \Omega(1 / n^2). Для этого достаточно доказать, что \|u\|^2_{\ell_2} - \|v\|^2_{\ell_2} = \Omega(1 / n^2) (так как \|u\|_{\ell_2} = 1, и при возведении в квадрат зазор между единицей и числом увеличивается не более, чем вдвое).

Докажем сначала, что \|u\|^2_{\ell_2} - \|v\|^2_{\ell_2} = \sum_{i,j} A_{ij} (u_i - v_j)^2. Действительно, \sum_{i,j} A_{ij} (u_i - v_j)^2 = \|u\|_{\ell_2}^2 + \|v\|_{\ell_2}^2 - (Au, v) = \|u\|_{\ell_2}^2 - \|v\|_{\ell_2}^2.

Осталось доказать, что \sum_{i,j} A_{ij} (u_i - v_j)^2 = \Omega(1 / n^2). Так как u \bot \mathbf{1}, то \sum_i u_i = 0. А раз \|u\|_{\ell_2} = 1, то найдутся два такие индекса i и j, что u_i - u_j \geq 1 / \sqrt{n}.

Так как граф связный, то найдется путь P = (i = i_1, i_2, \ldots, i_k = j). Будем считать, что P кратчайший. Теперь сделаем такую оценку:
1 / \sqrt{n} \leq u_i - u_j \leq
\leq |u_{i_1} - v_{i_1}| + |v_{i_1} - u_{i_2}| + |u_{i_2} - v_{i_2}| + \ldots
+ |u_{i_{k-1}} - v_{i_{k-1}}| + |v_{i_{k-1}} - u_{i_k}| \leq
\leq \sqrt{2k - 2} \cdot \|(u_{i_1} - v_{i_1}, v_{i_1} - u_{i_2}, u_{i_2} - v_{i_2}, \ldots,
u_{i_{k-1}} - v_{i_{k-1}}, v_{i_{k-1}} - u_{i_k})\|_{\ell_2}.

Отсюда следует, что найдется набор пар (i, j) такой, что A_{ij} \geq 1 / d, а \sum_{i,j} (u_i - v_j)^2 \geq 1 / (2n(k-1)).

Итак, получаем, что \sum_{i,j} A_{ij} (u_i - v_j)^2 \geq 1 / (2dn(k-1)). Так как мы выбирали кратчайший путь, то k - 1 не превосходит диаметра графа. Отсюда следует, что dk = O(n). В итоге, оценка доказана.

Собственные числа и случайные блуждания

Ноябрь 7, 2010

Рассмотрим ненаправленный регулярный (у каждой вершины одинаковая степень d) связный граф G = (V, E). Нас будет интересовать поведение случайных блужданий на G (случайное блуждание — это такой простой процесс: встает в какую-нибудь вершину, а потом несколько раз выбираем случайное ребро и идем по нему). Пусть p — распределение вероятностей на вершинах G. Как же выглядит распределение вероятностей после одного шага случайного блуждания? Очень просто: это будет вектор Ap, где A — матрица смежности, поделенная на d.

Так как G регулярный, то стационарное распределение случайного блуждания будет равномерным. У соответствующего векторы все компоненты будут равны 1 / n — будем обозначать его \mathbf{1}.

Мы будем интересоваться скоростью сходимости распределения на вершинах к равномерному. К примеру, пусть мы хотим оценить \|A^k p  - \mathbf{1}\|_{\ell_2}. Для этого рассмотрим следующую важную характеристику:

\lambda(G) = \max_{\|v\|_{\ell_2} = 1, v \bot 1} \|Av\|_{\ell_2}.

Оказывается, что чем \lambda(G) меньше, тем быстрее распределение сходится к равномерному. Но для начала давайте установим связь между \lambda(G) и собственными числами A.

Так как A симметричная, то у нее есть ортонормированный базис из собственных векторов. Обозначим его v_1, v_2, \ldots, v_n, а соответствующие собственные числа \lambda_1, \lambda_2, \ldots, \lambda_n. Будем считать, что |\lambda_1| \geq |\lambda_2| \geq \ldots \geq |\lambda_n|.

Матрица A стохастическая (все элементы неотрицательные, сумма любой строки и любого столбца — единица), а у стохастических матриц, как несложно понять, собственные числа по модулю не превосходят 1. Мы значем, что у A есть неподвижная точка — вектор \mathbf{1}. Таким образом, можно считать, что \lambda_1 = 1 и v_1 = \mathbf{1}.

Оказывается, что \lambda(G) = |\lambda_2|. Действительно, подпространство векторов, которые ортогональны \mathbf{1} равно линейной оболочке v_2, \ldots, v_n. А A растягивает векторы из этого подпространства не более, чем на |\lambda_2|.

Теперь займемся оценкой скорости сходимости распределения к равномерному (\|A^k p  - \mathbf{1}\|_{\ell_2}). Так как p — распределение вероятностей, то можно представить его в виде p = p' + \mathbf{1}, где p' \bot \mathbf{1}. Теперь произведем такую простую оценку:

\|A^k p  - \mathbf{1}\|_{\ell_2} = \|A^k(p' + \mathbf{1}) - \mathbf{1}\|_{\ell_2} = \|A^k p'\|_{\ell_2} \leq \lambda^k(G) \|p'\|_{\ell_2}

Последний переход верен, так как подпространство векторов, ортогональных \mathbf{1}, является инвариантным для A. Осталось заметить, что так как p' \bot \mathbf{1}, то \|p\|_{\ell_2}^2 = \|p'\|_{\ell_2}^2 + \|\mathbf{1}\|_{\ell_2}^2, а, значит, \|p'\|_{\ell_2} \leq \|p\|_{\ell_2} \leq \|p\|_{\ell_1} = 1.

Таким образом, получаем такую оценку:
\|A^k p  - \mathbf{1}\|_{\ell_2} \leq \lambda^k(G) = |\lambda_2|^k.

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

Оказывается, что верно такое утверждение: если у связного графа в каждой вершине есть петля, то |\lambda_2| = 1 - \Omega(1 / n^2) (мы докажем этот факт в следующем посте). Отсюда несложно получить, что случайное блуждание длины O(n^3 \log^2 n) с высокой вероятностью посещает все вершины графа.