Dowody, które ujawniają głębszą strukturę

35

Standardowy dowód na powiązanie z Chernoffem (z podręcznika Randomized Algorytmy ) korzysta z funkcji nierówności Markowa i funkcji generowania momentu, z odrobiną rozszerzenia Taylora. Nic zbyt trudnego, ale nieco mechanicznego.

Ale istnieją inne dowody związane z Chernoffem, które ujawniają głębszą strukturę napędzającą wynik. Na przykład istnieje wersja teoretyczno-informacyjna, która wykorzystuje metodę typów, czego przykładem jest ten artykuł Impagliazzo i Kabanets , a także krótki post Sanjoyego Dasgupty . Te ostatnie dowody są bardziej „intuicyjne”, ponieważ zapewniają uogólnienie standardowego wyniku, a także wyjaśniają, skąd biorą się śmieszne wyrażenia w wykładniku (rozbieżność KL).

Jakie są dobre przykłady takich rzeczy? Aby być bardziej konkretnym, oto zasady:

Oświadczenie powinno być dość dobrze znane (coś, czego można by się nauczyć na jakiejś klasie absolwentów)

Powinien istnieć „standardowy” dowód dostępny w podręcznikach lub standardowym materiale odniesienia, który jest „powszechnie” nauczany

Powinien istnieć alternatywny dowód, który nie jest tak dobrze znany, NIE jest powszechnie nauczany i albo dowodzi bardziej ogólnego stwierdzenia, albo łączy to stwierdzenie z głębszą strukturą matematyczną.

Zacznę od dwóch przykładów.

Chernoff związał się
- dowód „podręcznikowy”: nierówność markowa, funkcje generujące moment, ekspansja Taylora (MR)
- Niezbyt częsty i wnikliwy dowód: metoda typów, wykładnik ogona obejmujący rozbieżność KL
Schwartz-Zippel Lemma
- Dowód „podręcznikowy”: podstawowy przypadek obejmujący wielomian jednoznaczny. Indukcja od liczby zmiennych
- dowód „niecodzienny”: argument geometryczny za pośrednictwem Dany Moshkovitz (i Per Vognsen )

Poproszę jeden przykład na odpowiedź.

ps Niekoniecznie sugeruję, że należy uczyć niezwykłego dowodu : bezpośredni dowód jest często łatwiejszy dla studentów. Ale w tym sensie, że „dowody pomagają nam zrozumieć”, te alternatywne dowody są bardzo pomocne.

big-list proofs Suresh Venkat
źródło

23

Nie jestem pewien, czy jest to dokładnie to, czego szukasz, ponieważ widziałem „niecodzienny” dowód w podręcznikach, ale: czas O (n log n) jest ograniczony do szybkiego sortowania.

Dowód „podręcznikowy”: skonfiguruj losową relację powtarzalności, udowodnij przez indukcję, że ma pożądane rozwiązanie.
Dowód „niecodzienny”: znajdź prosty wzór na prawdopodobieństwo porównania dowolnych dwóch elementów (to tylko 2 / (d + 1), gdzie d jest różnicą między ich szeregami w uporządkowanej kolejności) i zastosuj liniowość oczekiwań i szeregów harmonicznych obliczyć oczekiwaną liczbę porównywanych par.

Test podręcznika wymaga mniej twórczego wglądu, ale niecodzienny dowód wprowadza technikę, która jest bardzo przydatna w analizie innych algorytmów, np. W przypadku randomizowanych algorytmów przyrostowych w geometrii obliczeniowej.

David Eppstein
źródło

3

Myślę, że to działa. to dobry przykład. masz rację, że „niecodzienny” dowód znajduje się również w podręcznikach, ale wciąż nie jest tak powszechny.

Suresh Venkat

1

Od ponad dekady uczę studentów tego „niecodziennego” dowodu.

Jeffε

Nie wiem, co myślą o tym inni; ale Jon Bentley podał bardzo elegancką analizę środowiska uruchomieniowego dla oczekiwanego szybkiego środowiska uruchomieniowego w tekście Beautiful Code. Możesz również uzyskać dostęp do jego filmu na ten sam temat <a href=" youtube.com/watch?v=aMnn0Jq0J-E"> tutaj </ a >. Jestem prawie pewien, że jest to „analiza książki” oczekiwanego czasu wykonywania

Quicksort

19

Dorzucę się jedną z komplikacji, dowód, że BPP jest w . Dowodem podręcznik jest wynikiem Lautemann, tylko zapisz ekspresji i pokazać, że działa ze zwykłą probabilistyczny argument. Niezwykły dowód: odgadnij trudną funkcję ( zgadnij, sprawdź twardość) i podłącz ją do generatora Nisan-Wigderson. $\Sigma_2^p$ $\exists\forall$ $\exists$ $\forall$

