Math SemesterberDOI 10.1007/s00591-014-0132-6

M AT H E M AT I K I N D E R L E H R E

Alte Geburtstagsprobleme – neu gelöst

Gerd Riehl

Eingegangen: 31. Oktober 2013 / Angenommen: 19. Februar 2014© Springer-Verlag Berlin Heidelberg 2014

Zusammenfassung Während das „klassische“ Geburtstagsproblem, nämlich dieWahrscheinlichkeit zu berechnen, dass mindestens zwei von n zufällig ausgewähltenPersonen denselben Geburtstag haben, relativ leicht lösbar ist, erweist sich die Verall-gemeinerung auf „mindestens s Personen“ (mit s > 2) als schwerer zugänglich undmit wachsendem n sehr rechenaufwändig. Es werden einige frühere Lösungsansätzefür die Fälle s = 3 bzw. s ≥ 3 dargestellt und die bei ihrer Umsetzung aufgetrete-nen Schwierigkeiten analysiert. Anschließend wird gezeigt, wie sich diese Problememit einem neuen Algorithmus vermeiden lassen, mit dem Gruppengrößen bis übern = 100 in kürzester Zeit bearbeitet werden können.

1 Einleitung

Im Jahr 1990 hat Georg Schrage [6] unter dem Titel „Ein Geburtstagsproblem“ un-tersucht, wie wahrscheinlich es ist, dass unter 15 Personen mindestens drei am selbenTag Geburtstag haben (ein Ereignis, das an seinem Institut an der Universität Dort-mund tatsächlich eingetreten war). Dieser 1992 in Stochastik in der Schule nachge-druckte Aufsatz war Anlass zu weiteren Beiträgen, 2002 von Rottmann [5], der dieVerallgemeinerung des Problems auf mehr als drei gemeinsame Geburtstage betrach-tet, und 2006 vom Verfasser dieses Beitrags [4], der einen alternativen Lösungswegeinschlug.

Durch zwei Aufsätze von Barth und Haller [1, 2] wurde kürzlich in Erinnerung ge-rufen, dass bereits 1939 Richard v. Mises [3] das Problem des Dreifach-Geburtstagsuntersucht, aber nicht vollständig gelöst hat. Ausgehend von seinem Beispiel werdenim folgenden Abschn. 2 die allmählichen Fortschritte bei der theoretischen Behand-lung des Problems dargestellt, aber auch die Schwierigkeiten, die bei der praktischenDurchführung der erforderlichen Rechnungen auftreten. Dabei wird zugleich deut-

G. Riehl (B)Obere Mark 6, 30890 Barsinghausen, Deutschlande-mail: Gerd.Riehl@t-online.de

G. Riehl

lich, wie diese Schwierigkeiten abnehmen, wenn leistungsfähigere Rechenhilfsmittelverfügbar sind.

Den Rechenaufwand kann man aber schon durch die Wahl eines zweckmäßigenAlgorithmus vermindern, wie wir ihn im dritten Abschnitt entwickeln werden. Die-ser steht in engem Zusammenhang mit der Formel, die von Mises [3] für die sog.Besetzungswahrscheinlichkeiten aufgestellt hat.

Im vierten Abschnitt benutzen wir den neuen Algorithmus, um verschiedene Pro-bleme zu lösen, die die Verteilung von Geburtstagen bzw. in einem allgemeinen Mo-dell die Aufteilung von Kugeln auf eine bestimmte Zahl von Fächern zum Inhalthaben. Dabei wird auch gezeigt, wie man eine weitere Beschleunigung der Berech-nungen erreicht, indem man sehr kleine Wahrscheinlichkeiten vernachlässigt, diebei einer exakten Lösung einen Großteil der erforderlichen Rechnungen beanspru-chen würden. Trotz dieser bewusst in Kauf genommenen Ungenauigkeit bleibt dieKontrolle über die Größe des dabei auftretenden Fehlers stets erhalten.

Wir behandeln die verschiedenen Geburtstagsprobleme mithilfe des Kugel-Fächer-Modells, d. h. wir modellieren die Abfrage des Geburtstags jeder der n Per-sonen einer Gruppe durch die zufällige Wahl eines von z = 365 Fächern, in das einevon n Kugeln gelegt wird. Die stochastische Situation wird dabei insofern idealisiert,als alle Tage des Jahres als gleichwahrscheinlich behandelt werden; unberücksich-tigt bleiben dabei Sonderfälle wie an einem 29. Februar geborene Personen odermöglicherweise in der befragten Gruppe vorhandene Zwillinge.

Es sei an dieser Stelle darauf hingewiesen, dass – über die aus didaktischen Grün-den naheliegende Einkleidung als Geburtstagsproblem hinaus – Fragestellungen be-züglich der Verteilung von n Kugeln auf z Fächer auch allgemein von Interesse sind,so in der Maxwell-Boltzmann-Statistik der Physik, wie schon von Mises ([3], S. 146)erwähnt.

Die Anzahl der bei der zufälligen Verteilung von n Kugeln auf z Fächer in ein be-stimmtes Fach gelangten Kugeln nennen wir b, die größte dieser Belegungszahlen m.Dieser Wert stellt die Realisierung der Zufallsvariablen Maximalbelegung dar, die imFolgenden mit M bezeichnet wird. Das hier interessierende Ereignis „mindestens s

Personen haben denselben Geburtstag“ lässt sich dann kurz als „M ≥ s“ schreiben.Das Ergebnis der Aufteilung kann man in einem (m+1)-tupel x = [x0;x1; . . . xm]

erfassen, dessen Koordinaten xb angeben, in wie vielen Fächern genau b Kugelnliegen. Es gelten dann also die Formeln

m∑

b=0

xb = z (1)

undm∑

b=0

b · xb = n. (2)

Beispiel 1 Acht Kugeln sollen auf sechs Fächer so aufgeteilt werden, dass eines ein-fach, zwei doppelt und eines dreifach belegt ist; zwei Fächer bleiben also leer (nach[1], S. 22). Abbildung 1 zeigt links eine mögliche Belegung der Fächer; ordnet mandie Fächer nach der Größe b ihrer Belegung an (Abb. 1 rechts), dann lässt sich daszugehörige (m + 1)-tupel unmittelbar ablesen: x = [2;1;2;1].

Alte Geburtstagsprobleme – neu gelöst

Abb. 1 Mögliche Aufteilungfür Beispiel 1 und Anordnungder 6 Fächer nach ihrerBelegungszahl b

Im folgenden Abschnitt verwenden wir bei der Darstellung früherer Untersuchun-gen und Ergebnisse statt der sehr unterschiedlichen Bezeichnungen der jeweiligenAutoren einheitlich die oben eingeführten Bezeichnungen.

2 Ein historischer Rückblick

2.1 Erste Lösungsversuche

Wir folgen in diesem Abschnitt der Darstellung von Barth und Haller [1]; dort findensich auch (mit etwas anderen Bezeichnungen) die Herleitungen der Formeln (3) und(4), die wir hier im Folgenden nur mitteilen. Auch werden bereits einige Ergebnisseangegeben, die mit den in Abschn. 4 noch zu entwickelnden Methoden gewonnenwurden.

Die vermutlich erste Erwähnung eines Geburtstagsproblems findet sich in der Ein-leitung des 1939 erschienenen Aufsatzes „Über Aufteilungs- und Besetzungswahr-scheinlichkeiten“ von Richard v. Mises [3]. Dieser erwähnt die als „sehr ungewöhnli-ches, seltenes Zusammentreffen“ charakterisierte Beobachtung, dass von den 60 An-gestellten eines Versicherungsbüros drei am selben Kalendertag Geburtstag hatten.Zwar geht er auf die Frage nach der Wahrscheinlichkeit dieses Ereignisses nicht wei-ter ein, stellt aber in seiner Arbeit mit der von ihm eingeführten Besetzungswahr-scheinlichkeit ein Hilfsmittel bereit, das es zumindest theoretisch ermöglicht, seinGeburtstagsproblem zu lösen.

Mit Besetzung bezeichnet v. Mises die Gesamtheit aller Aufteilungen von n Ku-geln auf z Fächer, bei denen genau xb Fächer mit genau b Kugeln belegt sind. Die-ses Ereignis haben wir oben mit dem (m + 1)-tupel x beschrieben; jedes solche(m + 1)-tupel stellt die Realisierung einer Zufallsvariablen Besetzung dar, die wirmit X bezeichnen.

Die Wahrscheinlichkeit für das Auftreten einer bestimmten Besetzung x bei zufäl-liger Aufteilung der n Kugeln nennt v. Mises ihre Besetzungswahrscheinlichkeit. Umdiese zu berechnen, geht er vom Laplace-Ansatz aus und bestimmt, wie viele der ins-gesamt zn möglichen Aufteilungen die Besetzung x liefern. Für diese Besetzungszahlgilt

N(x) = n!∏mb=0 b!xb

· z!∏mb=0 xb! . (3)

Beispiel 2 Für x = [2;1;2;1] aus Beispiel 1 ergeben sich mit n = 8, z = 6, undM = 3

8!0!2 · 1!1 · 2!2 · 3!1 · 6!

2! · 1! · 2! · 1! = 302 400

G. Riehl

für die Besetzung x günstige Fälle; bei insgesamt zn = 68 = 1 679 616 mögli-chen Aufteilungen erhält man damit die Besetzungswahrscheinlichkeit P(X = x) ≈0,18004.

Wie das Beispiel 2 zeigt, treten schon bei kleinen Werten von n und z im Verlaufder Rechnung sehr große Zwischenergebnisse auf, die in einer Zeit ohne elektroni-sche Rechengeräte nur schwer zu handhaben waren. Zudem stellen die Besetzungs-wahrscheinlichkeiten nur eine Teillösung der eigentlichen Aufgabe dar. Um etwa dieWahrscheinlichkeit des Ereignisses „M = 3“ zu bestimmen, müsste man alle zugehö-rigen Besetzungen ermitteln, ihre Wahrscheinlichkeiten berechnen und anschließendaddieren. Welchen Rechenaufwand dies bedeutet, wird am Beispiel des Dreifach-Geburtstags in einer Gruppe von 60 Personen deutlich: Zu „M = 3“ gehören 300verschiedene Besetzungen.

Angesichts dieser Schwierigkeiten ist es verständlich, dass v. Mises das Problemaus einer anderen Perspektive untersucht: Er betrachtet – in heutiger Terminologie– die Zufallsvariable Yb = Anzahl der Fächer mit Belegung b und bestimmt derenleicht zu berechnenden Erwartungswert

E(Yb) = 1

zb−1·(

n

b

)·(

1 − 1

z

)n−b

, (4)

der eine zutreffende Vorstellung von der Größenordnung der WahrscheinlichkeitP(M = b) gibt, allerdings nur dann, wenn E(Yb) deutlich kleiner als 1 ist, wie amEnde von Abschn. 2.2 näher erläutert werden wird.

Beispiel 3 Für v. Mises‘ Geburtstagsproblem mit n = 60, z = 365 und s = 3 er-hält man mithilfe von (4) den Erwartungswert E(Y3) ≈ 0,220. Da in diesem Wertauch Besetzungen mit M > 3 oder mit mehreren dreifach belegten Fächern erfasstsind, stellt er nur eine obere Schranke für die eigentlich gesuchte WahrscheinlichkeitP(M = 3) dar; die nur 0,198 beträgt (s. Tab. 4). Der Erwartungswert liefert aber einebrauchbare Näherung, weil 0,220 nicht zu nahe bei 1 liegt.

Es ist sinnvoll, auch die Wahrscheinlichkeiten (bzw. die Erwartungswerte) dernoch selteneren Fälle mit M > s in die Berechnung einzubeziehen. Für Beispiel 3ist dies

∑

b≥3

E(Yb) = z −2∑

b=0

E(Yb)

= 365 − 309,602 − 51,033 − 4,136

= 0,229.

Auch dieser Wert ist etwa 10 % größer als der eigentlich gesuchte Wahrscheinlichkeit,nämlich P(M ≥ 3) ≈ 0,207.

