Archive for Октябрь 2011

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

Октябрь 29, 2011

Мы докажем частный случай теоремы Дворецкого для пространств {\ell_{\infty}^n}.

Theorem 1 Для любого {\epsilon > 0} в {\mathbb{R}^n} найдется подпространство {V} размерности {\Omega(\log_{\epsilon^{-1}} n)}, где {\ell_{\infty}}-норма ведет себя практически как {\ell_2}: существует такая константа {C > 0}, что для любого {x \in V} имеют место неравенства {C \|x\|_{\ell_2} \leq \|x\|_{\ell_{\infty}} \leq (1 + \epsilon) C \|x\|_{\ell_2}}.

Proof: Это утверждение можно переформулировать так: рассмотрим куб {[-1, 1]^n}. Тогда у него найдется центральное сечение {A} размерности {d = \Omega(\log_{\epsilon^{-1}} n)} такое, что {CB_2^d \subset A \subset (1 + \epsilon)CB_2^d}, где {B_2^d} — единичный евклидов шар, а {C} — некоторая константа. То есть у куба есть центральные почти сферические сечения логарифмической размерности!

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

\displaystyle  \left\{x : \sum_{i=1}^{2k-1}\frac{x_i^2}{a_i^2} \leq 1\right\},

где {0 < a_1 \leq a_2 \leq \ldots \leq a_{2k-1}}. Тогда наше искомое подпространство размерности {k} будет задаваться {k-1} линейным уравнением, {i}-е из которых выглядит так:

\displaystyle  x_i \sqrt{\frac{1}{a_i^2} - \frac{1}{a_k^2}} = x_{2k-i} \sqrt{\frac{1}{a_k^2} - \frac{1}{a_{2k-i}^2}}.

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

Таким образом, если мы построим центральное сечение {A} куба размерности {d}, которое является почти эллипсоидом, то из предыдущего рассуждения следует, что существует сечение размерности {d / 2}, которая является почти сферическим. Итак, нам достаточно построить центральное сечение {A} размерности {d = \Omega(\log_{\epsilon^{-1}} n)} такое, что

\displaystyle  B_2^d \subset TA \subset (1 + \epsilon)B_2^d,

где {T} — линейное отображение {\mathbb{R}^d}.

Мы будем рассматривать тела вида {\{x \in \mathbb{R}^d: \forall i \in [m] \quad |(x, v_i)| \leq 1\}}, где {v_1, v_2, \ldots, v_m \in S^{d-1}}.

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

\displaystyle  x \mapsto ((x, v_1), (x, v_2), \ldots, (x, v_m)).

Во-вторых, такие тела содержат {B_2^d}. В-третьих, ясно, что тело такого вида лежит в {(1 + \epsilon)B_2^d} тогда и только тогда, когда для каждого {\theta \in S^{d-1}} найдется {v_i} такое, что {|(\theta, v_i)| \geq \frac{1}{1 + \epsilon}}. Задача свелась к такой: покрыть {S^{d-1}} как можно меньшим количеством шапочек (множеств вида {\left\{x \in S^{d-1}: (x, v) \geq \frac{1}{1 + \epsilon}\right\}}). Для этого достаточно построить {\Theta(\sqrt{\epsilon})}-сеть на {S^{d-1}}. Рассуждениями аналогичными доказательству теоремы Варшамова-Гилберта можно показать, что существует сеть размера {(\Theta(\epsilon^{-1/2}))^d}.

\Box

Реклама

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

Октябрь 6, 2011

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

Theorem 1 Если {n_1, n_2, \ldots, n_k} — длины слов однозначного кода, то

\displaystyle  			2^{-n_1} + 2^{-n_2} + \ldots + 2^{-n_k} \leq 1.

Proof: Для удобства будем считать, что слова у нас не в алфавите {\{0, 1\}}, а в алфавите {\{a, b\}}. Выберем некоторое натуральное число {l} и запишем формальную сумму:

\displaystyle  			(w_1 + w_2 + \ldots + w_k)^l,

где {w_i} — наши слова. Например, если код состоит из слов {\{ab, ba, bba\}}, то сумма будет выглядеть так:

\displaystyle  			(ab + ba + bba)^l.

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

\displaystyle  			(ab + ba + bba)^2 = abab + abba + abbba + baab + baba + babba + bbaab + bbaba + bbabba.

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

Теперь будем подставлять в это выражение {a = b = 1/2}. Слева получится {(2^{-n_1} + 2^{-n_2} + \ldots + 2^{-n_k})^l}, а справа — не более, чем {\max(n_1, n_2, \ldots, n_k) \cdot l}, так как для любого {t} справа не более, чем {2^t} слов длины {t} (так как все слова различны).

Предположим теперь, что {2^{-n_1} + 2^{-n_2} + \ldots + 2^{-n_k} > 1}. Тогда левая часть растет экспоненциально при росте {l}, а правая — линейно. Противоречие. \Box

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

Октябрь 6, 2011

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

Обозначим случайные величины соответствующие сдвигам {X_1, X_2, \ldots, X_n \in \{-1, 1\}}, а {S_n = X_1 + X_2 + \ldots + X_n} — положение частицы после {n} шагов. Мы хотим доказать, что {S_n} достаточно сильно сконцентрирована вокруг своего математического ожидания (которое, как несложно заметить, равно нулю). Центральная предельная теорема говорит нам, что

\displaystyle  		\frac{S_n}{\sqrt{n}} \xrightarrow{d} N(0, 1),

где сходимость понимается как сходимость по распределению при {n \rightarrow \infty}. То есть в пределе {S_n} отклоняется от нуля не более, чем на {3 \sqrt{n}}, с вероятностью порядка {0.001}. К сожалению, центральная предельная теорема ничего не говорит о скорости сходимости, а в приложениях часто полезно иметь аналогичные утверждения для конечного {n}. Есть варианты центральной предельной теоремы (например, теорема Берри-Эссеена), которые дают какую-то оценку на скорость сходимости при некоторых дополнительных условиях (конечность третьего момента). Но для {S_n} доказать сильную концентрацию вокруг нуля проще непосредственно.

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

Theorem 1

\displaystyle  			\mathrm{Pr}[|S_n| \geq t \sqrt{n}] \leq \frac{1}{t^2}

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

\displaystyle  			\mathrm{Pr}[|S_n| \geq t \sqrt{n}] = \mathrm{Pr}[S_n^2 \geq t^2 n] \leq \frac{\mathrm{E}[S_n^2]}{t^2 n} = \frac{1}{t^2}.

\Box

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

Theorem 2

\displaystyle  			\mathrm{Pr}[|S_n| \geq t \sqrt{n}] \leq \frac{3}{t^4}

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

\displaystyle  			\mathrm{Pr}[|S_n| \geq t \sqrt{n}] = \mathrm{Pr}[S_n^4 \geq t^4 n^2] \leq \frac{\mathrm{E}[S_n^4]}{t^4 n^2} = \frac{3 - \frac{2}{n}}{t^4} \leq \frac{3}{t^4}.

\Box

Дальше можно воспользоваться шестым моментом и получить оценку {O(1 / t^6)} и т. д. Но центральная предельная теорема в пределе дает нам оценку порядка {e^{-\Omega(t^2)}}, которую никакой константный момент обеспечить не в состоянии. Поэтому нам нужен какой-то новый трюк.

Рассмотрим преобразование Лапласа {f(\lambda) = \mathrm{E}\left[e^{\lambda S_n}\right]}. Оказывается, что используя его, можно получить хорошую оценку на концентрацию {S_n}.

Theorem 3

\displaystyle  			\mathrm{Pr}[S_n \geq t \sqrt{n}] \leq e^{-t^2/2}

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

