Archive for Февраль 2011

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

Февраль 18, 2011

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

Итак, пусть S \subseteq \{-1, 1\}^n. Мы хотим оценить количество ребер куба, ровно один конец которых лежит в S (обозначим это количество A). Мы докажем, что A / |S| \geq n - \log |S|.

Возьмем случайный элемент S. Обозначим полученную случайную величину (X_1, \ldots, X_n).

Во-первых, очевидно, что \mathbf{H}(X_1, \ldots, X_n) = \log |S|.

Во-вторых, несложно понять, что \sum_{i=1}^n \mathbf{H}(X_i \mid X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_n) = n - A / |S|.

Теперь делаем финальную выкладку:
\log |S| = \mathbf{H}(X_1, \ldots, X_n) =
= \mathbf{H}(X_1) + \mathbf{H}(X_2 \mid X_1) + \ldots + \mathbf{H}(X_n \mid X_1, \ldots, X_{n-1}) \geq
\geq \sum_{i=1}^n \mathbf{H}(X_i \mid X_1, \ldots, X_{i-1}, X_{i+1}, \ldots, X_n) = n - A / |S|.

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

Реклама