Odwrotny problem urodzinowy z wieloma kolizjami

Załóżmy, że miałeś rok obcy o nieznanej długości N. Jeśli masz losową próbkę wspomnianych kosmitów, a niektórzy z nich dzielą urodziny, czy możesz użyć tych danych do oszacowania długości roku?

Na przykład, w próbie 100, możesz mieć dwie trojaczki (tj. Dwa urodziny, z których każdy dzieli trzech kosmitów) oraz pięć par i osiemdziesiąt cztery singletony. Przy szacowaniu N absolutne minimum wynosi 91, a maksimum jest nieograniczone, ale jak znaleźć rozsądną oczekiwaną wartość?

Założenia obejmują takie rzeczy, jak „wszystkie urodziny są jednakowo prawdopodobne”.

W przeciwieństwie do innego pytania, na które udzielono odpowiedzi, w pokoju są znane kolizje. Każdy wystarczająco długi rok będzie miał duże prawdopodobieństwo braku kolizji dla pokoju kosmitów. Ale bardzo długie lata będą miały małe szanse na jakiekolwiek kolizje, a krótkie lata będą miały małe szanse na kilka kolizji, zapewniając w ten sposób (teoretyczny) zakres dla najbardziej prawdopodobnych długości roku.

Wartość oczekiwaną rozkładu oblicza się jako . W przypadku tego problemu chcemy obliczyć rozkład przy pewnych kryteriach kolizji lub znaleźć przy pewnych kryteriach kolizji, gdzie$E(X) = \sum {p_ix_i}$$N$$E(N) = \sum_{n=0}^{\infty}p_n n$$p_n=P(N=n).$

Załóżmy, że masz pewne kryteria kolizji, jak podano powyżej, i niech będzie prawdopodobieństwem, że kryteria kolizji zostaną spełnione, biorąc pod uwagę, że długość roku wynosiNastępnie można znaleźć, dzieląc po prostu liczbę sposobów spełnienia kryteriów kolizji przez ogólną liczbę sposobów zorganizowania urodzin. Po dla każdego możliwego , jedynym brakującym elementem jest tłumaczenie na$q_n$$n.$$q_n$$q_n$$n$$q_n$$p_n.$

Jeśli założymy, że jest proporcjonalny do , toPonieważ , iDlatego potrzebujemy tylko wzoru na aby rozwiązać ten problem.$p_n$$q_n$$p_n= \alpha q_n.$$\sum_{n=0}^{\infty} p_n=1$$\alpha \sum_{n=0}^{\infty} q_n=1$$\alpha=\frac{1}{\sum_{n=0}^{\infty} q_n}.$$q_n$

Na przykład, pozwól nam najpierw znaleźć liczbę sposobów spełnienia kryteriów kolizji, biorąc pod uwagęPierwszy obcy singleton może wylądować każdego dnia, więc nie ma możliwości. Następny singleton może wylądować każdego dnia oprócz urodzin pierwszego kosmity, więc istnieje możliwości. Wykonując to dla pierwszych 84 singletonów, otrzymujemy możliwych sposobów, aby to się wydarzyło. Zauważ, że mamy również 5 par i 2 trojaczki, więc „pierwszy” kosmita dla każdej grupy nie może też wylądować na parach singletonów. Prowadzi to do sposobów, w jakie ci kosmici nie kolidują (niezdarna składnia jest łatwiejsza do uogólnienia później).$N=n.$$n$$n-1$$n(n-1)(n-2)...(n-83)$$n(n-1)(n-2)...(n-84-5-2 + 1)$

Następnie drugi kosmita dla danej pary lub trojaczki ma 91 wyborów, następny ma 90 itd., Łączna liczba sposobów, jakie mogą się wydarzyć, biorąc pod uwagę urodziny pierwszych 91 kosmitów, wynosi . Pozostali członkowie trojaczków muszą upaść na urodziny par, a prawdopodobieństwo takiego zdarzenia wynosi . Mnożymy prawdopodobieństwa dla nich wszystkich razem, aby uzyskać całkowitą liczbę możliwych sposobów spełnienia kryteriów kolizji jako:$91(91-1)(91-2)...(91-7+1)$$7*6$

$$r_n=n(n-1)...(n-84-5-2+1)(84+5+2)(84+5+2-1)...(84+1)(5+2)(5+1)$$

W tym momencie, wzór jest jasne, czy mamy pojedynczych, pary i trypletów zastąpić 84 z 5 z i 2 z , aby uzyskać wzorze ogólnym. Myślę, że jasne jest również, że ogólna liczba możliwych sposobów na zorganizowanie urodzin to , gdzie m jest całkowitą liczbą obcych w problemie. Dlatego prawdopodobieństwo spełnienia kryteriów kolizji to liczba sposobów spełnienia kryteriów kolizji podzielona przez liczbę sposobów, w jakie kosmici mogą się urodzić, lub .$a$$b$$c$$a,$$b,$$c$$n^m$$q_n=\frac{r_n}{n^m}$

Kolejna interesująca rzecz pojawiła się we wzorze . Niech , I niech być pozostałą częścią , aby . Zauważ, że jest niezależne od n, więc możemy po prostu zapisać jako stałą! Ponieważ , a , możemy faktycznie z sumy w mianowniku. W tym momencie anuluje się z częścią licznika, aby uzyskać . Możemy uprościć$r_n$$y_n=n(n-1)...(n-(a+b+c)+1)=\frac{n!}{(n-(a+b+c))!}$$z_n$$r_n$$r_n=y_nz_n$$z_n$$z_n=z$$p_n=q_n/\sum_{i=0}^\infty q_i$$q_n=\frac{zy_n}{n^m}$$z$$p_n=\frac{y_n}{n^m}/\sum_{i=0}^\infty (\frac{y_i}{i^m})$$y_n$dalej, jeśli pozwolimy (lub można to uznać za liczbę unikalnych urodzin w grupie kosmitów), aby uzyskać:$s=a+b+c$