Die Grenzen der Argumentation mit dem Erwartungswert lassen sich gut am Bei-spiel des auch als „Geburtstagsparadoxon“ bezeichneten klassischen Geburtstagspro-blems mit s = 2 zeigen. Man fragt hier nach der kleinsten Gruppengröße n, bei der

Alte Geburtstagsprobleme – neu gelöst

Abb. 2 Pseudocode für den Algorithmus zur Lösung des Geburtstagsparadoxons

es günstig ist, auf mindestens einen gemeinsamen Geburtstag zu wetten, für die al-so P(M ≥ 2) > 0,5 wird. Die Bezeichnung „Geburtstagsparadoxon“ beruht auf derüberraschend kleinen, der naiven Intuition widersprechenden Lösung n = 23. Analogzu Beispiel 3 erhält man hier als Erwartungswert für zwei- oder mehrfach besetzteTage den Wert

∑

b≥2

E(Yb) = 365 − E(Y0) − E(Y1)

= 365 − 342,680 − 21,653

= 0,667,

der wesentlich näher bei 1 liegt und schon um mehr als 31 % größer als P(M ≥ 2)

ist.

Beispiel 4 Auch v. Mises geht auf das Paradoxon ein, fragt aber nach dem kleinstenn, für das der Erwartungswert E(Y2) ≥ 1 wird, und gibt als Lösung n = 29 an. Dieseinterpretiert er wie folgt: „Wer in seinem Bekanntenkreis rund 29 Geburtstage kennt,wird im Durchschnitt einen doppelt besetzten Tag finden“ ([3], S. 146). Dies ist zwarkorrekt, lässt aber keine Aussage über die genaue Verteilung von Y2 zu, insbesonderedarüber, dass man in rund 32 % der Fälle keinen mehrfach besetzten Tag zu erwartenhat.

Trotz dieser Einschränkung bleibt v. Mises das Verdienst, einen rechnerisch einfa-chen Zugang zur allgemeinen Form des Geburtstagsproblems gefunden zu haben, dergerade für die meistens interessierenden Ereignisse mit geringer Wahrscheinlichkeitgute Näherungslösungen liefert.

Eine exakte Lösung blieb für lange Zeit dem Spezialfall des Geburtstagspara-doxons vorbehalten. Als in den 70er-Jahren Taschenrechner Einzug in die Schulenhielten, wurde es zu einem Standardproblem des Stochastikunterrichts, das sich mitrelativ wenig Mühe nach dem Algorithmus von Abb. 2 lösen lässt.

Noch geringeren Arbeitsaufwand als mit einem Taschenrechner erfordert die Um-setzung des Algorithmus mithilfe einer Tabellenkalkulation (Tab. 1). Ausgehend vonden Startwerten für z, j und q (Spalte B) berechnet man zunächst mit den For-meln der while-Schleife in Abb. 2 den nächsten Wert für j bzw. q (Zellen C2und C3) und dann iterativ die weiteren Werte durch Kopieren dieser Zellen nachrechts, bis q < 0,5 wird. Dies ist erstmals für j = 23 der Fall. Die Wahrscheinlich-keit für mindestens einen gemeinsamen Geburtstag unter 23 Personen ergibt sich alsGegenwahrscheinlichkeit: P(M ≥ 2) = 1 − q ≈ 0,5073.

G. Riehl

Tab. 1 Lösung des Geburtstagsparadoxons mit Tabellenkalkulation(irrelevante Spalten ausgeblendet)

2.2 Rekursive Lösung für s = 3

Rund ein halbes Jahrhundert nach v. Mises hat Schrage [6] das Problem erneutuntersucht – ebenfalls aus Anlass einer erstaunlichen Beobachtung (ein Dreifach-Geburtstag unter den 15 Mitgliedern seines Instituts an der Universität Dortmund).

Neben einer „direkten Lösung“, die er aus kombinatorischen Überlegungen ge-winnt, gibt er auch einen Lösungsweg an, der auf einer Rekursion nach der Grup-pengröße n beruht. Er arbeitet übrigens sofort mit Wahrscheinlichkeiten und löst dasProblem über die Gegenwahrscheinlichkeit, in unserer Terminologie:

P(M ≥ 3) = 1 − P(M ≤ 2).

Für P(M ≤ 2) muss man die Wahrscheinlichkeiten aller Besetzungen x bestim-men, bei denen xb = 0 für b ≥ 3 ist. Diese bezeichnen wir kurz mit x = [x0;x1;x2],da nur die xb > 0 von Interesse sind. Bei gegebenem z und j sind alle drei Koordi-naten durch die Wahl einer einzigen (zweckmäßig ist x2) eindeutig festgelegt, es giltoffenbar

x1 = j − 2 · x2 (5)

und

x0 = z − x1 − x2 = z − j + x2. (6)

Da x1 nicht negativ sein darf, erhält man aus (5) die einschränkende Bedingung

j ≥ 2 · x2 ⇔ x2 ≤ j

2. (7)

Liegt nach j Befragungen die Besetzung x = [x0;x1;x2] vor, so kann diese aufzwei Arten aus der vorhergehenden x∗ (nach j − 1 Abfragen) entstanden sein:

• Entweder trat der an j -ter Stelle genannte Tag bisher noch nicht auf, dann war dieVorgänger-Besetzung x∗ = [x0 + 1;x1 − 1;x2].

• oder einer der bereits genau einmal aufgetretenen Tage wurde auch von der j -tenPerson genannt, dann war die Vorgänger-Besetzung x∗ = [x0;x1 + 1;x2 − 1].Die Wahrscheinlichkeit für einen Übergang von x∗ nach x beträgt demnach im

ersten Fall x0+1z

, im zweiten x1+1z

. Abbildung 3 veranschaulicht dies als Ausschnittaus einem Baumdiagramm; in den Termen für die Wahrscheinlichkeiten wurden x0und x1 mit (5) und (6) durch x2 und j ausgedrückt. Man beachte, dass die eingezeich-neten Übergänge nur möglich sind, wenn x1 > 0 oder x2 > 0 ist, da sonst x∗

