Beweise, die eine tiefere Struktur zeigen

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.

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.

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.$\Sigma_2^p$$\exists\forall$$\exists$$\forall$

$\sum_i a_iX_i$$\pm 1$ $X_i$ t ≥ $\sigma = \|a\|_2$$t \ge 2$

$$\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*}$$

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,$r_j$$0$$1$$X_i$$G_i$$r_j$$0$$r_j$ $1$

$$\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]$$

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,$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}$

$$\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}$$ 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 = \lambda^2 / (C\cdot \|a\|_2^2)$$C$$\mathrm{exp}(-\Omega(\lambda^2 / \|a\|_2^2))$$X_i$

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.$A$$r_i$$i$$A$

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