Beweise, die eine tiefere Struktur zeigen

35

Der Standardbeweis für die Chernoff-Bindung (aus dem Lehrbuch Randomized Algorithms ) verwendet die Markov-Ungleichungs- und Momenterzeugungsfunktionen, wobei ein wenig Taylor-Expansion hinzukommt. Nichts zu schwierig, aber etwas mechanisch.

Es gibt jedoch auch andere von Chernoff gebundene Beweise, die die tiefere Struktur aufdecken, die das Ergebnis bestimmt. Zum Beispiel gibt es eine informationstheoretische Version, die sich an der Methode der Typen orientiert, die in diesem Aufsatz von Impagliazzo und Kabanets sowie in diesem kurzen Beitrag von Sanjoy Dasgupta veranschaulicht wird . Diese letzteren Beweise sind insofern "intuitiver", als sie eine Verallgemeinerung des Standardergebnisses liefern und auch erklären, woher die lustigen Ausdrücke im Exponenten stammen (es ist eine KL-Divergenz).

Was sind gute Beispiele für solche Dinge? Um genauer zu sein, hier sind die Regeln:

  1. Die Aussage sollte einigermaßen bekannt sein (die Art von Dingen, die in einer Art Abschlussklasse gelehrt würden).
  2. In Lehrbüchern oder Standard-Referenzmaterialien sollte ein "Standard" -Proof vorhanden sein, der "allgemein" vermittelt wird
  3. Es sollte einen alternativen Beweis geben, der nicht so gut bekannt ist, NICHT allgemein gelehrt wird und entweder eine allgemeinere Aussage beweist oder die Aussage mit einer tieferen mathematischen Struktur verknüpft.

Ich beginne mit zwei Beispielen.

  1. Der Tschernoff ist angebunden

    • "Lehrbuch" Beweis: Markov-Ungleichung, Momenterzeugungsfunktionen, Taylor-Expansion (MR)
    • Gelegentlicher und aufschlussreicher Beweis: Typmethode, Exponent des Schwanzes mit KL-Divergenz
  2. Das Schwartz-Zippel-Lemma

    • "Lehrbuch" Beweis: Basisfall mit univariatem Polynom. Induktion über die Anzahl der Variablen
    • "ungewöhnlicher" Beweis: geometrisches Argument über Dana Moshkovitz (und Per Vognsen )

Ein Beispiel pro Antwort bitte.

ps ich was bedeutet nicht unbedingt , dass die ungewöhnliche Beweis sollte gelehrt werden: ein direkter Beweis ist oft einfacher für Studenten. Aber in dem Sinne, dass "Beweise uns helfen zu verstehen", sind diese alternativen Beweise sehr hilfreich.

Suresh Venkat
quelle

Antworten:

23

Ich bin mir nicht sicher, ob das genau das ist, wonach Sie suchen, da ich den "ungewöhnlichen" Beweis in Lehrbüchern gesehen habe, aber: die O (n log n) -Zeit, die für Quicksort gebunden ist.

  • "Lehrbuch" -Proof: Richten Sie eine randomisierte Wiederholungsrelation ein, und beweisen Sie durch Induktion, dass die gewünschte Lösung vorliegt.

  • "Gelegentlicher" Beweis: Finden Sie eine einfache Formel für die Wahrscheinlichkeit, dass zwei Elemente verglichen werden (es ist nur 2 / (d + 1), wobei d die Differenz zwischen ihren Rängen in der sortierten Reihenfolge ist), und verwenden Sie die Linearität der Erwartung und harmonische Reihen um die erwartete Anzahl von Paaren zu berechnen, die verglichen werden.

Der Lehrbuch-Proof erfordert weniger kreative Einsichten, aber der ungewöhnliche Proof führt eine Technik ein, die bei anderen Algorithmus-Analysen sehr nützlich ist, z. B. für randomisierte inkrementelle Algorithmen in der Computergeometrie.