Lance Fortnow
źródło

Co więcej, dowód Lautemanna znacznie upraszcza dowód Sipsera (1983), który Sipser przypisuje Gacsowi.

MS Dousti,

1

Czy istnieje odniesienie do „niecodziennego” dowodu, czy jest to folklor?

MS Dousti,

2

Dowód znajduje się w gazecie Nisana-Wigdersona.

Lance Fortnow,

2

To „niezwykły dowód” w porządku, ale jakie jest „nowe rozumienie” z tego dowodu? Myślę, że dowód Lautemanna jest bardziej pouczający. Czy coś mi umyka?

V Vinay,

13

Wszyscy wiemy dla Bernoulliego powinien zachowywać się jak Gaussa z odchyleniem standardowym , prawda? Udowodnijmy to, odnosząc się bezpośrednio do Gaussów! Biorąc liczbę całkowitą, $\sum_i a_iX_i$ $\pm 1$ $X_i$ $\sigma = \|a\|_2$ $t \ge 2$

\begin{array}{rcl} E [{(\sum_{i} a_{i} X_{i})}^{t}] & = & \sum_{i_{1}, \dots, i_{t}} (\prod_{j = 1}^{t} a_{i_{j}}) E [\prod_{j = 1}^{t} X_{i_{j}}] \\ \leq & \sum_{i_{1}, \dots, i_{t}} (\prod_{j = 1}^{t} | a_{i_{j}} |) E [\prod_{j = 1}^{t} X_{i_{j}}] \\ = & \sum_{\begin{matrix} i_{1} < \dots < i_{m} \\ r_{1}, \dots, r_{m} \\ \sum_{j} r_{j} = t \\ \forall j r_{j} > 0 \end{matrix}} (\binom{t}{r_{1}, \dots, r_{m}}) (\prod_{j = 1}^{m} | a_{i_{j}} |^{r_{j}}) (\prod_{j = 1}^{m} E [X_{i_{j}}^{r_{j}}]) \end{array}

$\begin{eqnarray*} \mathbf{E}\left[\left(\sum_i a_iX_i\right)^t\right] &=& \sum_{i_1,\ldots,i_t} \left(\prod_{j=1}^t a_{i_j}\right) \mathbf{E}\left[\prod_{j=1}^t X_{i_j}\right]\\ &\le& \sum_{i_1,\ldots,i_t} \left(\prod_{j=1}^t |a_{i_j}|\right) \mathbf{E}\left[\prod_{j=1}^t X_{i_j}\right]\\ &=& \sum_{\substack{i_1<\ldots< i_m\\ r_1,\ldots,r_m\\ \sum_j r_j = t\\ \forall j\ r_j > 0}} \binom{t}{r_1,\ldots,r_m}\left(\prod_{j=1}^m |a_{i_j}|^{r_j}\right)\left(\prod_{j=1}^m \mathbf{E}[X_{i_j}^{r_j}]\right) \end{eqnarray*}$

$r_j$ $0$ $1$ $X_i$ $G_i$ $r_j$ $0$ $r_j$ $1$

E [{(\sum_{i} a_{i} X_{i})}^{t}] \leq E [{(\sum_{i} | a_{i} | G_{i})}^{t}]

$\mathbf{E}\left[\left(\sum_i a_iX_i\right)^t\right] \le \mathbf{E}\left[\left(\sum_i |a_i|G_i\right)^t\right]$

$2$ $\sum_i |a_i| G_i$ $\|a\|_2$ $t$ $\|a\|_2^t \cdot t! / (2^{t/2} \cdot (t/2)!)$ $\|a\|_2^tt^{t/2}$

P r [| \sum_{i} a_{i} X_{i} | > λ] < 2^{O (t)} \cdot λ^{- t} \cdot ‖ a ‖_{2}^{t} t^{t / 2}

$\mathbf{Pr}\left[\left|\sum_i a_iX_i\right| > \lambda\right] < 2^{O(t)}\cdot \lambda^{-t}\cdot \|a\|_2^t t^{t/2}$

t = λ^{2} / (C \cdot ‖ a ‖_{2}^{2})

$t = \lambda^2 / (C\cdot \|a\|_2^2)$

C

$C$

e x p (- Ω (λ^{2} / ‖ a ‖_{2}^{2}))

$\mathrm{exp}(-\Omega(\lambda^2 / \|a\|_2^2))$

X_{i}

$X_i$

Jelani Nelson
źródło

6

$A$ $r_i$ $i$ $A$

\prod_{i} (r_{i}!)^{1 / r_{i}} .

$\prod_i (r_i!)^{1/r_i}.$

Timothy Chow
źródło

Dowody, które ujawniają głębszą strukturę

Odpowiedzi: