12 osób, 3 urodziny, 1 dzień

Nowe pytanie na Quora: jakie jest prawdopodobieństwo, że z grupy 12 osób 3 będą miały urodziny tego samego dnia (UPDATE 2021: oryginał mojej odpowiedzi już niedostępny - skasowałem konto na Quora).

Problem ten jest zaskakująco trudny, jeżeli weźmiemy pod uwagę jak łatwo rozwiązać ten sam problem dla dwóch lub więcej urodzin tego samego dnia.

Jak dotychczas opublikowano dwie odpowiedzi. Ponieważ żyjemy w czasach, w których statystyka i rachunek prawdopodobieństwa stały się dziedzinami prawie doświadczalnymi, możemy sprawdzić jaki wynik da symulacja.

Uruchommy poniższy kod w R:

set.seed(777)
N <- 10000000
draw <- function(){
   sample(1:365, 12, replace = T)
}
check_if_three <- function(vector){
   for (item in vector){
   if (sum(vector == item ) >= 3)
      return(TRUE) # whenever we encounter three or more birthdays on the same day we return TRUE
   }
return(FALSE)
}
accumulator <- 0
for (n in 1:N){
   if (check_if_three(draw())){
      accumulator <- accumulator + 1
   }
}
print(accumulator/N)
[1] 0.0016186

i … otrzymaliśmy jeszcze jedną odpowiedź, różną od pozostałych.

Sprawdźmy, czy możemy uzyskać to samo bardziej analitycznie.

Łatwiej jest rozwiązać problem gdy wyrazi się go przy pomocy kulek i kubków, gdyż ułatwia to bezpośrednie zliczanie. Rozwiązywanie problemu przy użyciu prawdopodobieństw warunkowych, tak jak robimy to dla przypadku dwóch lub więcej urodzin jednego dnia, jest, moim zdaniem, trudniejsze.

Zamodelujmy nasze dwanaście osób jako dwanaście kulek z naklejonymi nazwiskami (czyli kulki nie są identyczne). 365 kubków z numerami ustawionych w rzędzie reprezentować będzie dni w roku. Zakładamy, że nie ma bliźniaków, lat przestępnych ani żadnych innych niespodzianek.

Rozłóżmy teraz kulki w kubkach w sposób losowy - możliwych jest $365^{12}$ konfiguracji. Rozumować można w następujący sposób: na każdej z kulek możemy dopisać dowolny z 365 dni a następnie włożyć ją do kubka. W takim razie liczba konfiguracji to $365\cdot 365 … 365 = 365^{12}$.

Jest bardzo trudno policzyć bezpośrednio liczbę konfiguracji z 3 lub więcej kulkami w tym samym kubku, więc policzmy je pośrednio. Użyjmy standardowej techniki liczenia konfiguracji, które mają MNIEJ niż 3 kulek.

Te konfiguracje mają albo jedną kulkę na kubek, albo dwie lub jedną kulkę na kubek. Pierwszy przypadek mamy już policzony dla przypadku dwóch lub więcej urodzin jednego dnia (patrz np. Wikipedia). Jest ich

$$\frac{365!}{(365-12)!}$$

Wynik ten można uzyskać również usuwając $n!$ ze wzoru na liczbę kombinacji $$ {365\choose{12}}=\frac{365!}{(365-12)!12!}.$$ W tym wzorze $n!$ jest obecne po to, żeby uwzględnić nieidentyczność kulek (lub, bardziej ogólnie, obiektów). Nasze kulki nie są identyczne, więc nie potrzebujemy tego elementu.

Teraz trudniejsza częsć, czyli obliczenie liczby konfiguracji, które mają dwie lub jedną kulkę w kubku.

Zacznijmy od przypadku, gdy mamy jedną parę kulek w kubku oraz 10 pojedynczych kulek. Możemy rozumować w następujący sposób: najpierw z dwunastu kulek losujemy dwie, sklejamy je, tak żeby powstała jedna z dwoma nazwiskami. Mamy tu

$$ 12\choose{2}$$

możliwości.

Teraz mamy do dyspozycji 11 nieidentycznych kulek, które musimy rozłożyć w 365 kubkach - jedną na kubek. Rozumując tak jak poprzendnio (w przypadku jednej kulki na kubek) otrzymujemy

$$ {12\choose{2}}\times \frac{365!}{(365-11)!}$$

