City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Вероятностные оценки: метод сжатия
Lovasz local lemma and probabilistic method

What: Lecture
When: Sunday, 01 March 2015, 11:15–12:50
Where: ПОМИ РАН

Description

Вероятностные оценки: метод сжатия

  • Один пример такого рода (для чисел Рамсея) уже был
  • Другой пример: закон больших чисел для вероятности \(1/2\)
    • Среднее \(1/2\)
    • Среднее квадратичное отклонение и оценки с неравенством Чебышёва
    • Экспоненциальная оценка методом сжатия: арифметическое кодирование требует \(nH(p)\) битов
    • Для информации: неравенство Чернова и Азумы--Хёфдинга
  • Сильно непериодическое слово: расположить по кругу \(n\) битов так, чтобы любой поворот менял как минимум \(10\%\) битов (при достаточно большом \(n\))
  • Тот же вопрос для \(49\%\) изменённых битов (усреднение!)

Ещё о вероятностных доказательствах

  • Задача о коробке: если одна прямоугольная коробка помещается в другую, то сумма измерений первой не больше, чем у второй. (Можно ли перехитрить метро?). Решение: сумма измерений пропорциональная средней ширине коробки в случайном направлении
  • Задача о несравнимых множествах: антицепь в семействе подмножеств $2n$-элементного множества (порядок по включению) содержит не более $\binom{2n}{n}$ элементов. Доказательство: рассмотрим случайный процесс добавления элементов (в случайном порядке), события <<пройти через данный элемент антицепи>> несравнимы, значит, суммы их вероятностей не больше $1$, а они минимально возможные, когда размер ровно половинный
  • Игры с полной информацией: существование выигрышной стратегии у одного из игроков. Следствие: если есть вероятностная стратегия для одного из игроков, гарантирующая положительную вероятность выигрыша (против любой детерминированной стратегии второго), то есть и детерминированная стратегия. Пример: игра против начальника: подчинённые разных рангов ($0,1,2,\ldots$) делятся на две группы, начальник увольняет по своему выбору одну, но уменьшает ранги всех членов второй на $1$; задача подчинённых --- чтобы кто-то достиг ранга $0$. Вероятностная стратегия начальника: выбирать случайную группу. Вероятность выжить для ранга $k$ равна $2^{-k}$, если сумма меньше $1$, то есть вероятность извести всех (а значит, есть и детерминированная стратегия извести всех)
  • Бесконечные пространства и события меры $0$: построение иммунного множества с иммунным дополнением, построение двух несравнимых степеней по Тьюрингу

Дерандомизация

  • Игра против начальника: выбираем ту группу, где сумма $2^{-k}$ меньше, она будет меньше $1/2$, после повышения рангов в сумме будет меньше $1$, то есть ранг $0$ недостижим
  • Разрез не менее чем половины рёбер: поддерживаем условное математическое ожидание не меньше $E/2$: получаем жадный алгоритм (более половины новых рёбер разноцветные)
  • Отыскание выполняющего набора для 3-кнф, где не меньше $7/8$ условий выполнены

Video