0 bzw. x∗1

negativ gewesen sein müsste.Schrage selbst hat seine Berechnungen mit einem rekursiven TRUE-BASIC-

Programm durchgeführt und dabei – vermutlich ohne es zu kennen – auch v. Mi-ses‘ Problem gelöst; in seinen Beispielen ([6], S. 256) gibt er jedenfalls für den Falln = 60 die korrekte Lösung P(M > 2) = 0,207 an.

Alte Geburtstagsprobleme – neu gelöst

Abb. 3 MöglicheVorgänger-Besetzungen von[x0;x1;x2] mitÜbergangswahrscheinlichkeiten

Abb. 4 Pseudocode für den Algorithmus zur Lösung von Schrages Geburtstagsproblem

Rekursive Programme benötigen oft lange Rechenzeiten und erfordern viel Spei-cherplatz; als Abhilfe regt Schrage die Verwendung von Tabellen an, auf deren Ein-träge man zurückgreifen kann – ohne die bei rekursivem Arbeiten auftretende wie-derholte Neuberechnung derselben Werte. Statt einer rekursiven führt man dann eineiterative Berechnung durch, zwar mit denselben Formeln, aber mit einfachen Start-werten anstelle von komplizierten Randbedingungen. Abbildung 4 zeigt einen Al-gorithmus für dieses Vorgehen, der sich relativ leicht mit einer Tabellenkalkulationrealisieren lässt.

Die mit diesem Algorithmus gewonnenen Werte für Schrages Problem (n = 15),das Geburtstagsparadoxon (n = 23 bzw. bei v. Mises n = 29) sowie v. Mises’ Pro-blem (n = 60) zeigt Tab. 2. Zum Vergleich steht in Zeile 36 der ErwartungswertE(Y2).

Schrage hat das Geburtstagsproblem also um einen Schritt verallgemeinert, indemer eine Formel für P(M = 2) angab, die einfach mit Tabellenkalkulation zu realisie-ren ist und mit der auch P(M ≥ 3) dann leicht zu berechnen war. Leider kann manP(M = s) für s > 2 nicht mehr so problemlos mittels Tabellenkalkulation berechnen,weil bei einer weiteren von 0 verschiedenen Koordinate der Besetzung x die übrigenKoordinaten nicht mehr durch die Wahl einer einzelnen, etwa x3, eindeutig festgelegtsind.

G. Riehl

Tab. 2 Lösung des Problems der Dreifach-Geburtstage für verschiedene Gruppengrößen n mitTabellenkalkulation (irrelevante Spalten und Zeilen 11 bis 33 ausgeblendet)

An Tab. 2 lässt sich gut erkennen, dass P(M = 2) kleiner bleibt als v. Mises’Schätzwert E(Y2). Wir betrachten dazu den Fall n = 15 (Spalte Q); hier gilt

E(Y2) >

7∑

x2=1

x2 · q[15, x2],

denn in den Erwartungswert gehen außer den Besetzungen der Zeilen 4 bis 10 vonTab. 2 auch noch diejenigen ein, bei denen m > 2 und gleichzeitig x2 > 0 ist. Folglichist

E(Y2) − P(M = 2) >

7∑

x2=1

x2 · q[15, x2] −7∑

x2=1

q[15, x2]

=7∑

x2=1

(x2 − 1)q[15, x2] > 0.

Da der erste Summand der letzten Summe null wird, kann man die Summationauch mit x2 = 2 beginnen lassen. Wie schon in Beispiel 4 erwähnt, hängt die Güte derSchätzung von P(M = 2) durch den Erwartungswert E(Y2) wesentlich von dessenGröße ab:

• Im Fall n = 15 nehmen die Wahrscheinlichkeiten q[n,x2] schnell ab und tragendaher relativ wenig zur Differenz E(Y2) − P(M = 2) bei.

• Im Fall n = 23 (Spalte Y) ist die Wahrscheinlichkeit für mehrere Doppelge-burtstage schon deutlich größer und somit auch die letzte Summe in obigerAbschätzung.

• Ist E(Y2) ≥ 1, so kann dies wegen P(M = 2) ≤ 1 kein vernünftiger Näherungs-wert sein, wie die Fälle n = 29 und n = 60 bestätigen (Spalten AE und BJ inTab. 2).

2.3 Allgemeine Lösung

2002 hat Rottmann [5] den rekursiven Algorithmus von Schrage auf beliebige Be-setzungen x = [x0;x1; . . . xm] mit m > 2 verallgemeinert. Liegt nach j Abfragen die

Alte Geburtstagsprobleme – neu gelöst

Besetzung x vor, so findet man die als Vorgänger x∗ möglichen Besetzungen ähnlichwie oben im Fall m = 2: Ist xb (mit b > 0) positiv, dann kann von der j -ten Personein zuvor (b–1)-mal aufgetretener Tag genannt worden sein (für xb = 0 ist das nichtmöglich). Für die Vorgänger-Besetzung x∗ = [x∗

0 ;x∗1 ; . . . ;x∗

m] gilt dann:

x∗i = xi + 1 für i = b − 1, x∗

i = xi − 1 i = b, x∗i = xi sonst.

Die (bedingte) Wahrscheinlichkeit, dass auf x∗ die Besetzung x folgt (dass alsoder an j -ter Stelle genannte Geburtstag zum b-ten Mal auftritt), ist somit xb−1+1

z.

Beispiel 5 Rottmann erläutert sein Vorgehen an der Besetzung x = [362;2;0;1], de-ren Wahrscheinlichkeit er rekursiv bestimmen will. Da hier x2 = 0 ist, kommen fürdie Bestimmung der möglichen Vorgänger nur b = 1 und b = 3 infrage; im erstenFall ist x∗ = [363;1;0;1] im zweiten dagegen x∗ = [362;2;1;0]. Die Wahrschein-lichkeit für den Übergang von x∗ nach x ist einmal 363

365 , das andere Mal 1365 .

Rottmann weist selbst darauf hin, dass die Anzahl der Wahrscheinlichkeiten, dievon einem rekursiv arbeitenden Programm zu berechnen wären, mit wachsendem n