\displaystyle  			\mathrm{Pr}[S_n \geq t \sqrt{n}] = \mathrm{Pr}\left[e^{\lambda S_n} \geq e^{\lambda t \sqrt{n}}\right] \leq \frac{f(\lambda)}{e^{\lambda t \sqrt{n}}}.

Вычислим {f(\lambda)}. Вспомним, что {S_n = X_1 + X_2 + \ldots + X_n}, где {X_i} — независимые {\pm 1} сдвиги. Отсюда получаем

\displaystyle  			f(\lambda) = \mathrm{E}\left[e^{\lambda S_n}\right] = \left(\mathrm{E}\left[e^{\lambda X_1}\right]\right)^n = (\cosh \lambda)^n.

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

Lemma 4

\displaystyle  				\cosh \lambda \leq e^{\lambda^2/2}

Proof:

\displaystyle  				\cosh \lambda = \sum_{k=0}^{\infty} \frac{\lambda^{2k}}{(2k)!} \leq \sum_{k=0}^{\infty} \frac{\lambda^{2k}}{2^k k!} = e^{\lambda^2 / 2}

\Box

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

\displaystyle  			\mathrm{Pr}[S_n \geq t \sqrt{n}] \leq \frac{f(\lambda)}{e^{\lambda t \sqrt{n}}} = \frac{(\cosh \lambda)^n}{e^{\lambda t \sqrt{n}}} \leq e^{\lambda^2 / 2 - \lambda t \sqrt{n}}

Видно, что правая часть минимальна, если выбрать {\lambda = t / \sqrt{n}}. Итого, получаем

\displaystyle  			\mathrm{Pr}[S_n \geq t \sqrt{n}] \leq e^{-t^2 / 2}.

\Box

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

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

\displaystyle  		f(\lambda) = \sum_{k=0}^{\infty} \frac{\lambda^k \mathrm{E}[S_n^k]}{k!},

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

С другой стороны, моменты применимы в некоторых ситуациях, когда преобразование Лапласа не применимо. Например, пусть известно, что {X_1, X_2, \ldots, X_n} — попарно независимы, а не независимы в совокупности (это гораздо более слабое условие, например, для того, чтобы сгенерировать {n} попарно независимых битов, достаточно всего {O(\log n)} истинно независимых битов). Тогда оценка {O(1 / t^2)} по-прежнему имеет место, так как все, что мы используем, — это равенство {\mathrm{E}[X_i X_j] = \mathrm{E}[X_i] \mathrm{E}[X_j]}. Аналогично, если {X_1, X_2, \ldots, X_n} — 4-независимые, то имеет место оценка {O(1 / t^4)} и т. д.

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

Октябрь 3, 2011

Пусть G = (V, E) — простой ненаправленный граф. Будем интересоваться его укладками на плоскости, а точнее, минимально возможным количеством пересечений при укладке. Обозначим эту величину c(G). Например, для планарных графов c(G) = 0. Обозначим n := |V|, m := |E|.

Теорема. c(G) \geq m^3 / 64n^2 - n.

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

Докажем сначала, что c(G) \geq m - 3n. Это совсем просто — в планарных графах количество ребер не больше 3n, а любой граф можно превратить в планарный, удалив c(G) ребер.

Теперь докажем оценку из условия теоремы. Будем делать это вероятностным методом. Рассмотрим какую-то укладку G с k пересечениями. Рассмотрим подграф индуцированный случайным подмножеством V. Каждая вершина входит в это множество независимо с вероятностью p, которую мы выберем позднее. Тогда в среднем останется np вершин, mp^2 ребер и kp^4 пересечений. Пользуясь слабой оценкой, получаем, что k \geq mp^{-2} - 3np^{-3}. Теперь будем оптимизировать k. Если m \leq 4n, то оценка очевидна, а если m > 4n, то p = 4n / m < 1 доставляет оптимум.

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