Erweiterung des Geburtstagsparadoxons auf mehr als 2 Personen

29

Im traditionellen Geburtstagsparadox lautet die Frage: "Wie hoch sind die Chancen, dass zwei oder mehr Personen in einer Gruppe von Personen einen Geburtstag haben?". Ich stecke in einem Problem, das eine Erweiterung davon ist.n

Anstatt die Wahrscheinlichkeit zu kennen, dass zwei Personen einen Geburtstag haben, muss ich die Frage erweitern, um zu wissen, mit welcher Wahrscheinlichkeit oder mehr Personen einen Geburtstag haben. Mit können Sie dies tun, indem Sie die Wahrscheinlichkeit berechnen, dass sich keine zwei Personen einen Geburtstag teilen, und diese von abziehen , aber ich glaube nicht, dass ich diese Logik auf eine größere Anzahl von .xx=21x

Um dies weiter zu erschweren, benötige ich auch eine Lösung, die für sehr große Zahlen für (Millionen) und (Tausende) funktioniert .nx

Simon Andrews
quelle
1
Ich
gehe
3
Eigentlich ist es ein Bioinformatik-Problem, aber da es auf dasselbe Konzept wie das Geburtstagsparadoxon hinausläuft, dachte ich, ich würde die irrelevanten Details sparen!
Simon Andrews
4
Normalerweise würde ich Ihnen zustimmen, aber in diesem Fall könnten die Details eine Rolle spielen, da es bereits ein Bioleiterpaket geben könnte, das genau das tut, was Sie verlangen.
Csgillespie
Wenn Sie es wirklich wissen wollen, handelt es sich um ein Musterfindungsproblem, bei dem ich versuche, die Wahrscheinlichkeit einer bestimmten Anreicherungsstufe einer Teilsequenz innerhalb einer Reihe größerer Sequenzen genau abzuschätzen. Ich habe daher eine Reihe von Subsequenzen mit zugehörigen Zählungen und weiß, wie viele Subsequenzen ich beobachtet habe und wie viele theoretisch beobachtbare Sequenzen verfügbar sind. Wenn ich eine bestimmte Sequenz 10 Mal aus 10.000 Beobachtungen gesehen habe, muss ich wissen, wie wahrscheinlich es ist, dass dies zufällig passiert ist.
Simon Andrews
Fast acht Jahre später habe ich unter stats.stackexchange.com/questions/333471 eine Antwort auf dieses Problem veröffentlicht . Der Code dort funktioniert jedoch nicht für große , da er in quadratische Zeit benötigt . n,n
Whuber

Antworten:

17

Dies ist ein Zählproblem: Es gibt mögliche Zuordnungen von Geburtstagen zu Personen. Von diesen sei die Anzahl von Aufgaben, für die kein Geburtstag von mehr als Personen geteilt wird, aber mindestens ein Geburtstag tatsächlich von Personen geteilt wird . Die Wahrscheinlichkeit, nach der wir suchen, kann durch Summieren von für geeignete Werte von und Multiplizieren des Ergebnisses mit . b n q ( k ; n , b ) k k q ( k ; n , b ) k b - nbnbnq(k;n,b)kkq(k;n,b)kbn

Diese Zählungen können genau für Werte von kleiner als einige hundert gefunden werden. Sie werden jedoch keiner einfachen Formel folgen: Wir müssen die Muster der Art und Weise berücksichtigen, in der Geburtstage zugewiesen werden können . Ich werde dies veranschaulichen, anstatt eine allgemeine Demonstration zu liefern. Sei (dies ist die kleinste interessante Situation). Die Möglichkeiten sind:n = 4nn=4

  • Jede Person hat einen einzigartigen Geburtstag; Der Code lautet {4}.
  • Genau zwei Personen haben Geburtstag; der Code ist {2,1}.
  • Zwei Leute haben einen Geburtstag und die anderen zwei haben einen anderen; der Code ist {0,2}.
  • Drei Personen haben Geburtstag; Der Code lautet {1,0,1}.
  • Vier Personen haben Geburtstag; Der Code lautet {0,0,0,1}.

Im Allgemeinen ist der Code ein Tupel von Zählungen, deren -Element angibt, wie viele unterschiedliche Geburtsdaten genau von Personen geteilt werden. So ist insbesonderek th k{a[1],a[2],}kthk

1a[1]+2a[2]+...+ka[k]+=n.

Beachten Sie, dass es auch in diesem einfachen Fall zwei Möglichkeiten gibt, um maximal zwei Personen pro Geburtstag zu erreichen: eine mit dem Code und eine mit dem Code .{ 2 , 1 }{0,2}{2,1}

