:This-Artikel ist 'nicht über interaktive Probesysteme, die Wahrscheinlichkeit verwenden, um einen verifier zu überzeugen, dass ein Beweis, noch über probabilistic Algorithmen richtig ist, die die richtige Antwort mit der hohen Wahrscheinlichkeit, aber nicht mit der Gewissheit, noch über Methoden von Monte Carlo geben, die Simulationen sind, die sich auf die Pseudozufälligkeit verlassen.

Die probabilistic Methode ist eine nichtkonstruktive Methode, die in erster Linie in combinatorics verwendet ist, und hat durch Paul Erdős den Weg gebahnt, für die Existenz einer vorgeschriebenen Art des mathematischen Gegenstands zu beweisen. Es arbeitet durch die Vertretung, dass, wenn man zufällig Gegenstände aus einer angegebenen Klasse wählt, die Wahrscheinlichkeit, dass das Ergebnis der vorgeschriebenen Art ist, mehr ist als Null. Obwohl der Beweis Wahrscheinlichkeit verwendet, wird der Endbeschluss sicher ohne jeden möglichen Fehler bestimmt.

Diese Methode ist jetzt auf andere Gebiete der Mathematik wie Zahlentheorie, geradlinige Algebra und echte Analyse, angewandt worden

sowie in der Informatik (z.B randomized das Runden).

Einführung

Wenn jeder Gegenstand in einer Sammlung von Gegenständen scheitert, ein bestimmtes Eigentum zu haben, dann ist die Wahrscheinlichkeit, dass ein zufälliger aus der Sammlung gewählter Gegenstand dieses Eigentum hat, Null. Wenn es das umdreht, wenn die Wahrscheinlichkeit, dass der zufällige Gegenstand das Eigentum hat, größer ist als Null dann beweist das die Existenz von mindestens einem Gegenstand in der Sammlung, die das Eigentum hat. Es ist egal, wenn die Wahrscheinlichkeit klein vanishingly ist; jede positive Wahrscheinlichkeit wird tun.

Ähnlich zeigend, dass die Wahrscheinlichkeit (ausschließlich) ist, kann weniger als 1 verwendet werden, um die Existenz eines Gegenstands zu beweisen, der die vorgeschriebenen Eigenschaften nicht befriedigt.

Eine andere Weise, die probabilistic Methode zu verwenden, ist durch das Rechnen des erwarteten Werts einer zufälligen Variable. Wenn es gezeigt werden kann, dass die zufällige Variable einen Wert weniger übernehmen kann als der erwartete Wert, beweist das, dass die zufällige Variable auch einen Wert übernehmen kann, der größer ist als der erwartete Wert.

Allgemeine in der probabilistic Methode verwendete Werkzeuge schließen die Ungleichheit von Markov ein, der Chernoff, hat und Lovász lokales Lemma gebunden.

Zwei Beispiele wegen Erdős

Obwohl andere vor ihm Lehrsätze über die probabilistic Methode bewiesen haben (zum Beispiel, das 1943-Ergebnis von Szele, dass dort Turniere bestehen, die eine Vielzahl von Zyklen von Hamiltonian enthalten), viele der weithin bekanntsten Beweise mit dieser Methode sind wegen Erdős. Das erste Beispiel beschreibt unten ein solches Ergebnis von 1947, der einen Beweis eines niedrigeren gibt, der für den Ramsey Nummer R (r, r) gebunden ist.

Das erste Beispiel

Nehmen Sie an, dass wir einen ganzen Graphen auf n Scheitelpunkten haben. Wir möchten zeigen (für kleine genug Werte von n), dass es möglich ist sich zu färben, die Ränder des Graphen in zwei Farben (sagen Sie rot und blau), so dass es keinen ganzen Subgraphen auf r Scheitelpunkten gibt, der monochromatisch ist (jeder Rand hat dieselbe Farbe gefärbt).

Um so zu tun, färben wir den Graphen zufällig. Färben Sie jeden Rand unabhängig mit der Wahrscheinlichkeit 1/2, rot zu sein, und 1/2, blau zu sein. Wir berechnen die erwartete Zahl von monochromatischen Subgraphen auf r Scheitelpunkten wie folgt:

Für jeden Satz S r Scheitelpunkte von unserem Graphen, definieren Sie die Variable X (S), um 1 zu sein, wenn jeder Rand unter den r Scheitelpunkten dieselbe Farbe, und 0 sonst ist. Bemerken Sie, dass die Zahl von monochromatischen R-Subgraphen die Summe X (S) über alle möglichen Teilmengen ist. Für jeden S ist der erwartete Wert von X (S) einfach die Wahrscheinlichkeit, dass alle Ränder in S dieselbe Farbe, sind

