Доказательства, которые раскрывают более глубокую структуру

35

Стандартное доказательство границы Чернова (из учебника « Рандомизированные алгоритмы» ) использует неравенство Маркова и функции, порождающие моменты, с добавлением некоторого расширения Тейлора. Ничего слишком сложного, но несколько механического.

Но есть и другие доказательства, связанные с Черновым, которые раскрывают более глубокую структуру, определяющую результат. Например, есть теоретико-информационная версия, которая проходит через метод типов, примером которого является эта статья Impagliazzo и Kabanets , а также этот краткий пост Sanjoy Dasgupta . Эти последние доказательства являются более «интуитивными» в том смысле, что они обеспечивают обобщение стандартного результата, а также объясняют, откуда происходят забавные термины в показателе степени (это KL-дивергенция).

Каковы хорошие примеры таких вещей? Чтобы быть более конкретным, вот правила:

  1. Утверждение должно быть достаточно известным (то, чему научат в какой-нибудь аспирантуре)
  2. Должно быть «стандартное» доказательство, доступное в учебниках или стандартных справочных материалах, которые «обычно» преподаются
  3. Должно быть альтернативное доказательство, которое не так хорошо известно, НЕ обычно преподается, и либо доказывает более общее утверждение, либо связывает утверждение с более глубокой математической структурой.

Я начну с двух примеров.

  1. Черновы связаны

    • «учебное» доказательство: неравенство Маркова, функции, порождающие моменты, разложение Тейлора (MR)
    • Необычное и проницательное доказательство: метод типов, показатель степени хвоста с KL-дивергенцией
  2. Лемма Шварца-Циппеля

    • «учебное» доказательство: базовый случай, включающий одномерный полином. Индукция по числу переменных
    • «необычное» доказательство: геометрический аргумент через Дану МошковицПера Вогнсена )

Один пример за ответ, пожалуйста.

ps Я не обязательно подразумеваю, что необычное доказательство должно преподаваться: прямое доказательство часто легче для студентов. Но в том смысле, что «доказательства помогают нам понять», эти альтернативные доказательства очень полезны.

Суреш Венкат
источник

Ответы:

23

Я не уверен, что это именно то, что вы ищете, поскольку я видел «необычное» доказательство в учебниках, но: время O (n log n) ограничено для быстрой сортировки.

  • «Учебное» доказательство: установите случайное рекуррентное соотношение, по индукции докажите, что оно имеет желаемое решение.

  • «Необычное» доказательство: найдите простую формулу для вероятности того, что любые два элемента сравниваются (это просто 2 / (d + 1), где d - разница между их рангами в отсортированном порядке), и используйте линейность ожидания и ряд гармоник рассчитать ожидаемое количество пар, которые сравниваются.

Доказательство из учебника требует меньше творческого понимания, но необычное доказательство представляет метод, который очень полезен при анализе других алгоритмов, например, для рандомизированных инкрементальных алгоритмов в вычислительной геометрии.

Дэвид Эппштейн
источник
3
Я думаю, что это работает. Это хороший пример. Вы правы, что «необычное» доказательство также есть в учебниках, но все же не так часто.
Суреш Венкат
1
Я преподаю старшекурсникам это «необычное» доказательство уже более десяти лет.
Джефф
Я не знаю, что другие думают об этом; но Джон Бентли дал очень элегантный анализ времени выполнения для ожидаемой среды выполнения быстрой сортировки в тексте Beautiful Code. Вы также можете просмотреть его видео на ту же тему <a href=" youtube.com/watch?v=aMnn0Jq0J-E"> здесь </ a >. Я почти уверен, что это «анализ книги» ожидаемого времени выполнения быстрой сортировки
Акаш Кумар
19

Я выброшу один из сложности, доказательство того, что BPP находится в . Доказательство из учебника принадлежит Лаутеманну, просто запишите выражение и покажите, что оно работает с простым вероятностным аргументом. Необычное доказательство: угадать сложную функцию ( угадать, проверить твердость) и подключить ее к генератору Нисана-Вигдерсона.Σ2p

Лэнс Фортноу
источник
Кроме того, доказательство Лаутемана значительно упрощает доказательство Сипсера (1983), которое Сипсер приписывает Gacs.
MS Dousti
1
Есть ли ссылка на «необычное» доказательство или это фольклор?
MS Dousti
2
Доказательство содержится в статье Нисана-Вигдерсона.
Лэнс Фортноу
2
Это «необычное доказательство», хорошо, но что такое «новое понимание» из этого доказательства? Я бы подумал, что доказательство Лаутемана более поучительно. Я что-то здесь упускаю?
V Vinay
13

Мы все знаем , для Бернулли ± 1 X я должен вести себя как гауссова со стандартным отклонением σ = | | | | 2 , не так ли? Итак, давайте докажем это, напрямую связавшись с гауссианами! Взяв t 2 целое число,iaiXi±1 Xiσ=a2t2

E[(iaiXi)t]=i1,,it(j=1taij)E[j=1tXij]i1,,it(j=1t|aij|)E[j=1tXij]=i1<<imr1,,rmjrj=tj rj>0(tr1,,rm)(j=1m|aij|rj)(j=1mE[Xijrj])

Теперь давайте посмотрим на приведенную выше сумму справа. В любом заданном слагаемом либо некоторый является нечетным, делая ожидание , либо все четными, делая его . Представьте себе замену всех гауссовскими . Тогда мы были бы в подобном сценарии: нечетное бы , и все четные бы продукт по крайней мере . Таким образом, гауссовский случай термин за термином доминирует в случае Бернулли. Таким образом,rj01XiGirj0rj 1

E[(iaiXi)t]E[(i|ai|Gi)t]

Но в силу устойчивости гауссиана сам по себе гауссов со стандартным отклонением , поэтому мы знаем его моменты! Таким образом, наш й момент ограничен (Примерно ); это известно как неравенство Хинчина. Затем,2i|ai|Gia2ta2tt!/(2t/2(t/2)!)a2ttt/2

Pr[|iaiXi|>λ]<2O(t)λta2ttt/2
Set для достаточно большой постоянной и вы получите гауссову границу хвоста . Я впервые услышал это доказательство неравенства Хинчина в чате с Дэниелом Кейном, но, вероятно, есть более старая ссылка. Обратите внимание, что доказательство также проясняет, какой уровень независимости у вам нужен, чтобы получить различные границы.t=λ2/(Ca22)CX iexp(Ω(λ2/a22))Xi
Джелани Нельсон
источник
6

Минк предположил, и Брэгман доказал, что если - это матрица 0-1 с 1 в строке , то перманент будет не более Существует короткое доказательство в учебнике Алона и Спенсера « Вероятностный метод» , но, вероятно, «книжное» доказательство является доказательством Джайкумара Радхакришнана с использованием энтропии ( J. Combin. Theory Ser. A 77 (1997), 161-164). Из утверждения результата совсем не очевидно, что понятие энтропии лежит здесь под поверхностью.r i i A i ( r i ! ) 1 / r i .AriiA

i(ri!)1/ri.
Тимоти Чоу
источник