Rozszerzenie paradoksu urodzinowego na więcej niż 2 osoby

W tradycyjnym paradoksie urodzinowym pytanie brzmi: „jakie są szanse, że dwie lub więcej osób w grupie osób będzie miało urodziny”. Utknąłem na problem, który jest przedłużeniem tego.$n$

Zamiast znać prawdopodobieństwo, że dwie osoby dzielą urodziny, muszę rozszerzyć pytanie, aby wiedzieć, jakie jest prawdopodobieństwo, że lub więcej osób podzieli urodziny. Przy możesz to zrobić, obliczając prawdopodobieństwo, że żadna dwie osoby nie będą dzielić urodzin i odejmie to od , ale nie sądzę, żebym mógł rozszerzyć tę logikę na większą liczbę .$x$$x=2$$1$$x$

Aby to jeszcze bardziej skomplikować, potrzebuję również rozwiązania, które będzie działać dla bardzo dużych liczb dla (milionów) i (tysięcy).$n$$x$

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 .$b^n$$b$$n$$q(k; n, b)$$k$$k$$q(k;n,b)$$k$$b^{-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:$n$$n = 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], \ldots\}$$k^\text{th}$$k$

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 ] ! $n$$a[1]$$1$$a[2]$$2$$a[1]!a[2]!\cdots$; 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 $b$$b-1$ gdzie b ( m ) oznaczab(b-1)⋯(b-m+$b^{(a[1]+a[2]+\cdots)}$$b^{(m)}$ .$b(b-1)\cdots(b-m+1)$

Istnieje oczywista i dość prosta rekurencja odnosząca liczbę dla wzoru do liczby dla każdego wzorca . Po tych [ $\{a[1], \ldots, a[k]\}$ . Umożliwia to szybkie obliczenie zliczeń dla skromnych wartości n . Konkretnie [ k ] reprezentuje a [ k ] miejsc urodzenia dzielone dokładnie$\{a[1], \ldots, a[k-1]\}$$n$$a[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]$$k$$n$$x$$\{a[1], \ldots, 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)$$n$$k$

Przy (pięć możliwych urodzin) i n = 4 (cztery osoby), otrzymujemy$b=5$$n=4$

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 = 365$$n = 23$$q( k;23,365)$$k$

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 $n/b$$b$ : 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 ,$n/b$$n$$F(k)^b$$F$$n = 23$ daje$b = 365$

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.$n$$b$

Omotać, rozważmy oryginalne pytanie: wziąć (liczba obserwacji) oraz b = $n = 10,000$ (w przybliżeniu liczba możliwych „struktur”). Przybliżony rozkład maksymalnej liczby „wspólnych urodzin” wynosi$b = 1\,000\,000$

(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.$n$$b$

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 = $n = 10000$ skrzynek:$b = 1\,000\,000$

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.

Zawsze można rozwiązać ten problem za pomocą rozwiązania monte-carlo, chociaż nie jest to najbardziej wydajne. Oto prosty przykład problemu 2 osób w R (z prezentacji, którą przedstawiłem w zeszłym roku ; użyłem tego jako przykładu nieefektywnego kodu), który można łatwo dostosować, aby uwzględnić więcej niż 2:

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))
}

To próba ogólnego rozwiązania. Mogą występować błędy, więc używaj go ostrożnie!

Najpierw notacja:

$P(x,n)$$x$$n$

$P(y|n)$ $y$$n$

Uwagi:

1. $P(.)$

2. $y$$y$

Następnie wymagane prawdopodobieństwo podaje:

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

Teraz,

$P(y|n) = {n \choose y} (\frac{365}{365})^y \ \prod_{k=1}^{k=n-y}(1 -\frac{k}{365})$

$y$

Krok 1: Możesz wybrać $y$ ludzie w ${n \choose y}$ sposoby

Krok 2: Ponieważ dzielą urodziny, może to być dowolny z 365 dni w roku. Mamy w zasadzie 365 wyborów, co daje nam$(\frac{365}{365})^y$.

Krok 3: Pozostałe $n-y$ ludzie nie powinni dzielić urodzin z pierwszym $y$ludzie lub ze sobą. Takie rozumowanie daje nam$\prod_{k=1}^{k=n-y}(1 -\frac{k}{365})$.

You can check that for $x$ = 2 the above collapses to the standard birthday paradox solution.