exponentiell anwächst. Damit werde die Berechnung „zu einer Aufgabe, die selbstmit den schnellsten Computern nicht effektiv lösbar ist“ ([5], S. 31f).

Auch hier bietet sich als Ausweg wieder eine iterative anstelle der nur sehr be-grenzt einsetzbaren rekursiven Berechnung an. Hierzu habe ich 2006 einen Vorschlaggemacht [4], der zwar eine deutliche Verbesserung bringt, aber immer noch sehrspeicher- und rechenintensiv ist.

3 Ein neuer Algorithmus

Unser Ziel ist die Berechnung der Wahrscheinlichkeit P(M ≥ s) für das Ereignis E,dass bei einer Aufteilung von n Kugeln auf z Fächer in mindestens ein Fach mindes-tens s Kugeln gelangen. Wir zerlegen diese Aufgabe in zwei Schritte, indem wir zu-nächst alle zum Gegenereignis E gehörigen Besetzungen x (mit M < s) bestimmenund dann die Wahrscheinlichkeiten P(X = x) sowie deren Summe P(E) berechnen.Als Lösung erhält man schließlich P(M ≥ s) = 1 − P(E). Im Unterschied zu denbisher betrachteten Lösungswegen wählen wir dabei nicht eine Rekursion nach derAnzahl n der Kugeln sondern nach der Maximalbelegung m der Fächer.

3.1 Bestimmung der Besetzungen mit M < s

Wir erläutern das Vorgehen an einer Verallgemeinerung von Beispiel 1.

Beispiel 6 Will man P(M ≥ 4) bei der Verteilung von 8 Kugeln auf 6 Fächer bestim-men, so besteht E aus allen Besetzungen mit n = 8, z = 6 und m ≤ s − 1 = 3. Zu-nächst überlegt man sich, in wie viele Fächer – unter Beachtung der Bedingungen (1)und (2) – genau s − 1 = 3 Kugeln gelangen können, welche Werte also x3 annehmenkann. Hier können 0, 1 oder 2 Fächer dreifach belegt werden, wobei man 0, 3 oder6 Kugeln „verbraucht“. Das weitere Vorgehen veranschaulicht das Baumdiagramm(Abb. 5).

G. Riehl

Abb. 5 Bestimmung der bei 8Kugeln und 6 Fächernmöglichen Besetzungen mitm ≤ 3

Die nach der Festlegung von x3 verbleibenden 8 bzw. 5 oder 2 Kugeln sind imnächsten Schritt auf die 6 bzw. 5 oder 4 nicht besetzten Fächer so aufzuteilen, dasshöchstens 2 in jedes Fach kommen. Dies ist die gleiche Aufgabe wie zu Beginn,jedoch mit einer um mindestens 1 kleinerer Maximalbelegung.

Abbildung 5 zeigt die vollständige Lösung; dabei bezeichnen km bzw. fm die An-zahl der für die Bestimmung von xm verfügbaren Kugeln und Fächer. Der Pfad fürdie Besetzung aus Beispiel 1 ist durch dickere Strichstärke hervorgehoben.

Auch in Abb. 5 wird noch einmal deutlich, dass durch x2 nicht nur k1 und f1sondern auch die Werte von x1 und x0 festgelegt sind: x1 = k1 und x0 = f1 − k1.

Allgemein dienen als Startwerte für km und fm

ks−1 = n und fs−1 = z. (8)

Für 1 ≤ m ≤ s –1 gelten die Rekursionsformeln

km−1 = km − m · xm (9)

und

fm−1 = fm − xm. (10)

Sind nun m, km und fm gegeben, so ergeben sich für xm zwei Einschränkungen,die schon in Beispiel 6 deutlich wurden. In den maximal belegten Fächern liegenxm · m Kugeln, und diese Zahl kann höchstens gleich der Anzahl km der verfügbarenKugeln sein. Wegen xm ∈ N gilt also xm ≤ [ km

m]. Andererseits müssen sich die rest-

lichen Kugeln so auf die noch freien Fächer aufteilen lassen, dass in keines mehr alsm − 1 Kugeln gelangen, km−1 darf also nicht größer als (m − 1) · fm−1 sein; es mussalso gelten

km − m · xm ≤ (m − 1) · (fm − xm)

⇔ km ≤ (m − 1) · fm + xm

⇔ xm ≥ km − (m − 1) ·fm,

Alte Geburtstagsprobleme – neu gelöst

Abb. 6 Pseudocode der Prozedur Knoten(m, k,f, t,x) zur Bestimmung der Besetzungen x mit M < s

wobei xm natürlich nicht negativ werden darf. Bezeichnet a die möglichen Werte fürdie Anzahl xm der Fächer mit m Kugeln, so werden diese also begrenzt durch dieBedingung amin ≤ a ≤ amax mit

amin = max[0; km − (m − 1) · fm

]und amax =

[km

m

]. (11)

Abbildung 6 fasst unser Vorgehen als Pseudocode einer rekursiven Prozedur Kno-ten mit den Parametern m, k, f , t und x zusammen. Sie wird mit undefiniertem x

sowie nach (8) mit m = s − 1, k = n und f = z gestartet; die Variable t , die erst imfolgenden Abschnitt benötigt wird, bekommt den Startwert 1.

Solange m > 0 ist, ruft sich diese Prozedur mit jeweils um 1 vermindertem m (undentsprechend angepassten Werten für k, f und x) selbst auf. Auf diese Weise wirdsukzessive das s-tupel x aufgebaut, beginnend mit xs−1 bis hinunter zu x1.

Ist m = 0, so wird x0 = f gesetzt, und die somit vollständige Besetzung x wirdausgegeben, z. B. in einer Datei gespeichert. Danach springt das Programm in dieletzte noch nicht beendete aufrufende Prozedur zurück und setzt die Verarbeitungdort fort.

Bemerkenswert ist, dass die nacheinander vom Programm erzeugten Besetzungennach der Größe von m geordnet vorliegen, wie es für Beispiel 6 auch aus Abb. 5hervorgeht: Die oberen drei Pfade gehören zum Ereignis „M = 2“, die unteren fünfzu „M = 3“; wegen n > z ist M = 1 nicht möglich.

