Odwrotny problem urodzinowy: żadna para z 1 miliona kosmitów nie ma urodzin; jaka jest ich długość roku?

Załóżmy, że planeta ma bardzo długi rok dni. Na przyjęciu w pokoju przebywa 1 milion kosmitów i nikt nie obchodzi urodzin. Co można wywnioskować o rozmiarze ? $N$ $N$

(To bardziej zwięzłe pytanie zastępuje to źle sformułowane ).

probability birthday-paradox

— Paweł Uszak
źródło

Problem związany z urodzinami informuje o wartości N, gdzie prawdopodobieństwo co najmniej jednego dopasowania jest większe niż określona wartość. Gdy p = 1/2 zaskakuje intuicja, że daje to n = 23 .. Zakłada się, że każde urodziny mają takie samo jednolite prawdopodobieństwo (1/365). Nonuniformity tylko n zmniejsza. Teraz w twoim problemie wydaje się, że N zastępuje 365 i zakładam, że założono jednolitość.

— Michael R. Chernick,

Jeśli N <= 1 000 000, to co najmniej 1 dopasowanie ma prawdopodobieństwo = 1, a więc 0 dopasowań ma prawdopodobieństwo = 0.

— Michael R. Chernick,

Tak więc, gdy N> 1.000.000 prawdopodobieństwo co najmniej 1 dopasowania ma prawdopodobieństwo <1, a zatem prawdopodobieństwo zerowych dopasowań zaczyna rosnąć.

— Michael R. Chernick,

@Michael Proszę rezerwować komentarze do próśb o wyjaśnienia i inne przypadkowe dyskusje, i starać się publikować tylko jedną na raz: istnieje dobry powód ograniczenia liczby znaków. Jeśli omawiasz coś istotnego, co wymaga wielu komentarzy, prawdopodobnie próbujesz odpowiedzieć na pytanie, więc równie dobrze możesz opublikować odpowiedź.

— whuber

$k+1$

p (k; N) = 1 (1 - \frac{1}{N}) (1 - \frac{2}{N}) \dots (1 - \frac{k}{N}) .

$p(k;N) = 1\left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right)\cdots\left(1-\frac{k}{N}\right).$

$k$ $N$

\begin{matrix} (1) & \log (p (k; N)) = - \frac{k (k + 1)}{2 N} - \frac{k + 3 k^{2} + 2 k^{3}}{12 N^{2}} - O (k^{4} N^{- 3}) . \end{matrix}

$\log(p(k;N)) = -\frac{k(k+1)}{2N} - \frac{k + 3k^2 + 2k^3}{12N^2} - O(k^4 N^{-3}).\tag{1}$

$100-100\alpha\%$ $N$ $N^{*}$ $(1)$ $\log(1-\alpha)$ $\alpha$ $N$ $k$ $(1)$ $-k^2/(2N)$

- \frac{k^{2}}{2 N} > \log (1 - α),

$-\frac{k^2}{2N} \gt \log(1-\alpha),$

sugerując

\begin{matrix} (2) & N > \frac{- k^{2}}{2 \log (1 - α)} \approx \frac{k^{2}}{2 α} = N^{*} \end{matrix}

$N \gt\frac{-k^2}{2\log(1-\alpha)} \approx \frac{k^2}{2\alpha}=N^{*}\tag{2}$

$\alpha$

$k=10^6-1$ $\alpha=0.05$ $95\%$ $(2)$ $N \gt 10^{13}$

$(2)$ $N=9.74786\times 10^{12}$ $N$ $p(10^6-1, 9.74786\times 10^{12})=95.0000\ldots\%$ $95\%$ $N$ $95\%$ $N$ $100 - 95= 5\%$ $N$

$4\%$ $k=6$ $5.6\%$ $k=7$ $N$ $360$ $490$ $366$ $k$ $\alpha$

— Whuber
źródło

Nie byłem przygotowany na udzielenie takiej odpowiedzi. W przypadku liczb takie duże przybliżenia mogą być łatwiejsze do obliczenia. Wikipedia podaje ogólny problem związany z urodzinami, pokazując przybliżenia i granice N dla k osób (kosmitów). Miałem tę samą formułę, co twoje pierwsze równanie.

— Michael R. Chernick,

Moje pytanie brzmi: jak duże musi być N, aby osiągnąć 100% pewności. Myślę, że to coś w rodzaju 10 ^ 18.

— Michael R. Chernick,

@MichaelChernick Za 100% pewności N idzie w nieskończoność. Dla każdego skończonego roku i każdej partii z 2 lub więcej kosmitami prawdopodobieństwo dwóch kosmitów z tymi samymi urodzinami jest zawsze większe niż 0.

— Pere

@Pere Tak, dziękuję za obejrzenie tego. Naprawię to od razu. Nie miało to znaczenia dla reszty postu.

— whuber

@Paul Uszak Myślę, że twój komentarz na temat odpowiedzi Pere (teraz usunięty) był zbyt surowy. Myślę, że jego odpowiedź została udzielona w dobrej wierze. Próbował ci pomóc, podając przydatne przybliżenia. Później zobaczył odpowiedź Whubera i uznał, że jest ona bardziej kompletna, i zgodził się usunąć swoją odpowiedź. Jego komentarz o tym, że nie spodziewał się szczegółowej odpowiedzi, nie miał na myśli tego, jak ją interpretowałeś. To trudny problem. Trzeba było nawet przepisać post, aby był zrozumiały. Jestem pewien, że nie traktuje rozwiązania takiego problemu jako żartu.

— Michael R. Chernick,