Obliczmy jeszcze jeden przypadek. Ile mamy konfiguracji z dwiema parami i 8 pojedynczymi kulkami?

Losujemy pierwszą parę kulek spomiędzy 12 i zostaje nam 10 kulek. Spomiędzy tych 10 losujemy kolejne dwie i sklejamy pierwszą parę i osobno drugą parę, uzyskując w ten sposób 10 nieidentycznych kulek. Te kulki musimy z kolei rozożyć w 365 kubkach - po jednej na kubek.

Policzmy wszystkie elementy tego modelu pokolei. 2 kulko z 12

$$ 12\choose{2}$$

2 kulki z pozostałych 10

$$10\choose{2}$$

rozłożenie 10 kulek (z których dwie mają dwa nazwiska) w 365 kubkach

$$\frac{365!}{(365-10)!}$$

Wydaje się, że już mamy wszystko, ale jeszcze nie możemy mnożyć, bo pojawia się dodatkowy element. Powiedzmy, że za pierwszym razem wylosowaliśmy Jasia i Małgosię spośród 12 kulek a następnie, spośród pozostałych 10, Lolka i Bolka. Za drugim razem, najpierw wylosowaliśmy Lolka i Bolka a za drugim, spomiędzy 10 kulek, Jasia i Małgosię. Te losowania doprowadzą do dokładnie tych samych konfiguracji, więc musimy część z nich usunąć, mnożąc w tym przypadku przez $\frac{1}{2!}$. Zwróćmy uwagę, że w przypadku 3 losowań poprawka wyniesie $\frac{1}{3}$ (permutacje).

Ostatecznie liczba konfiguracji z dwiema parami to

$${12\choose{2}} {10\choose{2}} \frac{1}{2!}\times\frac{365!}{(365-10)!} $$

Teraz możemy już wypisać liczbę konfiguracji z dwiema lub jedną kulką w każdym kubuku: $$n = \frac{365!}{(365-12)!} + $$ $${12\choose{2}}\times\frac{365!}{(365-11)!} + $$ $${12\choose{2}}{10\choose{2}}\frac{1}{2!}\times\frac{365!}{(365-10)!} +$$ $${12\choose{2}} {10\choose{2}} {8\choose{2}}\frac{1}{3!}\times\frac{365!}{(365-9)!}+$$ $${12\choose{2}}{10\choose{2}}{8\choose{2}}{6\choose{2}}\frac{1}{4!}\times\frac{365!}{(365-8)!} +$$ $${12\choose{2}}{10\choose{2}}{8\choose{2}}{6\choose{2}}{4\choose{2}}\frac{1}{5!}\times\frac{365!}{(365-7)!}+$$ $${12\choose{2}}{10\choose{2}}{8\choose{2}}{6\choose{2}}{4\choose{2}}{2\choose{2}}\frac{1}{6!}\times\frac{365!}{(365-6)!}$$

Jeżeli odejmiemy tę liczbę od $365^{12}$ i podzielimy wynik przez $365^{12}$ otrzymamy poprawne prawdopodobieństwo trzech lub więcej urodzin tego samego dnia. Nasze obliczenia możemy sprawdzić przy pomocy darmowego systemu do obliczeń symbolicznych Maxima :

(%i1) 1-float(
   (365!/(365-12)!+
   binomial(12, 2)*365!/(365-11)!+
   binomial(12, 2)*binomial(10,2)*365!/(365-10)!* 1/2! +
   binomial(12, 2)*binomial(10,2)*binomial(8, 2)*365!/(365-9)!* 1/3! +
   binomial(12, 2)*binomial(10,2)*binomial(8, 2)*binomial(6, 2) * 365!/(365-8)! * 1/4! +
   binomial(12, 2)*binomial(10,2)*binomial(8, 2)*binomial(6, 2) * binomial(4, 2)* 365!/(365-7)! * 1/5! +
   binomial(12, 2)*binomial(10,2)*binomial(8, 2)*binomial(6, 2) * binomial(4, 2)* 365!/(365-6)! *1/6!)/365^12
);
(%o1) 0.001620563039933187

czyli wynik zgodny jest z symulacją w R z początku artykułu.

Wydaje się że rekurencyjny wzór w zwartej postaci dla przypadku ogólnego również da się wyprowadzić, pod warunkiej że mamy, cytując Matematykę Konkretną, do dyspozycji “jasny umysł, ogromną kartkę papieru i w miarę czytelny charakter pisma”.