Ganz herzlich willkommen zu diesem Video zum sogenannten Banach'schen
Streichholzproblem.
Der berühmte Mathematiker Stefan Banach, nach ihm ist zum Beispiel der
Banachraum benannt, war ein starker Raucher.
Einer Anekdote zufolge steckte er sich in jede Hosentasche eine
Schachtel mit jeweils N Streichhölzern.
Immer bevor er sich eine Zigarette anzündete, ließ er eine faire Münze
darüber entscheiden, aus welcher Hosentasche er eine Schachtel zog und
daraus einen Streichholz nahm.
Nach dem Anzünden der Zigarette steckte er die Schachtel wieder zurück
in die Hosentasche und zwar tat er das so lange, wie er noch ein
Streichholz vorgefunden hatte.
Irgendwann zog er jedoch eine Schachtel aus der Tasche und diese
Schachtel war leer.
Die Frage ist, mit welcher Wahrscheinlichkeit sind in der anderen
Schachtel noch genau J Streichhölzer?
Im folgenden sei b2n die Anzahl der Streichhölzer in der anderen
Schachtel, wenn eine Schachtel als leer entdeckt wird.
Der Buchstabe b steht natürlich für Banach.
Uns interessiert die Wahrscheinlichkeit, dass b2n den Wert j annimmt.
Dabei kann j jeden Wert von 0 bis n annehmen.
Der Wert 0 ist möglich, weil auch eine leere Schachtel zurück in die
Hosentasche wandert, wenn man ihr das letzte Streichholz entnommen
hat, und der Wert n tritt auf, wenn man n plus 1 mal hintereinander in
die gleiche Schachtel gegriffen hat.
Natürlich gibt es viele andere Einkleidungen des gleichen
mathematischen Problems.
So könnten etwa zwei Behälter mit jeweils n Objekten vorliegen, was
immer diese Objekte sind.
Greift man wiederholt und unabhängig voneinander in jeweils einen
Behälter und entnimmt ein Objekt, so findet man irgendwann einen
Behälter leer vor.
Dann bezeichnet die Zufallsgröße b2n die Anzahl der Objekte, die noch
im anderen Behälter vorhanden sind.
Ich bleibe jedoch im Folgenden bei Banach und den Streichhölzern.
Man sieht hier eine horizontale Halbachse und eine vertikale Achse,
die mit x bzw.
y beschriftet sind.
Die äquidistante Einteilung ist ein Vielfaches von 1.
Dabei läuft y von –n bis n und x von 0 bis 2n.
Wir veranschaulichen das Herausnehmen von Streichhölzern aus den
beiden Hosentaschen mithilfe von Polygonzügen, die im Folgenden auch
als Wege bezeichnet werden.
Ein Griff in die rechte Hosentasche und Entnahme eines Streichholzes
kennzeichnen wir durch einen blau markierten Aufwärtsschritt, das
Herausnehmen eines Streichholzes aus der linken Hosentasche als rot
markierten Abwärtsschritt.
Wenn die beiden nächsten Griffe in die rechte Hosentasche waren, so
schließen sich hier zwei Aufwärtsschritte an.
Auf der x-Achse sieht man also, wie viele Streichhölzer insgesamt
entnommen wurden.
Ich mache einmal diesen Anfang eines Polygonzuges weg und zeichne in
einem Winkel von 45° zur x-Achse einen Pfeil.
Entlang dieses Pfeils können wir im Laufe des gesamten Stochastischen
Vorgangs ablesen, wie viele Streichhölzer noch in der rechten
Hosentasche vorhanden sind.
Man sieht hier, am Anfang sind es n, wenn man auf der y-Achse die Höhe
1 erreicht hat, sind es noch n-1 und so weiter.
Entsprechend kann man entlang dieses Pfeils entnehmen, wie viele
Streichhölzer noch in der linken Hosentasche sind.
Wir starten jetzt den Stochastischen Vorgang und sehen zu, was Banach
macht.
Der erste Griff ging also in die rechte Hosentasche, der zweite in die
linke, der dritte und der vierte wieder in die rechte und der fünfte
in die linke Tasche.
Sehen wir uns einmal an, wie sich das Ganze weiterentwickelt.
Aha!
Nach den letzten drei Aufwärtsschritten sind keine Streichhölzer mehr
in der rechten Hosentasche vorhanden.
Wir haben also einen Punkt erreicht, bei dem die Schachtel in der
rechten Hosentasche leer ist.
Es wurde also nach der Entnahme des letzten Streichholzes eine leere
Schachtel zurückgesteckt.
Mal sehen, was Banach macht.
Wenn er jetzt wieder in die rechte Hosentasche greift, würde er
merken, dass kein Streichholz mehr in der Schachtel ist.
Er greift aber in die linke Hosentasche.
Beim nächsten Mal greift er aber in die rechte Tasche und stellt fest,
dass die darin befindliche Schachtel leer ist.
Wir lesen jetzt ab, wie viele Streichhölzer noch in der anderen
Schachtel sind und das seien j Stück.
Dabei kann j jeden Wert von 0 bis n annehmen.
Wenn Banach z.B.
zuerst n-mal hintereinander in die rechte und danach n-mal
hintereinander in die linke Tasche gegriffen hätte, hätte es diesen
Weg hier gegeben, der so verläuft und von hier oben dann darunter
geht.
Wir wären in diesem Punkt angekommen.
Und ganz egal, in welche Hosentasche danach gegriffen wird, es sind
keine Streichhölzer mehr da.
Die Gesamtanzahl an Streichhölzern, die entnommen wurde, ist 2n-j,
denn die Schachtel mit den n Streichhölzern in der rechten Hosentasche
wurde komplett geleert und es wurden n-j Streichhölzer aus der linken
Tasche entnommen, da noch j vorhanden sind.
Wir wollen ja die Wahrscheinlichkeit bestimmen, dass bei Auffinden
einer leeren Schachtel in der anderen Schachtel noch j Streichhölzer
sind.
Das passiert auf jeden Fall dann, wenn wir vom Startpunkt her kommend
in diesem Punkt hier landen und danach in die rechte Hosentasche
greifen.
Wir zählen zunächst einmal die Anzahl der verschiedenen Wege, die vom
Startpunkt aus in diesem Punkt ankommen.
Jeder dieser Wege weist insgesamt 2n-j Schritte auf, von denen genau n
Schritte Aufwärtsschritte sind.
Wenn ich die Ticks auf der x-Achse als Zeitpunkte deute, so liegt bei
dem dargestellten Weg zum Zeitpunkt 0, also hier, ein Aufwärtsschritt
vor, zum Zeitpunkt 1 ein Abwärtsschritt, zum Zeitpunkt 2 ein
Aufwärtsschritt und so weiter.
Zu guter Letzt gibt es zum Zeitpunkt 2n-j-1, also hier, einen
Abwärtsschritt.
Ein Weg ist also dadurch festgelegt, dass man von den insgesamt 2n-j
-Zeitpunkten 0, 1, 2 und so weiter bis 2n-j-1 diejenigen auswählt, zu
denen ein Aufwärtsschritt stattfinden soll.
Zu den anderen Zeitpunkten finden dann die Abwärtsschritte statt.
Die Anzahl der Möglichkeiten, aus 2n-j-Objekten hier den Zeitpunkten n
Objekte auszuwählen, ist der Binomialkoeffizient 2n-j über n.
Es gibt aber auch noch eine andere Möglichkeit, dass bei Auffinden
einer leeren Schachtel in der anderen Schachtel noch j Streichhölzer
sind, nämlich dass man solch einen Weg durchlaufen hat und dann kein
Streichholz mehr in der linken Tasche hat, aber das noch nicht sofort
merkt, weil man noch einmal in die rechte Tasche greift, also noch
einen Aufwärtsschritt macht.
Wenn man aber dann, was mit Wahrscheinlichkeit ein Halb passiert, in
die linke Tasche greift, ich deute das durch diesen Pfeil an, hat man
in der rechten Tasche noch j Streichhölzer.
Man beachte, dass ich den ersten Weg einfach an der x-Achse gespiegelt
und die Farben blau und rot vertauscht habe.
Aus Symmetriegründen gibt es also genauso viele Wege, die vom
Startpunkt aus in diesem Punkt ankommen, wie Wege, die vom Startpunkt
aus im dazu spiegelbildlich gelegenen Punkt ankommen, also auch 2n-j
über n Stück.
Wir können jetzt die gesuchte Wahrscheinlichkeit, dass b2n den Wert j
annimmt, hinschreiben.
Wegen der Spiegelsymmetrie an der x-Achse erhalten wir zunächst den
Faktor 2.
Jeder konkrete Weg, der vom Startpunkt aus in diesem Punkt hier
ankommt, hat aber die gleiche Wahrscheinlichkeit, denn ich schreibe ja
eine konkrete Folge der Länge 2n-j von Schrittrichtungen vor und die
Richtungen erfolgen unabhängig voneinander mit gleicher
Wahrscheinlichkeit ein Halb.
Jeder Weg hat also die gleiche Wahrscheinlichkeit ein Halb hoch 2n-j
und da wir die Anzahl der Wege schon bestimmt haben, ergibt sich
dieser Faktor.
Was wir jetzt nicht vergessen dürfen ist, dass wir ganz zum Schluss
noch einen Aufwärtsschritt wählen müssen, was mit Wahrscheinlichkeit
ein Halb passiert.
Das liefert uns noch diesen Faktor.
Jetzt kann man noch 2 gegen ein Halb kürzen und erhält das zentrale
Resultat dieses Videos, das ich als Satz formuliere.
Teil a des Satzes bezieht sich unmittelbar auf die Verteilung von b2n
und den Beweis dafür haben wir schon geführt.
Aussage b besagt, dass der Erwartungswert von b2n durch diesen
Ausdruck gegeben ist.
Aussage c ist ein Grenzwertsatz für den Erwartungswert.
Wenn wir den Erwartungswert von b2n durch die Wurzel aus 2n teilen, so
konvergiert dieser Quotient gegen die Wurzel aus 2 durch Pi und das
ist etwas kleiner als 0,8.
Zu guter Letzt sei noch ein etwas komplizierterer Ausdruck für die
Varianz von b2n angegeben.
Das Interessante ist, dass wir den Beweis von b, c und d hier nicht
führen müssen, weil nämlich b2n die gleiche Verteilung besitzt wie
eine Zufallsgröße n2n, die die Anzahl der Nullstellen einer
symmetrischen Irrfahrt der Länge 2n auf den ganzen Zahlen beschreibt.
Hierzu habe ich ein eigenes Video gemacht und in diesem Video bin ich
auf die Teile b, c und d eingegangen.
Was mich persönlich interessiert, ist eine begriffliche Einsicht,
warum b2n und n2n die gleiche Verteilung besitzen.
Wer da eine zündende Idee hat, möge mich bitte kontaktieren.
Die folgende Einsicht zeigt, dass wir Teil a des Satzes auch schneller
zeigen können.
Wir deuten einen Griff in die rechte bzw.
linke Hosentasche als Treffer bzw.
Niete.
Dann liegen beim Banachschen-Streichholz-Problem unabhängige Bernoulli
-Versuche mit gleicher Trefferwahrscheinlichkeit ein Halb vor.
Was besagt denn das Ereignis b2n gleich j im Sinne dieser Deutung von
Bernoulli -Versuchen?
Es tritt genau dann ein, wenn ich entweder vor dem n plus ersten
Treffer n minus j Nieten erzielt habe oder vor der n plus ersten Niete
genau n minus j Treffer.
Der n plus erste Treffer entspricht ja gerade dem n plus ersten Griff
in die rechte Hosentasche mit der nachfolgenden Erkenntnis, dass die
Schachtel leer ist und dann sind noch genau j Streichhölzer in der
anderen Schachtel, wenn ich vorher n minus j Nieten erzielt habe.
Diese erzielten Nieten entsprechen gerade den entnommenen
Streichhölzern aus der anderen Schachtel.
Ganz analog verhält es sich mit der n plus ersten Niete.
Ich deute die Situation einmal hier mit Sternen und einer 1 am Ende
an.
Die 1 entspricht einem Treffer und Nullen stehen für Nieten.
Wenn jeder Stern für einen Bernoulli-Versuch steht, muss, damit die 1
am Ende der n plus erste Treffer ist und vor diesem Treffer n minus j
Nieten auftreten, unter diesen Sternen n mal eine 1 und n minus j mal
eine 0 auftreten.
Insgesamt sind das zwei n minus j Sterne und es gibt zwei n minus j
über n Möglichkeiten, davon n als Einsen zu deklarieren.
Das ist genau der Binomialkoeffizient im Teil a des Satzes.
Da die Wahrscheinlichkeit für eine konkrete Ergebnisfolge der Länge 2n
minus j plus 1 gleich ein Halb hoch 2n minus j plus 1 ist und wir noch
den gleichwahrscheinlichen zweiten Fall betrachten müssen, dass vor
der n plus ersten Niete n minus j Treffer auftreten, haben wir Teil a
gezeigt.
Ich gebe abschließend einmal für den handelsüblichen Fall von 38
Streichhölzern pro Schachtel das Stabdiagramm der Verteilung der
Anzahl verbleibender Streichhölzer in der anderen Schachtel an, wenn
eine Schachtel leer angetroffen wird.
Interessanterweise sind die beiden Wahrscheinlichkeiten für die Fälle
j gleich 0, d.h.
die andere Schachtel ist auch leer und j gleich 1, d.h.
die andere Schachtel enthält noch genau ein Streichholz gleich groß
und danach fallen die Wahrscheinlichkeiten ab.
Wenn man hier ein wenig rechnet, stellt man fest, dass die
Wahrscheinlichkeit, dass sich, wenn eine Schachtel als leer entdeckt
wird, in der anderen Schachtel noch höchstens 5 Streichhölzer
befinden, etwas über 52% beträgt.
Der Erwartungswert der Anzahl restlicher Streichhölzer in der anderen
Schachtel ist etwas größer als 6.
Diese Aussage steht nicht im Widerspruch zu der davor, die ja besagt,
dass man getrost darauf wetten kann, dass bei Antreffen einer leeren
Schachtel in der anderen nur höchstens 5 Streichhölzer sind.
Ich bedanke mich ganz herzlich für das Anschauen des Videos.
Wem dieses Video gefallen hat, der kann es ja sehr gerne weiterempfehlen.