Wir können die Anzahl der möglichen Geburtstagszuweisungen, die einem bestimmten Code entsprechen, direkt zählen. Diese Zahl ist das Produkt von drei Begriffen. Einer ist ein multinomialer Koeffizient; Es zählt die Anzahl der Möglichkeiten, Personen in Gruppe von , Gruppe von usw. zu unterteilen. Da die Reihenfolge der Gruppen keine Rolle spielt, müssen wir diesen Multinomialkoeffizienten durch dividieren . sein Gegenseitigkeit ist der zweite Ausdruck. Schliesslich richten Sie die Gruppen aus und weisen ihnen jeweils einen Geburtstag zu: Es gibt Kandidaten für die erste Gruppe,a [ 1 ] 1 a [ 2 ] 2 a [ 1 ] ! a [ 2 ] ! b b - 1 b ( a [ 1 ] + a [ 2 ] + ) b ( m ) b ( b - 1 ) ( b - m + 1 )na[1]1a[2]2a[1]!a[2]!bb1für die zweite und so weiter. Diese Werte müssen multipliziert werden und bilden den dritten Term. Es ist gleich das "faktoriellen Produkt" wobei Mittel .b(a[1]+a[2]+)b(m)b(b1)(bm+1)

Es gibt eine offensichtliche und ziemlich einfache Rekursion, die die Anzahl für ein Muster mit der Anzahl für das Muster . Dies ermöglicht eine schnelle Berechnung der Zählwerte für bescheidene Werte von . Insbesondere steht für Geburtsdatum, das genau von Personen geteilt wird. Nachdem diese Gruppen von Personen aus den Personen gezogen wurden, was auf verschiedene Arten (sagen wir) geschehen kann , bleibt die Anzahl der Arten zu zählen, wie das Muster erreicht werden kann{ a [ 1 ] , , a [ k - 1 ] } n a [ k ] a [ k ] k a [ k ] k n x { a [ 1 ] , , A [ k - 1 ] } x{a[1],,a[k]}{a[1],,a[k1]}na[k]a[k]ka[k]knx{a[1],,a[k1]}unter den verbleibenden Menschen. Multiplizieren Sie dies mit die Rekursion zu erhalten.x

Ich bezweifle, dass es eine geschlossene Formel für , die durch Summieren der Zählwerte für alle Partitionen von deren maximaler Term gleich . Lassen Sie mich einige Beispiele anbieten:n kq(k;n,b)nk

Mit (fünf mögliche Geburtstage) und (vier Personen) erhalten wirn = 4b=5n=4

q(1)=q(1;4,5)=120q(2)=360+60=420q(3)=80q(4)=5.

Woher zum Beispiel die Wahrscheinlichkeit, dass drei oder mehr von vier Personen denselben "Geburtstag" (von möglichen Daten) haben, gleich .( 80 + 5 ) / 625 = 0,1365(80+5)/625=0.136

Als weiteres Beispiel nehmen Sie und . Hier sind die Werte von für das kleinste (nur bis zu sechs Sig Feigen):n = 23 q ( k ; 23 , 365 ) kb=365n=23q(k;23,365)k

k=1:0.49270k=2:0.494592k=3:0.0125308k=4:0.000172844k=5:1.80449E6k=6:1.48722E8k=7:9.92255E11k=8:5.45195E13.

Mit dieser Technik können wir leicht berechnen, dass bei 87 Personen eine Wahrscheinlichkeit von etwa 50% (mindestens) einer Drei-Wege-Geburtstags-Kollision, bei 187 eine Wahrscheinlichkeit von 50% einer Vier-Wege-Kollision und eine Wahrscheinlichkeit von 50% besteht eine Fünf-Wege-Kollision zwischen 310 Menschen. Diese letzte Berechnung dauert (zumindest in Mathematica) einige Sekunden, da die Anzahl der zu berücksichtigenden Partitionen zu groß wird. Für wesentlich größere benötigen wir eine Näherung.n

Eine Annäherung ergibt sich aus der Poisson-Verteilung mit der Erwartung , da wir eine Geburtstagszuordnung als aus betrachten können, die sich aus nahezu (aber nicht ganz) unabhängigen Poisson-Variablen mit der Erwartung ergibt: der Variablen für einen gegebenen möglichen Geburtstag beschreibt, wie viele der Personen diesen Geburtstag haben. Die Verteilung des Maximums ist daher ungefähr wobei die Poisson-CDF ist. Dies ist kein strenges Argument, also lasst uns ein wenig testen. Die Näherung für , ergibtb n / b n F ( k ) b F n = 23 b = 365n/bbn/bnF(k)bFn=23b=365