Im folgenden Abschnitt werden wir den Algorithmus der Abb. 6 so ausbauen, dassmithilfe der Variablen t zusätzlich auch P(X = x) berechnet wird.

3.2 Berechnung der Besetzungswahrscheinlichkeiten

Die Besetzungszahl N(x) kann man parallel zum eben gezeigten schrittweisen Auf-bau von x berechnen. Wir zeigen dies für den in Abb. 6 markierten Pfad 1–2–1–2(mit umgekehrter Reihenfolge der xm!): Zuerst sind ein Fach und drei Kugeln fürdie Dreifach-Belegung zu wählen. Das ist auf

( 61

) · ( 83

)Arten möglich; anschließend

gibt es( 5

2

)Möglichkeiten, die 2 doppelt belegten Fächer auszuwählen; in eines kom-

men 2 der restlichen 5 Kugeln; von den dann noch vorhandenen 3 Kugeln nochmals2 in das andere. Für die Fächer mit b = 2 gibt es also

( 52

) · {( 52

) · ( 32

)}Arten der

Belegung. Für b = 1 findet man analog( 3

1

) · ( 11

)Möglichkeiten. Bei den unbelegt

gebliebenen Fächern schließlich hat man keine Wahl mehr; im Fall b = 0 tritt stets

G. Riehl

Tab. 3 Iterative Berechnungder Wahrscheinlichkeit für dieBesetzung [2;1;2;1]

m 3 2 1 0

tm 1 1,55556 0,36008 0,18004

qm 1,55556 0,23148 0,50000 1

der Faktor 1 auf. Man kann ihn in unserem Beispiel – analog zu den Faktoren fürb > 0- in der Form

( 22

) · {( 20

) · ( 10

)}schreiben.

Das Produkt der jeweils ersten Faktoren (der Anzahl der Wahlmöglichkeiten fürdie Fächer) beträgt 6

1! · 5·42! · 3

1! · 2·12! = 6!

1!·2!·1!·2! , ist also genau der zweite Faktor ausder Formel (3) für N(x) bei v. Mises. Den ersten Faktor von (3) liefert das Produktder restlichen Faktoren: 8·7·6

3! · { 5·42! · 3·2

2! } · 11! · { 1

0! · 10! } = 8!

3!1·2!2·1!1·0!2 (Anzahl derWahlmöglichkeiten für die Kugeln). Um die Wahrscheinlichkeit von x zu bestimmen,muss man N(x) noch durch zn dividieren.

Allgemein berechnen wir, analog zu obigem Beispiel, für jedes m ≤ s denFaktor qm, um den sich die Besetzungswahrscheinlichkeit p in diesem Schrittändert:

qm =(fm

xm

) · ∏xm−1i=0

(km − i · mm

)

zm·xm; (12)

der Nenner zn von p wird dabei je nach der Anzahl m · xm der im Schritt m verteiltenKugeln auf die Nenner von qs−1, . . . , q1 aufgeteilt. Man beachte, dass es sich beiden qm selbst nicht um Wahrscheinlichkeiten handelt, so ist im obigen Beispiel q3 =149 > 1.

Bezeichnen wir mit tm das Teilprodukt der qb mit b > m, so lässt sich der iterativeAufbau der Besetzungswahrscheinlichkeit p in folgender Weise beschreiben:

tm = 1 für m = s − 1;tm = tm+1 · qm+1 für 0 ≤ m < s − 1; (13)

p = t0.

Beispiel 7 Tabelle 3 zeigt die Anwendung von (12) und (13) auf die in Abb. 6 her-vorgehobene Besetzung [2;1;2;1]; der Startwert t3 und das Ergebnis t0 sind grauunterlegt. Wie in Beispiel 2 ergibt sich P(X = x) = t0 ≈ 0,18004.

Wie man den Algorithmus von Abb. 6 so erweitern kann, dass zu jeder Besetzungx mit M < s auch p = P(X = x) berechnet wird, zeigt Abb. 7.

Dieser Algorithmus ist dadurch besonders effektiv, dass beim Übergang zu ei-ner neuen Besetzung im Allgemeinen ein Teil der Koordinaten automatisch von derzuvor abgeschlossenen Besetzung übernommen wird und ebenso das Teilprodukt t

derjenigen Faktoren qm, die zu diesen vom Vorgänger übernommenen Koordinatengehören.

Alte Geburtstagsprobleme – neu gelöst

Abb. 7 Pseudocode der Prozedur Knoten(m, k,f, t,x) zur simultanen Bestimmung aller Besetzungen xmit M < s und ihrer Wahrscheinlichkeiten P(X = x)

4 Realisierung des Algorithmus

In diesem Abschnitt zeigen wir, wie man mit einem auf dem neuen Algorithmus ba-sierenden Programm die Probleme von Schrage und v. Mises in kürzester Zeit lösenkann. Das Programm ist in Borland Pascal 7.0 aus dem Jahr 1992 geschrieben, alsoaus der Entstehungszeit von Schrages Aufsatz, und wurde auf einem über 10 Jahrealten Computer ausgeführt, mithin auf einem Stand der Technik, wie sie auch Rott-mann schon zur Verfügung stand. Damit soll gezeigt werden, welchen Fortschritt –unabhängig von der zwischenzeitlichen Weiterentwicklung der Technik – der neueAlgorithmus bringt.

Außer dem zentralen Algorithmus der Abb. 7 enthält das Programm Routinen zurZeitmessung, zum Zählen der erzeugten Besetzungen und zum Aufsummieren derWahrscheinlichkeiten von Besetzungen mit derselben Maximalbelegung m.

Anhand der Ergebnisse werden wir die Aspekte Rechenzeit, Genauigkeit unddurch die verwendete Hard- und Software bedingte Grenzen analysieren. ModernereGeräte und Programmiersysteme ermöglichen es, die Rechenzeit weiter zu verkürzenund die Grenzen – etwa hinsichtlich der Anzahl n der aufzuteilenden Kugeln bzw. derGruppengröße beim Geburtstagsproblem – weiter hinauszuschieben.

