Jest to problem liczenia: istnieją ewentualne cesje b urodzin do n osób. Spośród nich niech q ( k ; n , b ) będzie liczbą przydziałów, dla których żadne urodziny nie są dzielone przez więcej niż k osób, ale przynajmniej jedno urodziny jest faktycznie dzielone przez k osób. Prawdopodobieństwo, którego szukamy, można znaleźć, sumując q ( k ; n , b ) dla odpowiednich wartości k i mnożąc wynik przez b - n .bnbnq(k;n,b)kkq(k;n,b)kb−n
Liczby te można znaleźć dokładnie dla wartości mniejszych niż kilkaset. Nie będą one jednak zgodne z żadną prostą formułą: musimy wziąć pod uwagę wzorce przydzielania urodzin . Zilustruję to zamiast przedstawienia ogólnej demonstracji. Niech n = 4 (jest to najmniej interesująca sytuacja). Możliwości są następujące:nn=4
- Każda osoba ma wyjątkowe urodziny; kod to {4}.
- Dokładnie dwie osoby dzielą urodziny; kod to {2,1}.
- Dwie osoby mają jedno urodziny, a pozostałe dwie mają inne; kod to {0,2}.
- Trzy osoby dzielą urodziny; kod to {1,0,1}.
- Cztery osoby dzielą urodziny; kod to {0,0,0,1}.
Zasadniczo kod jest krotką zliczeń, których k- ty element określa, ile różnych dat urodzenia jest dzielonych przez dokładnie k osób. W szczególności{a[1],a[2],…}kthk
1a[1]+2a[2]+...+ka[k]+…=n.
Zauważ, nawet w tym prostym przypadku, że istnieją dwa sposoby osiągnięcia maksymalnie dwóch osób na urodziny: jeden z kodem a drugi z kodem { 2 , 1 } .{0,2}{2,1}
Możemy bezpośrednio policzyć liczbę możliwych przypisań urodzin odpowiadających dowolnemu kodowi. Ta liczba jest iloczynem trzech terminów. Jeden to współczynnik wielomianowy; zlicza liczbę sposobów podziału ludzi do a [ 1 ] grupach 1 , [ 2 ] grupach 2 i tak dalej. Ponieważ sekwencja grupami nie ma znaczenia, trzeba podzielić tego wielomianu o współczynnik w [ 1 ] ! a [ 2 ] ! ⋯na[1]1a[2]2a[1]!a[2]!⋯; jego wzajemność jest drugim terminem. Na koniec uszereguj grupy i przypisz każdemu z nich urodziny: kandydatów do pierwszej grupy, b - 1 do drugiej i tak dalej. Wartości te należy pomnożyć razem, tworząc trzeci element. Jest równy „iloczynowi czynnikowemu” b (bb−1 gdzie b ( m ) oznaczab(b-1)⋯(b-m+1b(a[1]+a[2]+⋯)b(m) .b(b−1)⋯(b−m+1)
Istnieje oczywista i dość prosta rekurencja odnosząca liczbę dla wzoru do liczby dla każdego wzorca . Po tych [ k{a[1],…,a[k]} . Umożliwia to szybkie obliczenie zliczeń dla skromnych wartości n . Konkretnie [ k ] reprezentuje a [ k ] miejsc urodzenia dzielone dokładnie k{a[1],…,a[k−1]}na[k]a[k]k grup k osób zostało wyciągniętych z n ludzi, co można zrobić na x różnych sposobów (powiedzmy), pozostaje policzyć liczbę sposobów osiągnięcia wzoru { a [ 1 ] , … , a [ k - 1 ] } wśród pozostałych osób. Pomnożenie tego przez x daje rekurencję.a[k]knx{a[1],…,a[k−1]}x
Wątpię, aby istniała formuła zamknięta dla , która jest uzyskiwana przez zsumowanie zliczeń dla wszystkich partycji n, których maksymalny człon wynosi k . Pozwól, że podam kilka przykładów:q(k;n,b)nk
Przy (pięć możliwych urodzin) i n = 4 (cztery osoby), otrzymujemyb=5n=4
q(1)q(2)q(3)q(4)=q(1;4,5)=360+60=120=420=80=5.
Stąd na przykład szansa, że trzy lub więcej osób na cztery ma te same „urodziny” (z możliwych dat) wynosi ( 80 + 5 ) / 625 = 0,136 .5(80+5)/625=0.136
Jako kolejny przykład weź i n = 23 . Oto wartości q ( k ; 23 , 365 ) dla najmniejszego k (tylko do sześciu sig fig):b=365n=23q(k;23,365)k
k=1:k=2:k=3:k=4:k=5:k=6:k=7:k=8:0.492700.4945920.01253080.0001728441.80449E−61.48722E−89.92255E−115.45195E−13.
Korzystając z tej techniki, możemy łatwo obliczyć, że istnieje około 50% szansy (przynajmniej) na trójstronną kolizję urodzinową wśród 87 osób, 50% szansy na czterokierunkową kolizję wśród 187 osób i 50% szansy na pięciokierunkowa kolizja między 310 osobami. Ostatnie obliczenia zaczynają się kilka sekund (w każdym razie w Mathematica), ponieważ liczba rozważanych partycji zaczyna się powiększać. Dla znacznie większego potrzebujemy przybliżenia.n
Jedno przybliżenie uzyskuje się za pomocą rozkładu Poissona z oczekiwaniem , ponieważ możemy zobaczyć przypisanie urodzin jako wynikające z b prawie (ale nie całkiem) niezależnych zmiennych Poissona, z których każda ma oczekiwanie nn/bb : zmienna dla każdej możliwej urodzin opisuje, ile spośród n osób ma te urodziny. Rozkład maksimum wynosi zatem w przybliżeniu F ( k ) b, gdzie F jest Poissonem CDF. To nie jest rygorystyczny argument, więc zróbmy trochę testów. Przybliżenie dla n = 23 , bn/bnF(k)bFn=23 dajeb=365
k=1:k=2:k=3:k=4:0.4987830.4968030.0141870.000225115.
Porównując z poprzednim, można zauważyć, że względne prawdopodobieństwa mogą być słabe, gdy są małe, ale prawdopodobieństwa absolutne są dość dobrze przybliżone do około 0,5%. Testowanie w wielu i B sugeruje, że przybliżenie to zwykle o dobra.nb
Omotać, rozważmy oryginalne pytanie: wziąć (liczba obserwacji) oraz b = 1n=10,000 (w przybliżeniu liczba możliwych „struktur”). Przybliżony rozkład maksymalnej liczby „wspólnych urodzin” wynosib=1000000
k=1:k=2:k=3:k=4:k>4:00.8475+0.1520+0.0004+<1E−6.
(Jest to szybkie obliczenie.) Oczywiste jest, że obserwowanie jednej struktury 10 razy na 10 000 byłoby bardzo znaczące. Ponieważ zarówno i b są duże, spodziewam się, że aproksymacja będzie działać tutaj całkiem dobrze.nb
Nawiasem mówiąc, jak zasugerował Shane, symulacje mogą zapewnić przydatne kontrole. Symulacja Mathematica jest tworzona z funkcją podobną do
simulate[n_, b_] := Max[Last[Transpose[Tally[RandomInteger[{0, b - 1}, n]]]]];
który jest następnie iterowany i podsumowywany, jak w tym przykładzie, w którym działa 10 000 iteracji z , b = 1n=10000 skrzynek:b=1000000
Tally[Table[simulate[10000, 1000000], {n, 1, 10000}]] // TableForm
Jego wydajność to
2 8503
3 1493
4 4
Częstotliwości te są ściśle zgodne z przewidywanymi przez przybliżenie Poissona.