k=1:0.498783k=2:0.496803k=3:0.014187k=4:0.000225115.

Ein Vergleich mit dem vorhergehenden zeigt, dass die relativen Wahrscheinlichkeiten schlecht sein können, wenn sie klein sind, aber die absoluten Wahrscheinlichkeiten sind vernünftigerweise gut auf ungefähr 0,5% angenähert. Tests mit einem weiten Bereich von und deuten darauf hin, dass die Approximation normalerweise ungefähr so ​​gut ist.bnb

Betrachten wir zum Abschluss die ursprüngliche Frage: Nehmen Sie (Anzahl der Beobachtungen) und (Anzahl der möglichen "Strukturen", ungefähr). Die ungefähre Verteilung für die maximale Anzahl von "gemeinsamen Geburtstagen" istb = 1n=10,000b=1000000

k=1:0k=2:0.8475+k=3:0.1520+k=4:0.0004+k>4:<1E6.

(Dies ist eine schnelle Berechnung.) Es ist klar, dass die Beobachtung einer Struktur bei 10 von 10.000 Strukturen von hoher Bedeutung ist. Da und beide groß sind, erwarte ich, dass die Approximation hier recht gut funktioniert.bnb

Im Übrigen können Simulationen nützliche Überprüfungen liefern, wie Shane angedeutet hat. Eine Mathematica-Simulation wird mit einer Funktion wie der folgenden erstellt

simulate[n_, b_] := Max[Last[Transpose[Tally[RandomInteger[{0, b - 1}, n]]]]];

Das wird dann iteriert und zusammengefasst, wie in diesem Beispiel, in dem 10.000 Iterationen des Falls , werden:b = 1n=10000b=1000000

Tally[Table[simulate[10000, 1000000], {n, 1, 10000}]] // TableForm

Seine Ausgabe ist

2 8503

3 1493

4 4

Diese Frequenzen stimmen eng mit denen überein, die durch die Poisson-Näherung vorhergesagt wurden.

whuber
quelle
Was für eine fantastische Antwort, vielen Dank @whuber.
JKnight
"Es gibt eine offensichtliche und ziemlich einfache Rekursion" - nämlich?
Kodiologist
1
@Kodiologist Ich habe eine kurze Beschreibung der Idee eingefügt.
Whuber
+1 aber wo in der ursprünglichen Frage haben Sie gesehen, dass n = 10000 und b = 1mln? Das OP scheint nach n = 1 mln und k = 10000 zu fragen, wobei b nicht angegeben ist (vermutlich b = 365). Nicht, dass es an dieser Stelle wichtig ist :)
Amöbe sagt Reinstate Monica
1
@amoeba Nach all der Zeit (sechs Jahre, 1600 Antworten und Zehntausende von Beiträgen) kann ich mich nicht erinnern, aber höchstwahrscheinlich habe ich die letzte Zeile falsch interpretiert. Beachten Sie zu meiner Verteidigung, dass, wenn wir es wörtlich lesen, die Antwort sofort ist (nach Anwendung einer Version des Pigeonhole-Prinzips): Es ist sicher, dass unter = Millionen von Menschen mindestens ein Geburtstag liegt, der unter mindestens = Tausende von ihnen! xnx
Whuber
2

Es ist immer möglich, dieses Problem mit einer Monte-Carlo-Lösung zu lösen, obwohl dies bei weitem nicht die effizienteste ist. Hier ist ein einfaches Beispiel für das 2-Personen-Problem in R (aus einer Präsentation, die ich im letzten Jahr gegeben habe ; ich habe dies als Beispiel für ineffizienten Code verwendet), das leicht angepasst werden kann, um mehr als 2 zu berücksichtigen:

birthday.paradox <- function(n.people, n.trials) {
    matches <- 0
    for (trial in 1:n.trials) {
        birthdays <- cbind(as.matrix(1:365), rep(0, 365))
        for (person in 1:n.people) {
            day <- sample(1:365, 1, replace = TRUE)
            if (birthdays[birthdays[, 1] == day, 2] == 1) {
                matches <- matches + 1
                break
            }
            birthdays[birthdays[, 1] == day, 2] <- 1
        }
        birthdays <- NULL
    }
    print(paste("Probability of birthday matches = ", matches/n.trials))
}
Shane
quelle
Ich bin nicht sicher, ob die Lösung für mehrere Typen hier funktioniert.
Ich denke, dass die Verallgemeinerung immer noch nur für zwei oder mehr Personen funktioniert, die sich einen Geburtstag teilen - nur, dass Sie verschiedene Unterklassen von Personen haben können.
Simon Andrews
1