4.1 Dreifach-Geburtstage

In Abschn. 2.2 haben wir die Wahrscheinlichkeit für das Ereignis „mindestens einDreifach-Geburtstag unter n Personen“ mittels Tabellenkalkulation gelöst, für „ge-nau ein Dreifach-Geburtstag“ war dies nicht möglich; mit dem neuen Algorithmuslassen sich beide Aufgaben simultan lösen. Es sei f die Wahrscheinlichkeitsvertei-lung der Maximalbelegung M , also f (m) = P(M = m), sowie F die zugehörige

G. Riehl

Tab. 4 Wahrscheinlichkeit für mindestens bzw. genau einen Dreifach-Geburtstag unter n Personen

n = 15, z = 365 n = 60, z = 365

m f (m) F(m) 1 − F(m) m f (m) F(m) 1 − F(m)

1 0,747099 0,747099 0,252901 1 0,005877 0,005877 0,994123

2 0,249572 0,996671 0,003329 2 0,786892 0,792770 0,207230

3 0,003302 0,999973 0,000027 3 0,198389 0,991159 0,008841

Tab. 5 Gesamtzahl g aller Besetzungen, Anzahl r der relevanten Besetzungen mit P(X = x) > 10−8 undRechenzeit t in Sekunden bei der Aufteilung von n Kugeln auf 365 Fächer

n 15 30 45 60

g 176 5604 89134 966467

r 18 55 116 224

t <0,005 s 0,005 s 1,59 18,62

Verteilungsfunktion, d. h. F(m) = P(M ≤ m). Wir lassen das Programm eine Ta-belle dieser beiden Funktionen sowie der Differenz 1 − F(m) = P(M ≥ m + 1) für1 ≤ m ≤ 3 erzeugen. In den grau unterlegten Zellen von Tab. 4 stehen die Ergebnissefür die Probleme von Schrage und v. Mises. Dieser Tabelle kann man zusätzlich dieWahrscheinlichkeit dafür entnehmen, dass an wenigstens einem Tag mindestens vierPersonen Geburtstag haben, P(M ≥ 4) = 1−F (3) beträgt 0,000027 für n = 15 bzw.0,008841 für n = 60.

4.2 Anzahl der Besetzungen bei wachsender Gruppengröße n

Solange nur relativ kleine Werte von s interessieren und damit F(s − 1) nur wenigeSummanden mit kleinen Werten von m umfasst, bleibt auch die Zahl der möglichenBesetzungen begrenzt, bei den Beispielen in Tab. 4 sind es 27 bzw. 331. Für dieBerechnungen braucht der Computer im ersten Fall weniger als 1 ms, im anderen 2,2ms.

Mit zunehmender Größe von n und s steigt zwar die Anzahl der Besetzungen ra-pide an, die allermeisten haben aber eine sehr kleine Wahrscheinlichkeit. Die Wertein Tab. 5 zeigen dies für verschiedene Gruppengrößen n beim Geburtstagsproblem.Außer der Gesamtzahl g der bei n Kugeln möglichen Besetzungen wurde auch dieAnzahl r der „relevanten“ Besetzungen mit einer Wahrscheinlichkeit über 10−8 aus-gezählt, deren Summe nur wenig von 1 abweicht, wie wir im folgenden Abschnittsehen werden.

Es wird deutlich, dass r mit zunehmendem n nur geringfügig zunimmt. Der Grundfür die starke Zunahme der Rechenzeit sind die vielen Besetzungen mit vernach-lässigbar kleiner Wahrscheinlichkeit, die wir im folgenden Abschnitt ausschließenwerden.

Alte Geburtstagsprobleme – neu gelöst

Tab. 6 P („mindestens s = m + 1 von n Personen haben am selben Tag Geburtstag“) = 1 − F(m)

n = 60, z = 365, s ≤ 6 n = 125, z = 365, s ≤ 8

m f (m) F(m) 1 − F(m) m f (m) F(m) 1 − F(m)

1 0,005877 0,005877 0,994123 1 3,2 · 10−11 0,000000 1,000000

2 0,786892 0,792770 0,207230 2 0,138055 0,138055 0,861945

3 0,198389 0,991159 0,008841 3 0,718895 0,856950 0,143050

4 0,008570 0,999729 0,000271 4 0,133036 0,989987 0,010013

5 0,000265 0,999993 0,000007 5 0,009466 0,999452 0,000548

6 0,000007 1,000000 1,8 · 10−7 6 0,000522 0,999975 0,000025

7 0,000000 1,000000 4,6 · 10−8 7 0,000024 0,999999 0,000001

8 0,000000 1,000000 4,6 · 10−8 8 0,000001 1,000000 5,5 · 10−8

4.3 Mehrfach-Geburtstage mit s > 3 – Beschleunigung des Algorithmus

Um allgemein P(M ≥ s) zu bestimmen, muss man f (m), F(m) und 1−F(m) wie inTab. 4 bis m = s − 1 berechnen; dann ist P(M ≥ s) = 1 −F(s − 1). In Tab. 6 ist diesfür n = 60 und n = 125 durchgeführt, wobei eine Genauigkeit von 6 Nachkommas-tellen angestrebt wurde. Um die Berechnung von irrelevant kleinen Wahrscheinlich-keiten zu vermeiden, werden die rekursiven Aufrufe der Prozedur Knoten (in Abb. 8grau markiert) und alle sich daraus ergebenden Rechenschritte nur dann ausgeführt,wenn das Teilprodukt t der Pfadwahrscheinlichkeit größer als 10−8 ist. Die Rechen-zeit verkürzt sich dadurch erheblich, sie beträgt 0,11 s im Fall n = 60 bzw. 2,3 s fürn = 125.