$$p_n=\frac{\frac{n!}{(n-s)!}}{n^m}/\sum_{i=0}^\infty (\frac{\frac{i!}{(i-s)!}}{i^m})$$

Teraz mamy (dość) prosty wzór na , a zatem (dość) prosty wzór na , gdzie jedynym założeniem było to, że jest proporcjonalne do (prawdopodobieństwo spełnienia zderzenia kryteria, biorąc pod uwagę, że ). Myślę, że jest to słuszne założenie, a ktoś mądrzejszy ode mnie może nawet udowodnić, że założenie to jest powiązane z po rozkładzie wielomianowym. W tym momencie możemy obliczyć za pomocą metod numerycznych lub przyjąć pewne założenia aproksymacyjne, ponieważ zbliży się do 0, gdy zbliży się do .$p_n$$E(N)$$P(N=n)$$q_n$$N=n$$P(N=n)$$E(N)$$p_n$$n$$\infty$

Doskonała odpowiedź od Cody zapewnia miły sposób wyrazić funkcję wiarogodności dla , to liczba dni w roku (lub tylnego dystrybucja oparta na płaskiej przed) przez faktoringu z jakiejś części prawdopodobieństwa, który jest niezależny od .$N$$N$

W tej odpowiedzi chciałbym zapisać to bardziej zwięźle, a także zapewnić sposób na obliczenie maksimum tej funkcji prawdopodobieństwa (zamiast oczekiwanej wartości, która jest znacznie trudniejsza do obliczenia).

---

Funkcja prawdopodobieństwa dla N

Liczba sposobów narysowania sekwencji urodzin z zestawu urodzin, z zastrzeżeniem, że jest liczbą pojedynczych urodzin, zduplikowanych urodzin, a potrójnych urodzin jest równe$a+2b+3c$$n$$a$$b$$c$

$$\begin{array}{ccl} r_n &=& \underbrace{{n}\choose{a+b+c}}_{\small\begin{array}{ccc}&\text{number of ways to} &\\ &\text{pick $m$ unique birthdays}& \\ &\text{out of $n$ days}&\end{array}} \underbrace{\frac{(a+b+c)!}{a!b!c!}}_{\small\begin{array}{ccc}&\text{number of ways to} &\\ &\text{distribute $m$ birthdays}& \\ &\text{among groups of size $a$, $b$ and $c$}&\end{array}} \underbrace{\frac{(a+2b+3c)!}{1!^a2!^b3!^c}}_{\small\begin{array}{ccc}&\text{number of ordered ways to} &\\ &\text{arrange specific }& \\&\text{single, duplicate, and triplicates}& \\ &\text{among the aliens }&\end{array}} \\ &=& \frac{n!}{(n-a-b-c)!} \times \frac{(a+2b+3c)}{a!b!c!1!^a2!^b3!^c} \end{array}$$

i tylko pierwszy termin po prawej stronie jest zależny od , więc biorąc pod uwagę pozostałe terminy, kończymy prostym wyrażeniem funkcji prawdopodobieństwa$n$

$$\begin{array}{rcl} \mathcal{L}(n|a,b,c) &=& n^{-(a+2b+3c)} \frac{n!}{(n-a-b-c)!} = n^{-m} \frac{n!}{(n-s)!}\\ & \propto & P(a,b,c|n) \end{array}$$

gdzie podążamy za zapisem Cody i używamy do oznaczenia liczby kosmitów, a liczby unikalnych urodzin.$m$$s$

---

Oszacowanie maksymalnego prawdopodobieństwa dla N

Możemy użyć tej funkcji wiarogodności dla uzyskania maksymalnej oszacowania prawdopodobieństwa dla .$N$

Zauważ, że

$$\mathcal{L}(n) = \mathcal{L}(n-1) \left(\frac{n-1}{n}\right)^m\frac{n}{n-s}$$

a maksimum pojawi się tuż przed dla którego$n$

$$\left(\frac{n-1}{n}\right)^m\frac{n}{n-s} = 1$$

lub

$$s = n \left(1-\left(1-1/n\right)^m \right)$$

który jest dla dużej przybliżeniu (przy użyciu szeregu Laurenta, który można znaleźć, podstawiając i napisz szereg Taylora dla w punkcie )$n$$x = 1/n$$x$$x=0$

$$s \approx \sum_{k=0}^l {{m}\choose{k}} (-n)^{-k} + \mathcal{O} \left( n^{-(l+1)} \right)$$

Używając tylko terminu pierwszego rzędu otrzymujesz:$s \approx m - \frac{m(m-1)}{2 n}$

$$n_1 \approx \frac{ {{m}\choose{2}}}{m-s}$$

Wykorzystując drugie określenie kolejności, jak również uzyskać :$s \approx m - \frac{m(m-1)}{2 n} + \frac{m(m-1)(m-2)}{6 n^2}$

$$n_2 \approx \frac{ {{m}\choose{2}} + \sqrt{{{m}\choose{2}}^2- 4 (m-s){{m}\choose{3}} } }{2(m-s)}$$

Tak więc w przypadku kosmitów, wśród których jest niepowtarzalnych urodzin, otrzymujesz przybliżenie i . Gdy rozwiążesz równanie numerycznie, otrzymasz które zaokrąglamy w dół do aby uzyskać MLE.$m=100$$s=91$$n_1 \approx 550$$n_2 \approx 515.1215$$n=516.82$$n=516$