EIG034 Vier Farben, Vier Samples
Thomas Kahle
Manchmal gibt es kuriose Zufälle in der Mathematik. Es gibt z.B. genauso viele binäre Bäume mit n Knoten, wie es nxn-rechts-oben Pfade ohne Überquerung der Diagonalen gibt. Ist das jetzt Zufall, oder steckt da was dahinter? In diesem Fall steckt tatsächlich was dahinter, deswegen gehe ich noch einen Schritt weiter und vergleiche den berühmten Vierfarbsatz mit dem weniger berühmten Vier-Sample-Satz aus der algebraischen Statistik. Da muss doch was dahinter stecken?
* Catalan-Vermutung
* Catalan-Zahlen in der OEIS
* Vierfarbsatz
* Formal proof of the four color theorem (pdf)
* Heawood-Karte (Satz von Ringel-Youngs)
* Graphical Models
* Maximum-Likelihood-Schätzung
* The Maximum-Likelihood-Threshold of a graph (arXiv)
* Maximum-Likelihood-Thresholds via graph rigidity (arXiv)
* Snapshots of Modern Mathematics from Oberwolfach
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Automatisch generiertes Transkript (nicht geprüft)
6, 3, 6, 0, 7, 6, 0, 8 Hallo zusammen. Ich begrüße euch im Eigenraum. Schön, dass ihr wieder eingeschaltet habt. Schon wieder eine neue Folge. Es geht jetzt ein bisschen schneller. Ich habe in meinen Statistiken gesehen, dass die
durchschnittliche Zeit, die zwischen Folgen vergeht, wenn man jetzt also alle Folgen
nimmt vom Eigenraum, die ist mittlerweile 17 Tage,
aber bei den letzten Folgen war es ja ein bisschen weniger und diesmal ist es
auch ein bisschen weniger und nächste Woche ist auch schon wieder eine Aufnahme
geplant, aber ob ich diese Frequenz jetzt halten kann, wenn die,
Live-Shows, manche nennen sie auch Vorlesungen, dann bald wieder losgehen,
ja, das ist ein bisschen zweifelhaft.
Aber ich will euch heute eine etwas kuriose Sache berichten.
Zwei tolle Sätze, die eine interessante Parallele haben.
Und ich habe auch ein bisschen über Zufall in der Mathematik nachgedacht.
Wenn man so eine Parallele zwischen verschiedenen Tatsachen in der Mathematik entdeckt,
dann steckt ja da meistens irgendwas dahinter, was man dann erst Jahre oder
Jahrhunderte oder Jahrtausende später entdeckt.
Es gibt zum Beispiel die Katalan-Zahlen. Das ist eine ganz berühmte Zahlenfolge aus der Kombinatorik.
Catalan war ein belgischer Mathematiker im 19. Jahrhundert. Heißt so,
verschiedene Sachen, die sind nach dem benannt.
Also der ist recht bekannt durch Dinge, die nach ihm heißen.
Zum Beispiel die Catalan-Vermutung ist relativ bekannt.
Ja, bin jetzt schon wieder auf einer Tangente, aber diese Catalan-Vermutung,
die sagt eben, dass wenn man 2 hoch 3 nimmt und 3 hoch 2, also 2 hoch 3 ist ja 8 und 3 hoch 2 ist 9.
Und die zwei Ausdrücke unterscheiden sich jetzt um genau eins. Stimmt's?
So, die Katalan-Vermutung fragt nun, gibt es auch noch irgendwelche anderen Ausdrücke?
Einfach natürliche Zahl hoch natürliche Zahl minus natürliche Zahl hoch natürliche
Zahl, das können vier verschiedene Zahlen sein, gleich 1. Also wir wissen 2
hoch 3 und 3 hoch 2 unterscheiden sich um 1.
Aber könnte man jetzt auch 4 hoch 7 und 7 hoch 4 oder 4 hoch 7 und 2 hoch 9
oder irgendwie 4 Zahlen,
die eine hoch die andere minus die dritte hoch die vierte soll 1 ergeben.
Kann man das irgendwie noch lösen mit natürlichen Zahlen?
Und das kann man nicht. Also die Katalan-Vermutung war, es geht nur mit 2 hoch 3 und 3 hoch 2.
Und das war vom Mitte des 19. Jahrhunderts bis ins 21.
Jahrhundert offen. Ist aber jetzt bewiesen. Also es stimmt. 2 hoch 3 und 3 hoch
2 ist die einzige Lösung für diese Frage. Frage.
Okay. Und auch nach Katalan benannt sind die Katalan-Zahlen.
Und da komme ich jetzt wieder zurück zu dem Zufall, Zufällen in der Mathematik.
Die Katalan-Zahlen sind Folge 108 in der OEIS.
Und das sind vielleicht die Zahlen, die am häufigsten in der Kombinatorik auftauchen.
Man kann die ganz einfach definieren, wenn man weiß, was Binomialkoeffizienten sind.
Dann nimmt man einfach den Binomialkoeffizient 2n choose n, also 2n über n,
würde man auf Deutsch sagen.
Die Anzahl Möglichkeiten aus 2n Dingen...
N Dinge auszuwählen, also die Anzahlmöglichkeiten, die Hälfte einer geraden
Anzahl von Elementen auszuwählen.
Und das muss man dann auch durch n plus 1 teilen. Und wenn man das macht,
kriegt man die n-te Katalanzahl raus.
Also die n-te Katalanzahl ist 1 durch n plus 1 und dann der Binomialkoeffizient 2n über n.
Okay, denkt man halt, irgend so ein Binomialkoeffizient, habe ich ja in Kombinatorik,
kommt das ja immer mal vor, man
zählt irgendwas ab und dann kriegt man ein Binomialkoeffizient raus. raus.
Aber diese Zahlenfolge ist die, die wahrscheinlich den längsten Eintrag in der OES hat.
Also in der Online-Enzyklopädie der ganzheitlichen Folgen gibt es ja immer zu
jeder Folge so Erklärungen, wo die auftaucht.
Und diese Katalan-Zahlen sind die, die am häufigsten auftauchen in der Kombinatorik.
Ich sage euch mal zwei Sachen. Zum Beispiel, wenn man abzählen will,
wie viele binäre Bäume mit Endknoten gibt es.
Also ein binärer Baum, das taucht in der Informatik relativ häufig auf, so eine Datenstruktur.
Man fängt oben an mit einem Knoten und dann geht es nach links und nach rechts
runter und dann sind da wieder Knoten, jeweils links einer und rechts einer.
Binär, weil es so zwei Abzweigungen gibt. Und an jedem von den Knoten kann man
wieder links-rechts abzweigen und links-rechts abzweigen und irgendwo kann es auch mal enden.
Also an irgendwelchen kann man vielleicht nur rechts abzweigen und links nicht und so weiter.
Und dann fragt man sich, wie viele Möglichkeiten gibt es, das so zu machen,
dass am Ende n Knoten herauskommen.
Und wenn man da alle Knoten zählt, also auch die, die in den mittleren Ebenen
sind, dann fragt man sich, wie viele solche Binärbäume gibt's und da kommt genau
die Katalan-Zahl heraus.
Okay, das war die erste Erklärung und die zweite Erklärung ist,
man nimmt sich Karopapier, so wie man es aus der Schule kennt,
und malt sich ein Quadrat der Größe n kreuz n hin.
Für irgendein n, sagen wir mal 5. Und dann malt man noch die Diagonale ein von dem Quadrat.
Und jetzt will man entlang der Linien des Karopapiers einen Pfad zeichnen,
der in dem Quadrat von links unten nach rechts oben geht und die Diagonale nicht überquert.
Okay? Also wenn ich jetzt links unten meinen Stift ansetze, dann muss ich erstmal
nach rechts, weil wenn ich nach oben gehen würde, wäre ich ja schon überhalb
der Diagonalen. Dann muss ich nach rechts. Ein Feld.
Und jetzt bin ich noch 4 Felder von dem rechten Rand entfernt und 5 Felder von dem oberen Rand.
Und jetzt könnte ich entweder nach oben gehen, dann bin ich wieder auf der Diagonalen
oder ich könnte nochmal nach rechts gehen.
Und dann habe ich eben verschiedene Möglichkeiten, solche Pfade zu zeichnen,
die niemals wieder runter gehen, sondern die immer nur nach rechts oder nach
oben gehen und dann irgendwann bei der rechten oberen Ecke ankommen sollen.
Also wenn ich an den rechten Rand stoße, dann muss ich ab da immer hoch gehen.
Also ich soll niemals wieder runter gehen und ich muss an der rechten oberen Ecke ankommen.
Und wenn ich die Anzahl der Pfade bestimme, dann kommt man auch auf diese Katalanzahl.
So, und nicht nur das, jetzt gibt es in OEIS findet er jetzt 200 solche Dinge,
die irgendwie durch Katalan-Zahlen abgezählt werden.
Und ist das jetzt ein Zufall oder gibt es da irgendwelche Beziehungen?
Und ein Teilgebiet der Kombinatorik ist diese Beziehung zu finden.
Also gibt es jetzt eine direkte Beziehung, die einem zeigt, dass die Anzahl
der Binärbäume mit n Knoten das gleiche ist,
wie die Anzahl der Pfade in diesem n Kreuz, n Quadrat, die immer nur rechts
oder hoch gehen und die Diagonale nicht überqueren.
Also kann man eindeutig den Binärbäumen diese Pfade zuordnen und umgekehrt.
Wenn sie die gleiche Anzahl haben, deutet das ja irgendwie darauf hin,
dass es diese Zuordnung vielleicht gibt.
Und das ist eben ein Teilgebiet der Kombinatorik. Und die Mathematik,
würde ich sagen, die hat so ein Gespür für solchen Zufall.
Also da ist schon so eine Art Denke, das kann doch kein Zufall sein.
Also wenn man sowas beobachtet, denkt man eigentlich, das kann kein Zufall sein.
Und von einem solchen kuriosen Zusammenhang, einer kuriosen Duplizität der Bedingungen
will ich heute mal erzählen.
Und das sind meine zwei Sätze, um die es heute geht. Der erste ist ziemlich
bekannt. Das ist nämlich der Vier-Farbsatz.
Der sagt, dass wenn man eine Landkarte hat, zum Beispiel die Karte von Deutschland, Europa,
eine Weltkarte, also so eine 2D-Zeichnung von Ländern und Grenzen,
dass man die immer mit vier Farben so ausmalen kann, dass nie zwei benachbarte
Länder die gleiche Farbe haben.
Also nehmt euch mal eine Ausmahlkarte von Europa und dann malt ihr Deutschland
an, sagen wir mit, was ist eine gute Farbe für Deutschland? Pink.
Und dann müsst ihr Polen anmalen, da geht jetzt nicht Pink, weil zwei benachbarte
Länder sollen nicht die gleiche Farbe haben. Also nehmt ihr für Polen, sagen wir, Lila.
Und dann kommt Tschechien dran, das braucht jetzt eine andere Farbe als Polen
und eine andere Farbe als Deutschland, weil das ja beides Nachbarländer sind,
dann kriegt das, sagen wir mal, Grün.
Jetzt haben wir schon drei verschiedene Farben verbraucht. Und jetzt kommt,
wenn wir weiter rumgehen, Österreich.
Und da wäre aber dann wieder Lila, also die Farbe von Polen möglich.
Weil Österreich ja keine Grenze mit Polen hat.
Und wenn Österreich eine Grenze mit Polen hätte, also wenn wir die Karte mal
gedanklich verändern würden, sodass dann Tschechien umschlossen ist von Österreich
und Polen und es da eine Grenze geben würde, dann könnten Österreich und Polen
nicht die gleichen Farben haben.
Dann würden wir jetzt für Österreich unsere vierte Farbe verbrauchen.
Und jetzt könnte man auf die Idee kommen, na, wenn ich jetzt bei der Schweiz
bin, dann bräuchte ich jetzt bestimmt schon eine fünfte Farbe,
wenn diese Grenze da ist, aber naja, die Polenfarbe ist ja dann trotzdem wieder frei.
Und dann kann man das ja mal ausprobieren, wenn man jetzt versucht,
aber ich soll auch nicht die Polenfarbe haben, also male ich es dann noch wieder
dran, aber dann wäre ja die Tschechienfarbe wieder frei und so weiter und so fort.
Und man stellt ziemlich schnell fest, wenn man damit rumexperimentiert,
dass vier Farben immer genügen, aber beweisen, beweisen, beweisen,
beweisen, Das war richtig schwer.
Und gut, diese ganze Geschichte will ich jetzt hier nicht unbedingt in ihrer
vollen Länge wiedergeben.
Dieser Satz wurde erst in den 1970er Jahren bewiesen und war einer der ersten
Computerbeweise oder überhaupt der erste Computerbeweis.
Also man hat auf Papier das reduziert auf eine riesengroße Fallunterscheidung
und Apple und Haken haben Mitte der 70er Jahre diese Fallunterscheidung,
die Reduktion auf die Fallunterscheidung und dann diese Fallunterscheidung mit
dem Computer ausgeführt.
Und mittlerweile gibt es auch so einen formalisierten Beweis davon,
also einen Beweis, der komplett durch den Computer geführt und überprüft wird,
wo alle Teile, auch die, die vorher keine Computerberechnungen waren,
formalisiert wurden, sodass sie jetzt vom Computer überprüft werden können.
Früher, in den 70ern, war das eine kuriose Debatte.
Also da wurde intensiv diskutiert, ob dieser Beweis,
wir reduzieren das erst auf Papier, auf tausende von Fällen und diese tausenden
von Fällen, die können wir dann mit einem Computerprogramm nachprüfen,
ob das überhaupt ein Beweis ist,
weil man dem Computer in dem Sinne nicht traut, dass der einen Beweis führen kann.
Heutzutage, würde ich sagen, ist die Denke eigentlich andersrum. Also ich persönlich,
ich traue den Computern mehr als den Menschen, weil, naja, man kann es eben
auf verschiedener Hardware ausprobieren und man kann die Programme gut überprüfen
und Menschen machen eigentlich ziemlich viele Fehler, vor allen Dingen bei Beweisen.
Und vor allen Dingen, wenn sie sowas sagen, es genügt, die folgenden 2000 Fälle
zu betrachten, dann haben die einen bestimmten Fall vergessen.
Aber jedenfalls, Apple und Haken haben keinen Fall vergessen,
weil auch der Teil, der reduziert auf diese Fälle, die dann überprüft werden
müssen, der ist mittlerweile auch so aufgeschrieben in so einer Formalisierung,
dass dann mit dem Computer überprüft werden kann.
Der Satz gilt übrigens auch für Karten auf der Sphäre, ist also auf die Erde anwendbar.
Und wie Mathematikerinnen und Mathematiker immer so sind, fragen sich dann natürlich
auch so Fragen, wie gilt der auch auf dem Donut?
Also wenn die Erde jetzt keine Erde wäre, sondern ein Donut mit so einem Loch
in der Mitte, dann könnte man sich auch vorstellen, dass irgendwie die Donut
wird besiedelt und dann gibt es ja so Länder und die machen ihre Grenzen.
So sind die Menschen halt, machen immer Grenzen. und dann geht es aber nicht
mehr. Dann reichen vier Farben nicht aus.
Also es hängt irgendwie damit zusammen, dass die Erde eine Kugel ist und die
Erdoberfläche eine Sphäre.
Wenn wir auf einem Donut leben würden, bräuchte man mindestens sieben Farben.
Ist auch schon sehr lange bekannt.
Eine Karte von Hewitt, die sogenannte Hewitt-Karte und Hewitt-Färbung,
zeigt, dass man auf dem Donut mindestens sieben Farben braucht.
Okay. Und wenn ihr diesen Satz in der Mathematik irgendwo hört,
in eurer Mathematikvorlesung, dann kommt er meistens in eine Grafentheorie dran
und wird da so formuliert, jeder planare Graph kann mit höchstens vier Farben gefärbt werden.
Und da findet noch so eine kleine Transformation statt. Also man benutzt das
Konzept der Grafentheorie, von der ja auch hier im Podcast schon öfter die Rede
war, also die Theorie der durch Kanten verbundenen Punkte.
Und so ein Graph heißt Planar, wenn man ihn in die Ebene zeichnen kann,
sodass sich die Kanten nicht kreuzen.
Also völlig überschneidungsfrei. Ich male die Punkte in die Ebene und male dann
die Verbindungslinien.
Die müssen nicht gerade sein, die können krumm sein, aber sie dürfen sich eben nicht kreuzen.
Und dann kann man sehen, dass man zum Beispiel jeden Graphen mit höchstens vier
Knoten planar einbetten kann, in die Ebene zeichnen kann,
aber mit fünf Knoten, sechs Knoten und mehr Knoten gibt es eben Graphen,
für die es einfach nicht möglich ist.
Das liegt an dem Graphen. Wenn Sie zum Beispiel alle Kanten haben,
der Graphen mit fünf Ecken oder fünf Punkten,
man nennt die Punkte Ecken, und allen möglichen Kanten, den fünf über zwei Kanten,
die da möglich sind, gleich 10, der ist nicht planar. So, und...
Jetzt macht man für seine Landkarte, macht man einfach einen Punkt für jedes
Land und eine Kante zwischen zwei Punkten, die zu Ländern gehören,
wenn die beiden Länder eine gemeinsame Grenze haben.
Dann dürfen sie nämlich nicht die gleiche Farbe haben im Ausmalen und bei der
Färbung von Graphen fragt man sich eben, kann man die Ecken,
die Punkte in dem Graphen so färben, dass zwei, die durch eine Kante verbunden
sind, nicht die gleiche Farbe haben.
Das nennt man dann eine Färbung des Graphen. Und dann sagt der Satz,
jeder planare Graph kann mit höchstens vier Farben gefärbt werden,
in Klammern, sodass nie zwei benachbarte Punkte die gleiche Farbe haben.
Und so ein Graph, der von einer Landkarte kommt, der ist immer planar.
Wenn ich die Punkte in die Mitten der Länder mache, dann kann ich immer die
Kanten einfach über die gemeinsame Grenze zeichnen und bekomme so einen planaren Graphen.
Und die Abstraktion ist eben, dass man diesen Satz für planare Graphen formuliert.
So, das war der erste Satz, der Vier-Farb-Satz. Und jetzt kommen wir zum zweiten
Satz, dem Vier-Sample-Satz.
Der Vier-Sample-Satz ist, ich muss es zugeben, deutlich weniger bekannt.
Ihr werdet ihn jetzt, glaube ich, bisher noch nicht auf Wikipedia finden.
Könnte natürlich sein, dass ihr es jetzt irgendwie später nachhört und dann
wurde er schon hinzugefügt, aber als ich es jetzt aufnehme, ist er noch nicht auf Wikipedia.
Genau genommen, naja, man könnte sagen, ich versuche, diesen Namen zu etablieren.
Jedenfalls sagt dieser Satz, wenn man ein gaussisches grafisches Modell hat,
das zu einem planaren Graphen gehört.
Dann genügen vier Samples, vier Datenpunkte, damit der Maximum-Likelihood-Schätzer existiert.
Mit Wahrscheinlichkeit 1, klein gedrucktes. Es gibt noch klein gedrucktes.
Ich sage mal, dann genügen vier Samples, um Maximum-Likelihood-Schätzung zu machen.
So, jetzt muss ich da ein bisschen drüber reden. Das ist ein Satz aus der algebraischen
Statistik, einem modernen Gebiet, in dem Algebra und diskrete Mathematik auf
Statistik angewendet werden.
Also in einem ganz anderen Gebiet als der Grafentheorie.
Und diese gaussischen grafischen Modelle sind eines der wichtigsten Tools der Statistik.
Also Gauss ist in diesem Fall, bezieht sich das auf die Normalverteilung,
die Gauss'sche Glockenkurve, in diesem Fall in mehreren Variablen.
Aber das ist eigentlich die häufigste Modellannahme, die man für reellwertige
Zufallsvariablen, sowie Messdaten von irgendwelchen Wetterstationen oder was
auch immer man in der Physik oder Modellierung misst, macht.
Also es ist eine sehr verbreitete Modellannahme, dass man diese Gauss'schen Zufallsvariablen hat.
Und grafische Modelle geben einem jetzt Informationen darüber oder Modellierungsmöglichkeiten
für die Abhängigkeiten zwischen den Variablen.
Also in der Statistik geht es ja irgendwie immer darum, herauszufinden,
ob bestimmte Dinge etwas miteinander zu tun haben.
Also wenn ich das Medikament nehme, verbessert sich dann mein Gesundheitszustand
oder beendet sich die Krankheit.
Ja, und da sind irgendwie zufällige Fluktuationen, weil das Medikament bei jedem
ein bisschen anders wirkt, aber gibt es einen Zusammenhang zwischen der Variable,
hat Medikament genommen,
hat Medikament nicht genommen und dem Verlauf der Krankheit,
die auch als eine Variable modelliert wird.
Oder wenn man zum Beispiel Wetter- oder Klimamodelle macht, dann wären die Zufallsvariablen
die einzelnen Messstationen, an denen wir Daten bekommen,
so viel hat es geregnet und an denen wir Vorhersagen machen wollen, so viel wird es regnen.
Und da hat man vielleicht ein paar tausend davon auf der ganzen Erde und da
gibt es sicher Abhängigkeiten zwischen dem Wetter in Kassel und dem Wetter in
Göttingen, weil die sind ja ziemlich nah aneinander,
aber es gibt wahrscheinlich wenig Abhängigkeiten zwischen dem Wetter in Kassel
und dem Wetter in Karachi in Pakistan,
weil es eben sehr weit weg ist und die Physik irgendwie lokal wirkt.
Und sowas modelliert man dann zum Beispiel mit einem Graphen,
indem man die Punkte, die Ecken in dem Graphen als die Zufallsvariablen nimmt
und die Zusammenhänge durch Kanten modelliert.
Und dann im übertragenen Sinne bedeutet Verbundenheit in dem Graphen,
dass eine Abhängigkeit besteht und Unabhängigkeit zwischen den Zufallsvariablen
wird durch Nichtverbundenheit oder lange Wege ausgedrückt.
So, um den Satz zu verstehen, brauchen wir auch noch die Maximum-Likelihood-Schätzung
als auch so ein Kernprinzip der Statistik. Ich versuche mich mal an einer ganz kurzen Erklärung.
Also, was ist eigentlich der Unterschied zwischen Statistik und Wahrscheinlichkeitstheorie?
Ich sage das immer so. Also Wahrscheinlichkeitstheorie ist, man kennt den Zufall,
der Fachterminus dafür ist die Verteilung, also man kennt den zufallserzeugenden
Prozess sehr genau, so genau wie man nur möchte und möchte jetzt Vorhersagen machen,
wie die Daten aussehen, die von diesem zufälligen Prozess erzeugt werden.
Das ist Wahrscheinlichkeitstheorie.
Statistik hingegen ist das Umkehrproblem. Man kennt die Daten,
man hat Daten, man hat was gemessen und will Aussagen darüber machen,
was für Eigenschaften hat der zugrunde liegende Zufall.
Also man misst das Wetter und will Aussagen darüber machen, was geht in dem
Wettermodell vor sich, wie sind die Parameter.
Und ja, das ist der große Bereich der parametrischen Statistik.
Der wählt nun irgendwelche Parameter und will diese Parameter bestimmen aus Daten.
Und diese Maximum-Likelihood-Schätzung ist die, würde ich mal sagen,
populärste Methode der Daten.
Parametrische Statistik. Und die sagt, wähle deine Parameter so,
dass die Daten, die du wirklich beobachtet hast, die höchste Wahrscheinlichkeit haben.
Also ich beobachte echte Daten und wenn ich meine Parameter jetzt irgendwie
verschieden wähle, kann ich ja immerhin mit Hilfe von Wahrscheinlichkeitstheorien
mit der Operation, Ich kenne den Zufall und bestimme Eigenschaften der Daten.
Ausrechnen, wie wahrscheinlich wäre es denn, so hypothetisch,
wenn die Parameter so wären, wie wahrscheinlich wäre es dann,
meine echten Daten zu sehen.
Und wenn die Parameter so wären, wie wäre es dann wahrscheinlich?
Und dann nehme ich die Parameter, sodass meine echten Daten die höchste Wahrscheinlichkeit hätten.
Ja, ist so ein Optimierungsproblem. Also so führt man eben Statistik auf ein
Optimierungsproblem zurück. Und da gibt es halt viel Forschung.
Und naja, Optimierungsproblem haben wir in der Schule schon gelöst.
Also Maximum finden will, Abblattung 0 setzen und dann die Gleichung lösen.
Okay, das ist eine andere lange Geschichte. Da geht ihr mal lieber in eine Statistikvorlesung,
statt euch sowas in einem Podcast mitzunehmen. Klingt irgendwie gefährlich.
Und ich sage jetzt nochmal den 4-Sample-Satz.
Also wenn man so ein gaussisches grafisches Modell hat und der Graph,
der die Abhängigkeit modelliert, ist planar.
Das hat jetzt nichts mit Landkarten zu tun. Sondern ich habe ein grafisches
Modell und der Graph ist planar.
Dann genügen vier Sample, um die Maximum-Likelihood-Schätzung zu machen.
Also der technische Ausdruck wäre, wenn man vier Sample hat,
existiert der Maximum-Likelihood-Schätzer mit Wahrscheinlichkeit 1.
Und das ist kurios oder interessant, weil es gar nicht davon abhängt,
wie viele Variablen man betrachtet.
Also ob ich jetzt auf meiner Erde 100 Wetterstationen habe oder 10.000,
es genügen immer 4 Sample.
Weil in meinem Wettermodell mache ich vielleicht so ein quadratisches Gitter
auf die Erde, wo jede Station mit den 4 Nachbarn, die am nächsten sind, verbunden ist.
Und dann habe ich eben ein grafisches Modell eines planaren Graphen,
weil so ein Gitter sich so eben planar um den Erdball legt und dann genügen vier Sample.
Egal wie viele Messstationen ich habe.
Kurios, oder? Und das ist eben sehr praktisch, weil man in der Statistik oft
Situationen hat, wo man sehr viele Variablen hat und jeder Datenpunkt sehr teuer
ist und dann will man natürlich, dass die Methode funktioniert,
auch wenn man nur sehr wenige Datenpunkte hat.
Und der Beweis dieses Satzes, ich verliere mich in technischen Details,
aber der ist wirklich kurios, der jagt einen so richtig durch mehrere Gebiete der Mathematik.
Denn erst wird dieses Problem, diese Anzahl Sample zu finden,
sodass der Maximum-Light-Due-Schätzer existiert,
wird erst auf so ein Matrix-Vervollständigungs-Problem zurückgeführt.
Man brechen nämlich aus den Daten die sogenannte Sample Covariance Matrix,
also die empirische Covariance Matrix, genau so heißt es.
Und dann ist man mit der Aufgabe konfrontiert, die zu vervollständigen.
Also man nimmt dann nur die Einträge, die zu den Kanten von dem Graphen gehören
und muss dann eine positiv definierte Matrix finden, die die vervollständigt.
Okay, und dieses Matrix-Vervollständigungsproblem, also erstmal erste Umformulierung,
man macht es irgendwie in so ein Problem über Matrizen, klingt erstmal gut,
weil über Matrizen wissen wir auch sehr viel. Aber das Problem ist immer noch zu schwer.
Deswegen wird das in eine sogenannte Starrheitstheorie, auf Englisch Rigidity Theory übersetzt.
Und da geht es um so die Theorie von irgendwelchen Dingen, wenn ich aus Stangen
was baue, die durch so bewegliche Gelenke verbunden sind, wird das dann starr.
Also, wieder ein ganz anderes Problem. Und das Kuriose ist jetzt,
dass der planare Graph von dem grafischen Modell, den wir am Anfang hatten,
der wird dann als dreidimensionaler Polyeder aufgefasst, also der Graph sind
genau die Kanten von einem Polyeder in drei Dimensionen und das wird dann mit
Starrheitstheorie untersucht und so gibt es dann eine Verbindung und man kommt auf diese vier Samples.
Also es ist wirklich kurios, der Podcast ist jetzt ein bisschen zu kurz,
um das völlig auszuführen.
Das habe ich kürzlich mal zusammen mit Carlos Amendola von der TU Berlin aufgeschrieben
und das wird irgendwann erscheinen in einem Snapshot of Modern Mathematics vom Oberwolfach.
Und das ist ja übrigens eine sehr gute Reihe, ich verlinke euch das mal,
in der so ja, Mathematik erklärt wird und das wird aber noch editiert,
damit ihr es besser lesen könnt.
Das wird von Leuten, die richtig so verstehen, wie man was erklären muss,
damit die Leute das gut lesen können. Und na, da weise ich dann noch mal drauf hin.
So, ist es noch jemand dran geblieben? Also wir haben diese zwei Sätze,
den Vierfarbsatz, der sagt, wenn ich einen planaren Graphen habe,
habe, dann reichen vier Farben aus, um den einzufärben.
Und den Vier-Sample-Satz, der sagt, wenn ich einen planaren Graphen habe,
dann reichen vier Sample, um Maximum-Likelihood-Schätzung im grafischen Modell zu machen.
Und man hat diese kuriose Parallele, dass man jedes Mal das Planarität zu dieser Vier führt.
Aber es sind natürlich völlig unterschiedliche.
Gebiete der Mathematik und es sind auch völlig unterschiedliche Vieren.
Also das eine, da geht es um Färbung und bei dem anderen geht es um Anzahl Datenpunkte
in dem statistischen Verfahren.
Und ich stelle jetzt hier diese
Herausforderung, die Verbindung zwischen diesen zwei Sätzen aufzutun.
Also das würde mich wirklich interessieren und wenn das zu meinen Lebzeiten
noch passiert, wäre ich gelinde gesagt überrascht.
Und Und ja, so denkt man manchmal nach über, ist es Zufall oder ist es kein Zufall?
Und wenn man so ein bisschen in mathematischen Vorträgen ist und sich die Diskussionen
zu sowas anhört, dann gibt es da eine schöne Formulierung auf Englisch und die sagt,
also stellt euch vor, es kommt so ein Vortrag und plötzlich tauchen dort Planare,
Graphen oder eine 4 auf und im zweiten Teil des Vortrags tauchen Planare, Graphen oder eine 4 auf.
Und die Vortragende wird dann gefragt, huch, besteht denn da ein direkter Zusammenhang?
Das ist ja kurios, zweimal hier planare Graphen und eine 4.
Und dann könnte sie zum Beispiel sagen, das sei by accident.
Also im Englischen, wenn man vermutet, dass es keinen direkten Zusammenhang
gibt, dann sagt man, es sei ein Unfall. Und die Denkweise ist,
in der Mathematik steckt eigentlich immer was dahinter.
Und wenn nichts dahinter steckt, dann ist es eigentlich ein Unfall.
Und ich weiß es nicht, ist der Vierfarbsatz parallel zum Viersamplesatz ein
Unfall oder steckt da mehr dahinter?
So, also, da könnt ihr ja mal ein bisschen drüber nachdenken oder auch nicht, wie euch das gefällt.
Wo ihr jedenfalls keine Wahl habt, ist, dass ihr auch beim nächsten Mal wieder
einschaltet, hier beim Eigenraum.
Mich würde es sehr freuen. Und bis dahin, abonniert den Podcast,
folgt auf Mastodon, diskutiert mit und erzählt weiter.
Bis zum nächsten Mal. Tschüss.