David Eppstein
quelle
3
Ich denke das funktioniert. Es ist ein schönes Beispiel. Sie haben Recht, dass der "ungewöhnliche" Beweis auch in Lehrbüchern vorkommt, aber immer noch nicht so verbreitet ist.
Suresh Venkat
1
Ich unterrichte Studenten seit über einem Jahrzehnt diesen "ungewöhnlichen" Beweis.
Jeffs
Ich weiß nicht, was andere darüber denken. Jon Bentley hat jedoch eine sehr elegante Laufzeitanalyse für die erwartete Laufzeit der schnellen Sortierung im Text Beautiful Code angegeben. Sie können sein Video auch <a href=" youtube.com/watch?v=aMnn0Jq0J-E"> hier </ a > zum selben Thema aufrufen . Ich bin mir ziemlich sicher, dass dies "die Analyse des Buches" der erwarteten Laufzeit von quicksort ist
Akash Kumar
19

Ich werde eine von Komplexität werfen, den Beweis , dass BPP in ist . Der Lehrbuchbeweis stammt von Lautemann. Schreiben Sie einfach den Ausdruck ∃ ∀ auf und zeigen Sie, dass er mit einem einfachen probabilistischen Argument funktioniert. Der unübliche Beweis: Vermutung eine harte Funktion ( zu erraten, Härte zu prüfen) und Stecker in den Nisan Wigderson-Generator.Σ2p

Lance Fortnow
quelle
Hinzu kommt, dass Lautemanns Beweis Sipsers (1983), den Sipser Gacs zuschreibt, stark vereinfacht.
MS Dousti
1
Gibt es eine Referenz für den "ungewöhnlichen" Beweis oder ist es Folklore?
MS Dousti
2
Der Beweis ist in der Nisan-Wigderson-Zeitung.
Lance Fortnow
2
Es ist ein "ungewöhnlicher Beweis", aber was ist das "neue Verständnis" dieses Beweises? Ich würde denken, Lautemanns Beweis ist aufschlussreicher. Vermisse ich hier etwas?
V Vinay
13

iaiXi±1 Xi t 2σ=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])

Schauen wir uns nun die obige Summe rechts an. In jedem gegebenen Summanden ist entweder ein Teil von ungerade, wodurch die Erwartung , oder alle sind gerade, wodurch es . Stellen Sie sich vor, Sie ersetzen alle durch Gaussian . Dann wären wir in einem ähnlichen Szenario: ungerade würde geben , und alle geraden würden das Produkt mindestens . So dominiert der Gaußsche Fall Begriff für Begriff den Bernoulli-Fall. Somit,rj01XiGirj0rj 1

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

Aber durch Stabilität des Gaußschen wird ist selbst ein Gaußscher mit der Standardabweichung , also kennen wir seine Momente! Somit ist unser ter Moment begrenzt durch (Ungefähr ); Dies ist als Khintchines Ungleichung bekannt. Dann,2i|ai|Gia2ta2tt!/(2t/2(t/2)!)a2ttt/2

Pr[|iaiXi|>λ]<2O(t)λta2ttt/2
Setze für eine ausreichend große Konstante und Sie erhalten den Gaußschen Schwanz gebundenen . Ich habe diesen Beweis für Khintchines Ungleichheit zum ersten Mal gehört, als ich mit Daniel Kane gesprochen habe, aber wahrscheinlich gibt es einen älteren Hinweis. Beachten Sie, dass der Beweis auch deutlich macht, welche Unabhängigkeitsebene unter den Sie benötigen, um verschiedene Endgrenzen zu erhalten.t=λ2/(Ca22)Cexp(Ω(λ2/a22))Xi
Jelani Nelson
quelle
6

Minc vermutete und Brégman bewies, dass, wenn eine 0-1-Matrix mit 1 in Zeile , die bleibende von höchstens Es gibt einen kurzen Beweis in Alons und Spencers Lehrbuch The Probabilistic Method , aber wahrscheinlich ist der "Buch" Beweis Jaikumar Radhakrishnans Beweis unter Verwendung von Entropie ( J. Combin. Theory Ser. A 77 (1997), 161-164). Aus der Aussage des Ergebnisses ist keineswegs ersichtlich, dass der Begriff der Entropie hier unter der Oberfläche liegt.AriiA

i(ri!)1/ri.
Timothy Chow
quelle