Ob durch die Vernachlässigung der unwahrscheinlichen Besetzungen Fehler auf-treten, die die angestrebte Genauigkeit verletzen, kann man daran erkennen, dassF(m) den Wert 1,000000 nicht erreicht. Die Summe der vernachlässigten Wahr-scheinlichkeiten ergibt die Differenz 1 − F(m), die sich – abhängig von der Run-dungsgenauigkeit – ab einem bestimmten Wert von m nicht mehr ändert (in Tab. 6ist dies für n = 60 von m = 7 an der Fall). Dass in unseren Beispielen die gewünsch-te Genauigkeit gewährleistet ist, erkennt man auch daran, dass 1 − F(m) ab m = 6bzw. m = 8 auf 0,000000 zu runden wäre. Sollte einmal 1 −F(m) auf 0,000001 odereinen größeren Wert gerundet erscheinen, muss man die Toleranzgrenze für t kleinerals 10−8 wählen.

Auf keinen Fall darf man die in der Tabelle grau unterlegten Werte für die Be-stimmung von P(M ≥ s) benutzen, da sie mit einem hohen relativen Fehler behaftetsein können. Die Werte in Tab. 6 sind für diese Aufgabe nur bis s = 6 bzw. s = 8brauchbar.

4.4 Verallgemeinertes Geburtstags-Paradoxon – Technische Grenzen

Das in Abschn. 2.1 angesprochene sog. Geburtstags-Paradoxon lässt sich auf zweiArten verallgemeinern: Man kann danach fragen, ab welcher Gruppengröße n esgünstig wird, auf mindestens s Personen mit gemeinsamem Geburtstag zu wetten,

G. Riehl

Abb. 8 Algorithmus für die Suche nach dem kleinsten n beim verallgemeinerten Geburtstags-Paradoxon

Tab. 7 Lösung des Geburtstagsparadoxons für s = 2 und s = 3 (n = 23 bzw. n = 88)

z = 365, s = 2, m = 1; p = 0,5 z = 365, s = 3, m = 2; p = 0,5

n1 1 − F(n1,1) n2 1 − F(n2,1) n1 1 − F(n1,2) n2 1 − F(n2,2)

1 0,000000 2 0,002740 1 0,000000 2 0,000000

2 0,002740 4 0,016356 · · · · · · · · · · · ·4 0,016356 8 0,074335 64 0,244999 128 0,879996

8 0,074335 16 0,283604 64 0,244999 96 0,602252

16 0,283604 32 0,753348 80 0,418169 96 0,602252

16 0,283604 24 0,538344 80 0,418169 88 0,511065

20 0,411438 24 0,538344 84 0,464550 88 0,511065

22 0,475695 24 0,538344 86 0,487826 88 0,511065

22 0,475695 23 0,507297 87 0,499455 88 0,511065

und man kann statt 0,5 eine andere kritische Wahrscheinlichkeit p für dieses Er-eignis vorgeben. Dann lautet also die Aufgabe: „Bestimme das kleinste n, für dasP(M ≥ s) > p wird.“

In jedem Fall ist nun m = s − 1 vorgegeben und die Gruppengröße n variabel.Wir machen dies dadurch deutlich, dass wir f und F nun als Funktionen von zweiVariablen notieren, in Tab. 6 also f (60;m), F(60;m), f (125;m), f (125;m) stattf (m) und F(m). Wir suchen das kleinste n, für das 1 − F(n,m) > p wird. Die-se Suche verläuft in zwei Schritten, wie der Algorithmus in Abb. 8 zeigt. Das inAbschn. 4.3 benutzte Programm wird hier in abgewandelter Form als Funktion F

verwendet.Tabelle 7 zeigt die Anwendung des Algorithmus auf das Geburtstagsparadoxon,

also s = 2 und p = 0,5, sowie auf den Fall s = 3 und p = 0,5. Zunächst werdendie benachbarten Zweier-Potenzen n1 = 2r und n2 = 2r+1 so bestimmt, dass für dasgesuchte n die Ungleichung n1 < n ≤ n2 gilt; dies ist im linken Teil von Tab. 7 beimIntervall [16; 32] erreicht, im rechten bei [64; 128]. Daran schließt sich eine Schach-telung durch Intervall-Halbierung an, bis n2 − n1 = 1 ist. Dann ist n2 die gesuchteminimale Gruppengröße n.

Alte Geburtstagsprobleme – neu gelöst

Tab. 8 Minimalwerte für n mit P(M ≥ s) > p (leere Felder: Keine Berechnung möglich)

p s = 2 s = 3 s = 4 s = 5

0,9 41

0,5 23 88

0,1 10 47 114

0,05 7 37 94

0,01 4 22 62 125

Beim Versuch, den Fall s = 4 zu lösen, kommt es zu einem Programm-Abbruch,es wird ein „floating point overflow“ gemeldet. Hier stößt man an die Grenzen desLeistungsvermögens der eingangs erwähnten technischen Ausstattung. Mit stärkererHard- und Software lassen sich diese Grenzen jedoch erweitern.

Bei den Geburtstagsproblemen mit z = 365 treten keine technischen Problemeauf, wenn die Gruppengröße n unter 100 liegt. In Tab. 8 sind die kleinsten n angege-ben, bei denen die Wahrscheinlichkeit größer als p wird, dass mindestens s Personengemeinsam Geburtstag haben. Die leeren Felder zeigen an, wo die Berechnung nichtmöglich war; in allen diesen Fällen ist erkennbar, dass n sicher größer als 100 seinmuss.

Literatur

1. Barth, F., Haller, R.: Besetzungen und Geburtstage. Stoch. Sch. 32(3), 20–27 (2012)2. Barth, F., Haller, R.: Gemeinsame Geburtstage. Stoch. Sch. 33(1), 25–32 (2013)3. Mises, R.v.: Über Aufteilungs- und Besetzungs-Wahrscheinlichkeiten. Istanbul Univ. Fen Fak. Mecm

4, 145–163 (1939)4. Riehl, G.: Neues zum Geburtstagsproblem. MNU, Math. Naturwiss. Unterr. 59(7), 439–444 (2006)5. Rottmann, K.: Lösung des Geburtstagsproblems für den Fall, dass k von n Personen am gleichen Tag

Geburtstag haben. Stoch. Sch. 32(2), 30–32 (2002)6. Schrage, G.: Ein Geburtstagsproblem. Mathem. Semesterber. 37, 251–257 (1990)