Geburtstagsparadox für drei Personen

Viele Menschen kennen das Paradoxon der Geburtstage : In einer Gruppe von 23 zufällig ausgewählten Personen übersteigt die Wahrscheinlichkeit, dass mindestens zwei von ihnen den gleichen Geburtstag haben, die Hälfte.

Das Problem, das ich betrachten werde, ist als Übung in dem Buch Algorithmen: Konstruktion und Analyse formuliert :
„Wie viel muss eine Person mitnehmen, um mindestens die Hälfte mit mindestens drei Personen zu treffen, die denselben Geburtstag haben.“


Wir stellen sofort fest, dass die Geburtstage der Versuchsteilnehmer als Ereignisse als gemeinsam unabhängig und gleich wahrscheinlich angesehen werden.

Wir führen eine Notation ein:

n = 365 (wir lassen auch das Schaltjahr weg).
k ist die Anzahl der Teilnehmer. Wir betrachten k <= 2 n , andernfalls tritt mit Wahrscheinlichkeit 1 ein dreifacher Zufall auf.

A ist ein Ereignis, das darin besteht, dass die Gruppe drei oder mehr Personen mit demselben Geburtstag hat.
B = ( nicht A ) - eine Veranstaltung, die darin besteht, dass keine drei Teilnehmer den gleichen Geburtstag haben.

Ereignis B wird genau dann ausgeführt, wenn eine bestimmte Anzahl m vorliegtAn verschiedenen Tagen im Jahr nehmen jeweils genau zwei Personen teil, an den anderen ( k - 2 m ) Tagen genau eine Person:
Tage d 1 d 2 ... d k - 2 m d k - 2 m + 1 d k - 2 m + 2 ... d k - m d k - m + 1 ... d n
Anzahl der Personen 1 1 ... 1 2 2 ... 2 0 ... 0
Es ist klar, dass m in Abhängigkeit von einer bestimmten Personengruppe von 0 bis [ k / 2] variieren kann .
Sei B m die Veranstaltung, die aus genau zwei Teilnehmern an m verschiedenen Tagen im Jahr und jeweils einem an den anderen ( k - 2 m ) Tagen besteht.
Die Besonderheit der Menge von Ereignissen { B m , m = 0, ..., [ k / 2]} besteht darin, dass sie inkompatibel sind und

B = B 0B 1 ≤ ... ≤ B [ k / 2] .

Dies ermöglicht es uns, die Wahrscheinlichkeit des Ereignisses B durch die Wahrscheinlichkeiten der Ereignisse B m zu berechnen :

P ( B ) = P ( B 0 ) + P ( B 1 ) + ... + P ( B [ k / 2] ).

Als nächstes untersuchen wir die Wahrscheinlichkeit von Ereignissen B m .

Ebenso wahrscheinliche elementare Ergebnisse (Ereignisse) sind Gruppen von Paaren: {( i , d i ); i = 1, ..., die k }, von denen jedes Mittel , dass die Person Nummer i als Geburtstag hat d i.
Die Anzahl aller elementaren Ergebnisse wird basierend auf der Tatsache bestimmt, dass jeder Teilnehmer n Geburtstagsoptionen hat:
N B m = n k .

Die Anzahl der elementaren Ergebnisse, wenn das Ereignis B m ausgeführt wird, wird als etwas komplizierter angesehen:

B m = C n m C n-m k -2 m k ! / 2 m .

Hier haben wir zunächst die Anzahl der Möglichkeiten bestimmen , die ausgewählt werden können , m Tage Doppel Streichhölzer. Wählen Sie dann aus den verbleibenden Tagen k - 2 m, die für eine Person entfallen. An ausgewählten Tagen können die Teilnehmer k ! / 2 m wege. Teilen Sie durch 2 m , da uns die Reihenfolge innerhalb der Paare, die einen gemeinsamen Geburtstag haben, egal ist.

Daher

P ( B m ) = N B m / N = C n m C n-m k -2 m k ! / (2 m n k ).
P ( B ) = k ! (C n 0 C n -0 k -0 / 2 0+ C n 1 C n –1 k –2 / 2 1 + ... + C n m C n – m k –2 m / 2 m + ... + C n [ k / 2] C n - [ k / 2] k –2 [ k / 2] / 2 [ k / 2] ) / n k .

Die gewünschte Wahrscheinlichkeit ist gleich:

P ( A ) = 1 - P ( B ) = 1 - k ! (C n 0 C n-0 k -0 / 2 0 + C n 1 C n -1 k -2 / 2 1 + ... + C n m C n-m k -2 m / 2 m + ... + C n [ k / 2] C n - [ k / 2] k -2 [ k / 2] / 2 [ k / 2] ) / n k .

Mein Java-Programm ergab die folgenden Werte dieser Wahrscheinlichkeit in Abhängigkeit von k :
k P ( A )
2 0
3 7.506E-6
5 7.475E-5
10 8,877E-4
20 0,00824
40 0,0669
60 0,207
70 0,306
80 0,418
87 0,499
88 0,511
100 0,646
110 0,746
120 0,828
150 0,965
200 0.999512
250 0.999999460
Sie benötigen also mindestens 88 Personen, damit die Wahrscheinlichkeit eines Triple Matchs 1/2 übersteigt.

Jetzt auch beliebt: