Erdős und die probabilistische Methode: Existenz durch Zufall beweisen
Paul Erdős hatte kein Zuhause, keinen Beruf im gewöhnlichen Sinn und fast keinen Besitz. Er verbrachte sein Leben damit, mit einem Koffer zwischen Universitäten zu reisen, mit den Worten "mein Gehirn ist offen" auf der Türschwelle eines Kollegen aufzutauchen und einen Strom von Sätzen und ungelösten Problemen zu hinterlassen, an denen Mathematiker bis heute arbeiten. Unter allem, was er schuf, sticht eine Idee hervor, weil sie veränderte, wie Beweise überhaupt geführt werden. Sie heißt probabilistische Methode, und in ihrem Kern steckt ein Zug, der fast wie Schummeln klingt: zu beweisen, dass etwas existiert, indem man sich weigert, es zu bauen.
Die Frage: Wann ist Ordnung unausweichlich?
Beginnen wir mit einem einfach klingenden Rätsel. Auf einer Party mit sechs Personen sind je zwei entweder Freunde oder Fremde. Es stellt sich heraus, dass man unter je sechs Personen immer drei findet, die alle gegenseitig befreundet sind, oder drei, die alle gegenseitig fremd sind. Ordnung drängt sich auf. Der Zweig der Mathematik, der untersucht, wann das geschehen muss, ist die Ramsey-Theorie, und sie hängt der Frage eine Zahl an.
Ramseys Satz garantiert, dass diese Zahlen existieren, aber er sagt nicht, wie groß sie sind. Die naheliegende Anschlussfrage lautet: Wie groß kann eine Gruppe werden und dabei jeden einfarbigen Cluster der Größe k vermeiden? Diese Frage zu beantworten bedeutet, die Existenz einer solchen cleveren Färbung zu beweisen. Und genau hier wird es aussichtslos, eine von Hand zu bauen, denn die Zahl der möglichen Färbungen ist astronomisch.
Erdős's Zug: Nicht bauen, abzählen
Erdős's Einsicht von 1947 bestand darin, nicht länger zu versuchen, eine gute Färbung zu entwerfen, sondern stattdessen vollständig zufällig zu färben und dann die Arithmetik die Arbeit machen zu lassen. Das Argument ist kurz genug, um es vollständig zu verfolgen.
Färbe jede Verbindung durch einen Münzwurf
Nimm n Personen und betrachte das vollständige Netzwerk, in dem jedes Paar durch eine Kante verbunden ist. Färbe jede Kante unabhängig zufällig, rot oder blau, jeweils mit Wahrscheinlichkeit ein Halb. Keine Cleverness, kein Entwurf. Nur eine faire Münze für jede einzelne Kante.
Miss, wie wahrscheinlich es ist, dass eine Gruppe einfarbig ist
Fixiere irgendeine bestimmte Menge von k Personen. Unter ihnen gibt es C(k,2) Kanten, das sind k(k-1)/2 Verbindungen. Dass all diese Kanten eine einzige Farbe teilen, ist unwahrscheinlich: Die Wahrscheinlichkeit ist 2 × (1/2)^C(k,2), da es zwei Farben gibt und jeder der C(k,2) Münzwürfe übereinstimmen muss. Nenne diese kleine Zahl p.
Addiere die erwartete Zahl schlechter Gruppen
Es gibt C(n,k) verschiedene Gruppen von k Personen, um die man sich sorgen muss. Nach der Linearität des Erwartungswerts ist die erwartete Zahl vollständig einfarbiger Gruppen einfach die Anzahl der Gruppen mal der Wahrscheinlichkeit für jede einzelne: C(n,k) × 2 × (1/2)^C(k,2). Dieser eine Ausdruck erfasst im Durchschnitt, wie viele einfarbige Cluster eine zufällige Färbung enthalten wird.
Liegt der Durchschnitt unter 1, muss eine makellose Färbung existieren
Wähle nun n ungefähr gleich 2^(k/2). Mit dieser Wahl ergibt die obige erwartete Zahl einen Wert kleiner als 1. Aber eine Abzählung tatsächlicher einfarbiger Gruppen ist eine ganze Zahl, und wenn der Durchschnitt über alle Färbungen unter 1 liegt, dann muss mindestens eine Färbung den Wert 0 erreichen. Diese Färbung hat überhaupt keine einfarbige Gruppe der Größe k. Daher ist R(k,k) größer als n, was etwa 2^(k/2) ist.
Lies diesen letzten Schritt noch einmal, denn er ist die ganze Magie. Wir haben nie eine gute Färbung hergestellt. Wir haben nie eine beschrieben. Wir haben gezeigt, dass die durchschnittliche Färbung so nah an makellos ist, dass eine perfekte irgendwo im Stapel existieren muss. Der Beweis reicht dir Gewissheit über ein bestimmtes Objekt, ohne auf irgendein bestimmtes Objekt zu zeigen.
Warum das revolutionär war
Vor Erdős bedeutete der Beweis, dass etwas existiert, fast immer, es zu konstruieren, oder zumindest ein Verfahren zu beschreiben, das es täte. Die probabilistische Methode brach diese Erwartung. Sie etablierte, dass der Zufall selbst als Beweis dienen kann: Wenn ein zufälliger Versuch mit irgendeiner Wahrscheinlichkeit über null gelingt, ist Erfolg möglich, Punkt.
Dieser nichtkonstruktive Charakter stellt das Argument in dieselbe Familie wie einige der elegantesten Ergebnisse der Mathematik. Cantors Diagonalargument beweist ebenfalls die Existenz von etwas, einer Zahl, die in jeder Liste fehlt, durch reine logische Kraft statt durch explizite Konstruktion. Beide teilen jene stille, fast beunruhigende Macht: Die Schlussfolgerung ist wasserdicht, obwohl sie einem nie das Ding zeigt, das sie verspricht. Der Zufall hier ruht auf denselben Grundlagen, die in Wahrscheinlichkeit intuitiv verstehen behandelt werden, wo die Idee eines Erwartungswerts, der Motor von Schritt drei, von Grund auf aufgebaut wird.
Die Erdős-Probleme und ihr KI-Moment
Erdős bewies nicht nur Sätze. Er stellte Probleme, hunderte davon, oft versehen mit kleinen Geldpreisen, die von ein paar Dollar für eine knifflige Aufgabe bis zu Tausenden für eine Frage reichten, die er für wirklich tief hielt. Viele dieser Probleme sind noch offen, und sie wurden sorgfältig katalogisiert und werden gepflegt auf erdosproblems.com.
Das Zen daran
Die probabilistische Methode ist aus demselben Grund schön wie ein guter Zaubertrick: Man beobachtet jeden Schritt, man findet die Stelle nicht, an der man getäuscht wurde, und dennoch fühlt sich das Ergebnis unmöglich an. Es gibt keinen Taschenspielertrick. Der Erwartungswert liegt wirklich unter eins, und eine ganze Zahl unter ihrem eigenen Durchschnitt muss wirklich irgendwo auf null absinken. Die Gewissheit ist total, die Konstruktion fehlt, und beide Dinge sind zugleich wahr.
Das ist die bleibende Lehre, die Erdős hinterließ. Existenz und Konstruktion sind nicht dasselbe. Manchmal ist der sauberste Weg, zu wissen, dass irgendwo ein perfektes Objekt existiert, zu beweisen, dass das durchschnittliche Objekt fast perfekt ist, und die Lücke den Rest erledigen zu lassen. Für ein weiteres Ergebnis, bei dem eine einzige Zeile Ideen verknüpft, die unverbunden scheinen, bietet Eulers Identität die entgegengesetzte Art von Schönheit: Wo Erdős Existenz aus dem Abzählen heraufbeschwört, fixiert Euler eine genaue und unvermeidliche Zahl.
Häufige Fragen
- Was ist die probabilistische Methode?
- Sie ist eine Art zu beweisen, dass ein Objekt mit einer bestimmten Eigenschaft existiert, ohne das Objekt direkt zu konstruieren. Man baut eine zufällige Version der Sache, zeigt, dass die Wahrscheinlichkeit für die gewünschte Eigenschaft größer als null ist, und folgert, dass mindestens ein solches Objekt existieren muss. Paul Erdős hat die Technik begründet, und sie ist heute ein zentrales Werkzeug in der Kombinatorik und der Informatik.
- Was hat Erdős damit bewiesen?
- Sein wegweisendes Ergebnis von 1947 lieferte eine untere Schranke für Ramsey-Zahlen: Er zeigte, dass die diagonale Ramsey-Zahl R(k,k) größer ist als 2^(k/2). Im Klartext: Es gibt Möglichkeiten, die Verbindungen in einem großen Netzwerk mit zwei Farben zu färben, sodass keine große Gruppe vollständig in einer einzigen Farbe verbunden ist. Er bewies die Existenz dieser Färbungen, ohne je eine vorzuweisen, allein durch Abzählen.
- Wie kann man die Existenz von etwas beweisen, ohne es zu bauen?
- Über Durchschnitte. Wenn man ein Objekt zufällig wählt und die erwartete Zahl seiner Mängel berechnet, und diese erwartete Zahl unter 1 liegt, dann muss mindestens ein Objekt im Pool null Mängel haben. Eine zufällige Wahl, deren durchschnittliche Mängelzahl kleiner als eins ist, garantiert, dass irgendwo in der Sammlung ein perfektes Beispiel sitzt, auch wenn das Argument nie auf das konkrete zeigt.
- Was ist eine Ramsey-Zahl?
- Die Ramsey-Zahl R(k,k) ist die kleinste Gruppengröße, die Ordnung erzwingt, egal wie man die Dinge anordnet. Konkret ist R(k,k) die kleinste Anzahl von Personen, sodass man, wie auch immer man jedes Paar in Freunde oder Fremde einteilt, garantiert eine Gruppe von k Personen findet, die alle gegenseitig befreundet oder alle gegenseitig fremd sind. Ramseys Satz besagt, dass diese Zahlen existieren; Erdős's Methode zeigt, dass sie sehr schnell wachsen.
- Warum ist die probabilistische Methode heute wichtig?
- Sie machte den Zufall zu einer Beweistechnik, und diese Idee durchzieht heute Kombinatorik, Algorithmenentwurf, Codierungstheorie und theoretische Informatik. Viele Ergebnisse über Netzwerke und Algorithmen werden noch immer bewiesen, indem man zeigt, dass eine zufällige Konstruktion mit positiver Wahrscheinlichkeit funktioniert. Die Methode ist auch der Grund, warum ein großer Teil von Erdős's eigenen Problemen aktive Forschungsziele bleibt.
Hat dir das Durchdenken Spaß gemacht?
Math Zen macht aus dieser Intuition tägliche Übung, mit adaptiven Aufgaben zu 24 Mathethemen.