(der Faktor 2 kommt, weil es zwei mögliche Farben gibt).

Das hält für einigen der C für wahr (n, r) mögliche Teilmengen könnten wir gewählt haben, so haben wir das, ist die Summe von E [X (S)] über den ganzen S

Die Summe einer Erwartung ist die Erwartung der Summe (unabhängig davon, ob die Variablen unabhängig sind), so ist die Erwartung der Summe (die erwartete Zahl von monochromatischen R-Subgraphen)

Denken Sie, was geschieht, wenn dieser Wert weniger als 1 ist. Die Zahl von monochromatischen R-Subgraphen in unserem zufälligen Färben wird immer eine ganze Zahl sein, so muss das mindestens ein Färben weniger haben als der erwartete Wert. Aber die einzige ganze Zahl, die dieses Kriterium befriedigt, ist 0. So, wenn

etwas Färben passt unser gewünschtes Kriterium, so definitionsgemäß R (r, r) muss größer sein als n. Insbesondere R (r, r) muss mindestens exponential mit r wachsen.

Eine Besonderheit dieses Arguments ist, dass es völlig nichtkonstruktiv ist. Wenn auch es (zum Beispiel) beweist, dass fast jedes Färben des ganzen Graphen auf (1.1) Scheitelpunkte keinen monochromatischen R-Subgraphen enthalten, führt es kein ausführliches Beispiel solch eines Färbens an. Das Problem, solch ein Färben zu finden, ist seit mehr als 50 Jahren offen gewesen.

Das zweite Beispiel

Eine 1959-Zeitung von Erdős (sieh Verweisung, die unten zitiert ist), hat das folgende Problem in der Graph-Theorie gerichtet: In Anbetracht positiver ganzer Zahlen g und k, besteht wirklich dort ein Graph G, nur Zyklen der Länge mindestens g, solch enthaltend, dass die chromatische Zahl von G mindestens k ist?

Es kann gezeigt werden, dass solch ein Graph für jeden g und k besteht, und der Beweis vernünftig einfach ist. Lassen Sie n sehr groß sein und einen zufälligen Graphen G auf n Scheitelpunkten zu denken, wo jeder Rand in G mit der Wahrscheinlichkeit p=n besteht. Es kann gezeigt werden, dass mit der positiven Wahrscheinlichkeit die folgenden zwei Eigenschaften halten:

• G enthält an den meisten n/2 Zyklen der Länge weniger als g.

Beweis. Lassen Sie X die Zahl-Zyklen der Länge weniger sein als g. Die Zahl von Zyklen der Länge i im ganzen Graphen auf n Scheitelpunkten ist, und jeder von ihnen ist in G mit der Wahrscheinlichkeit anwesend. Folglich durch die Ungleichheit von Markov haben wir

:.

• G enthält keinen unabhängigen Satz der Größe.

Beweis. Lassen Sie Y die Größe des größten unabhängigen Satzes in G sein. Klar haben wir

wenn.

Hier kommt der Trick: Da G diese zwei Eigenschaften hat, können wir an den meisten n/2 Scheitelpunkten von G umziehen, um einen neuen Graphen G' auf n Scheitelpunkten zu erhalten, der nur Zyklen der Länge mindestens g enthält. Wir können sehen, dass dieser neue Graph keinen unabhängigen Satz der Größe hat. Folglich hat G chromatische Zahl mindestens k, weil chromatische Zahl tiefer durch die 'Zahl von Scheitelpunkten/Größe des größten unabhängigen Satzes' begrenzt wird.

Dieses Ergebnis gibt einen Hinweis betreffs, warum die Berechnung der chromatischen Zahl eines Graphen so schwierig ist: Selbst wenn es keine lokalen Gründe (wie kleine Zyklen) für einen Graphen gibt, um viele Farben zu verlangen, kann die chromatische Zahl noch willkürlich groß sein.

Siehe auch

• Zufälliger Graph
• Beweise von Probabilistic von non-probabilistic Lehrsätzen
• Methode von bedingten Wahrscheinlichkeiten
• Interaktives Probesystem
• Alon, Noga; Spencer, Joel H. (2000). Die probabilistic Methode (2ed). New York: Wiley-Zwischenwissenschaft. Internationale Standardbuchnummer 0-471-37046-0.
• J. Matoušek, J. Vondrak. Die Probabilistic Methode. Vortrag-Zeichen.
• Alon, N und Krivelevich, M (2006). Extremal und Probabilistic Combinatorics