Стандартное доказательство границы Чернова (из учебника « Рандомизированные алгоритмы» ) использует неравенство Маркова и функции, порождающие моменты, с добавлением некоторого расширения Тейлора. Ничего слишком сложного, но несколько механического.
Но есть и другие доказательства, связанные с Черновым, которые раскрывают более глубокую структуру, определяющую результат. Например, есть теоретико-информационная версия, которая проходит через метод типов, примером которого является эта статья Impagliazzo и Kabanets , а также этот краткий пост Sanjoy Dasgupta . Эти последние доказательства являются более «интуитивными» в том смысле, что они обеспечивают обобщение стандартного результата, а также объясняют, откуда происходят забавные термины в показателе степени (это KL-дивергенция).
Каковы хорошие примеры таких вещей? Чтобы быть более конкретным, вот правила:
- Утверждение должно быть достаточно известным (то, чему научат в какой-нибудь аспирантуре)
- Должно быть «стандартное» доказательство, доступное в учебниках или стандартных справочных материалах, которые «обычно» преподаются
- Должно быть альтернативное доказательство, которое не так хорошо известно, НЕ обычно преподается, и либо доказывает более общее утверждение, либо связывает утверждение с более глубокой математической структурой.
Я начну с двух примеров.
Черновы связаны
- «учебное» доказательство: неравенство Маркова, функции, порождающие моменты, разложение Тейлора (MR)
- Необычное и проницательное доказательство: метод типов, показатель степени хвоста с KL-дивергенцией
-
- «учебное» доказательство: базовый случай, включающий одномерный полином. Индукция по числу переменных
- «необычное» доказательство: геометрический аргумент через Дану Мошковиц (и Пера Вогнсена )
Один пример за ответ, пожалуйста.
ps Я не обязательно подразумеваю, что необычное доказательство должно преподаваться: прямое доказательство часто легче для студентов. Но в том смысле, что «доказательства помогают нам понять», эти альтернативные доказательства очень полезны.
Я выброшу один из сложности, доказательство того, что BPP находится в . Доказательство из учебника принадлежит Лаутеманну, просто запишите выражение ∃ ∀ и покажите, что оно работает с простым вероятностным аргументом. Необычное доказательство: угадать сложную функцию ( ∃ угадать, ∀ проверить твердость) и подключить ее к генератору Нисана-Вигдерсона.Σp2 ∃∀ ∃ ∀
источник
Мы все знаем , для Бернулли ± 1 X я должен вести себя как гауссова со стандартным отклонением σ = | | | | 2 , не так ли? Итак, давайте докажем это, напрямую связавшись с гауссианами! Взяв t ≥ 2 целое число,ΣяaяИкся ± 1 Икся σ= ∥ a ∥2 t ≥ 2
Теперь давайте посмотрим на приведенную выше сумму справа. В любом заданном слагаемом либо некоторый является нечетным, делая ожидание , либо все четными, делая его . Представьте себе замену всех гауссовскими . Тогда мы были бы в подобном сценарии: нечетное бы , и все четные бы продукт по крайней мере . Таким образом, гауссовский случай термин за термином доминирует в случае Бернулли. Таким образом,rj 0 1 Xi Gi rj 0 rj 1
Но в силу устойчивости гауссиана сам по себе гауссов со стандартным отклонением , поэтому мы знаем его моменты! Таким образом, наш й момент ограничен (Примерно ); это известно как неравенство Хинчина. Затем,2 ∑i|ai|Gi ∥a∥2 t ∥a∥t2⋅t!/(2t/2⋅(t/2)!) ∥a∥t2tt/2
источник
Минк предположил, и Брэгман доказал, что если - это матрица 0-1 с 1 в строке , то перманент будет не более Существует короткое доказательство в учебнике Алона и Спенсера « Вероятностный метод» , но, вероятно, «книжное» доказательство является доказательством Джайкумара Радхакришнана с использованием энтропии ( J. Combin. Theory Ser. A 77 (1997), 161-164). Из утверждения результата совсем не очевидно, что понятие энтропии лежит здесь под поверхностью.r i i A ∏ i ( r i ! ) 1 / r i .A ri i A
источник