Odwrotny problem urodzinowy z wieloma kolizjami

9

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.

Techhead
źródło
3
Moja odpowiedź na specjalną wersję tego pytania łatwo uogólnia (używając dystrybucji wielomianowej): patrz stats.stackexchange.com/questions/252813 .
whuber
@Techhead Na różne sposoby! Oczywistym podejściem do oszacowania parametru, o którym należy wspomnieć, byłoby maksymalne prawdopodobieństwo.
Glen_b
1
Możliwy duplikat problemu
Stephan Kolassa
1
@ whuber Widziałem to pytanie i twój komentarz, ale nie widziałem, jak zastosować większość z nich do próbki o znanych kolizjach. Nie jest trudno znaleźć rozwiniętą formę, ale nie wiem, jak znaleźć sumę logarytmiczną.
Techhead
1
Zgadzam się, że twoja wersja jest na tyle bardziej skomplikowana, że ​​nie powinna być zamykana jako duplikat.
whuber

Odpowiedzi:

2

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, gdzieE(X)=pixiNE(N)=n=0pnnpn=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 naqnn.qnqnnqnpn.

Jeśli założymy, że jest proporcjonalny do , toPonieważ , iDlatego potrzebujemy tylko wzoru na aby rozwiązać ten problem.pnqnpn=αqn.n=0pn=1αn=0qn=1α=1n=0qn.qn

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.nn1n(n1)(n2)...(n83)n(n1)(n2)...(n8452+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(911)(912)...(917+1)76

rn=n(n1)...(n8452+1)(84+5+2)(84+5+21)...(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 .abca,b,cnmqn=rnnm

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ćrnyn=n(n1)...(n(a+b+c)+1)=n!(n(a+b+c))!znrnrn=ynznznzn=zpn=qn/i=0qiqn=zynnmzpn=ynnm/i=0(yiim)yndalej, jeśli pozwolimy (lub można to uznać za liczbę unikalnych urodzin w grupie kosmitów), aby uzyskać:s=a+b+c

pn=n!(ns)!nm/i=0(i!(is)!im)

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 .pnE(N)P(N=n)qnN=nP(N=n)E(N)pnn

Cody Maughan
źródło
Wygląda na to, że proponujesz obliczyć wartość oczekiwaną na podstawie funkcji prawdopodobieństwa zamiast funkcji masy prawdopodobieństwa. Czy to było zamierzone?
Sextus Empiricus
2

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 .NN

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ównea+2b+3cnabc

rn=(na+b+c)number of ways topick m unique birthdaysout of n days(a+b+c)!a!b!c!number of ways todistribute m birthdaysamong groups of size ab and c(a+2b+3c)!1!a2!b3!cnumber of ordered ways toarrange specific single, duplicate, and triplicatesamong the aliens =n!(nabc)!×(a+2b+3c)a!b!c!1!a2!b3!c

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ństwan

L(n|a,b,c)=n(a+2b+3c)n!(nabc)!=nmn!(ns)!P(a,b,c|n)

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


Oszacowanie maksymalnego prawdopodobieństwa dla N

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

Zauważ, że

L(n)=L(n1)(n1n)mnns

a maksimum pojawi się tuż przed dla któregon

(n1n)mnns=1

lub

s=n(1(11/n)m)

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 )nx=1/nxx=0

sk=0l(mk)(n)k+O(n(l+1))

Używając tylko terminu pierwszego rzędu otrzymujesz:smm(m1)2n

n1(m2)ms

Wykorzystując drugie określenie kolejności, jak również uzyskać :smm(m1)2n+m(m1)(m2)6n2

n2(m2)+(m2)24(ms)(m3)2(ms)

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=100s=91n1550n2515.1215n=516.82n=516

porównanie przybliżenia z prawdziwym MLE

Sextus Empiricus
źródło