Dies ist ein Versuch einer allgemeinen Lösung. Da es einige Fehler geben kann, ist Vorsicht geboten!

Zuerst etwas Notation:

x nP(x,n) ist die Wahrscheinlichkeit, dass oder mehr Personen unter Personen einen Geburtstag haben,xn

y nP(y|n) ist die Wahrscheinlichkeit, dass genau Personen unter Personen einen Geburtstag haben.yn

Anmerkungen:

  1. Der Missbrauch der Notation als Wird auf zwei verschiedene Arten verwendet.P(.)

  2. Per Definition kann nicht den Wert 1 annehmen, da dies keinen Sinn ergibt und = 0 so interpretiert werden kann, dass niemand einen gemeinsamen Geburtstag hat.yyy

Dann ist die erforderliche Wahrscheinlichkeit gegeben durch:

P(x,n)=1P(0|n)P(2|n)P(3|n)....P(x1|n)

Jetzt,

P(y|n)=(ny)(365365)y k=1k=ny(1k365)

Hier ist die Logik: Sie brauchen die Wahrscheinlichkeit, dass genau Personen einen Geburtstag haben.y

Schritt 1: Sie können wählen Menschen in Wege.( ny(ny)

Schritt 2: Da sie gemeinsam Geburtstag haben, kann dies jeder der 365 Tage im Jahr sein. Wir haben also im Grunde 365 Möglichkeiten, die uns .(365365)y

Schritt 3: Die verbleibenden Personen sollten keinen Geburtstag mit den ersten Personen oder untereinander teilen . Diese Argumentation gibt uns .y k = n - y k = 1 ( 1 - knyyk=1k=ny(1k365)

Sie können überprüfen, ob für = 2 die oben genannten Probleme mit der Standardlösung für Geburtstagsparadoxon zusammenhängen.x


quelle
Wird diese Lösung unter dem Fluch der Dimensionalität leiden? Wenn anstelle von n = 365 n = 10 ^ 6 ist, ist diese Lösung noch möglich?
Csgillespie
Einige Annäherungen müssen möglicherweise verwendet werden, um mit hohen Dimensionen umzugehen. Verwenden Sie möglicherweise die Stirling-Näherung für Fakultäten im Binomialkoeffizienten. Um mit den Produktbegriffen umzugehen, könnten Sie Protokolle nehmen und die Summen anstelle der Produkte berechnen und dann das Anti-Protokoll der Summe nehmen.
Es gibt auch mehrere andere Formen von Approximationen, die zum Beispiel die Taylorreihenerweiterung für die Exponentialfunktion verwenden. Siehe die Wiki-Seite für diese Annäherungen: en.wikipedia.org/wiki/Birthday_problem#Approximations
Angenommen, y = 2, n = 4 und es gibt nur zwei Geburtstage. Ihre Formel, angepasst durch Ersetzen von 365 durch 2, scheint zu sagen, dass die Wahrscheinlichkeit, dass genau 2 Personen einen Geburtstag haben, Comb (4,2) * (2/2) ^ 2 * (1-1 / 2) * (1-2 / 2) = 0. (In der Tat ist es leicht zu erkennen, dass die Wahrscheinlichkeiten, dass 2, 3 oder 4 Personen einen "Geburtstag" haben, 6/16, 8/16, und 2/16.) Tatsächlich ergibt Ihre Formel immer dann, wenn ny> = 365 ist, 0, während wenn n groß und y fest ist, die Wahrscheinlichkeit auf ein Maximum ungleich Null ansteigen sollte, bevor n 365 * y erreicht und dann abnimmt. aber nie runter auf 0.
whuber
Warum ersetzen Sie 365 durch ? Die Wahrscheinlichkeit, dass sich 2 Personen einen Geburtstag teilen, wird wie folgt berechnet: 1 - Prob (sie haben einen eindeutigen Geburtstag). Prob (dass sie einzigartigen Geburtstag haben) = (364/365). Die Logik ist wie folgt: Wählen Sie eine Person. Diese Person kann jeden Tag der 365 Tage als Geburtstag haben. Die zweite Person kann dann nur an einem der verbleibenden 364 Tage Geburtstag haben. Somit ist die Wahrscheinlichkeit, dass sie einen einzigartigen Geburtstag haben, 364/365. Ich bin nicht sicher, wie Sie 6/16 berechnen. n