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

• Один пример такого рода (для чисел Рамсея) уже был
• Другой пример: закон больших чисел для вероятности \(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$ условий выполнены