Umgekehrtes Geburtstagsproblem mit mehreren Kollisionen

Angenommen, Sie hatten ein außerirdisches Jahr mit einer unbekannten Länge N. Wenn Sie eine zufällige Stichprobe dieser Außerirdischen haben und einige von ihnen Geburtstage teilen, können Sie diese Daten verwenden, um die Länge des Jahres zu schätzen?

In einer Stichprobe von 100 könnten Sie beispielsweise zwei Drillinge (dh zwei Geburtstage, die jeweils von drei Außerirdischen geteilt werden) und fünf Paare und vierundachtzig Singletons haben. Bei der Schätzung von N beträgt das absolute Minimum 91 und das Maximum ist unbegrenzt. Wie würde ich jedoch einen angemessenen erwarteten Wert finden?

Zu den Annahmen gehören Dinge wie "Alle Geburtstage sind gleich wahrscheinlich".

Im Gegensatz zu einer anderen hier beantworteten Frage sind Kollisionen im Raum bekannt. In einem ausreichend langen Jahr besteht eine hohe Wahrscheinlichkeit, dass keine Kollisionen für einen Raum von Außerirdischen auftreten. Sehr lange Jahre haben jedoch eine geringe Wahrscheinlichkeit für Kollisionen, und kurze Jahre haben eine geringe Wahrscheinlichkeit für wenige Kollisionen, wodurch ein (theoretischer) Bereich für die wahrscheinlichsten Jahreslängen bereitgestellt wird.

estimation inference birthday-paradox Techhead
quelle

Meine Antwort auf eine spezielle Version dieser Frage lässt sich leicht verallgemeinern (unter Verwendung der Multinomialverteilung): siehe stats.stackexchange.com/questions/252813 .

whuber

@ Techhead Auf verschiedene Arten! Der naheliegende Ansatz für die Parameterschätzung wäre die maximale Wahrscheinlichkeit.

Glen_b -Reinstate Monica

Mögliches Duplikat von Ein umgekehrtes Geburtstagsproblem: Kein Paar von 1 Million Außerirdischen hat Geburtstag. Was ist ihre Jahreslänge?

Stephan Kolassa

@whuber Ich habe diese Frage und Ihren Kommentar gesehen, aber ich habe nicht gesehen, wie ich das meiste davon auf eine Probe mit bekannten Kollisionen anwenden kann. Es ist nicht schwer, die erweiterte Form zu finden, aber ich weiß nicht, wie ich die logarithmische Summe finden würde.

Techhead

Ich bin damit einverstanden, dass Ihre Version so kompliziert ist, dass sie nicht als Duplikat geschlossen werden sollte.

whuber

Antworten:

Der Erwartungswert einer Verteilung wird berechnet als . Für dieses Problem wollen wir die Verteilung von bei bestimmten Kollisionskriterien berechnen oder bei bestimmten Kollisionskriterien finden, wobei $E(X) = \sum {p_ix_i}$ $N$ $E(N) = \sum_{n=0}^{\infty}p_n n$ $p_n=P(N=n).$

Angenommen, Sie haben einige Kollisionskriterien wie oben angegeben, und ist die Wahrscheinlichkeit, dass die Kollisionskriterien erfüllt sind, wenn die Länge des Jahres beträgtDann kann gefunden werden, indem einfach die Anzahl der Möglichkeiten, wie die Kollisionskriterien erfüllt werden können, durch die Anzahl der Möglichkeiten geteilt wird, wie Geburtstage im Allgemeinen angeordnet werden können. Sobald für jedes mögliche , fehlt nur noch die Übersetzung von in $q_n$ $n.$ $q_n$ $q_n$ $n$ $q_n$ $p_n.$

Wenn wir annehmen, dass proportional zu , dann istDa , ist undDaher brauchen wir nur eine Formel für , um dieses Problem zu lösen. $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$

Lassen Sie uns für Ihr Beispiel zunächst die Anzahl der Möglichkeiten ermitteln, wie die Kollisionskriterien beiDer erste außerirdische Singleton kann an jedem Tag landen, es gibt also Möglichkeiten. Der nächste Singleton kann an jedem Tag außer dem Geburtstag des ersten Aliens landen, daher gibt es Möglichkeiten. Wenn wir dies für die ersten 84 Singletons vervollständigen, erhalten wir mögliche Wege, wie dies geschehen kann. Beachten Sie, dass wir auch 5 Paare und 2 Drillinge haben, sodass der "erste" Alien für jede Gruppe auch nicht auf den Singleton-Paaren landen darf. Dies führt zu einer Art und Weise, wie diese Aliens nicht kollidieren (die ungeschickte Syntax dient später zur leichteren Verallgemeinerung). $N=n.$ $n$ $n-1$ $n(n-1)(n-2)...(n-83)$ $n(n-1)(n-2)...(n-84-5-2 + 1)$

Als nächstes hat der zweite Alien für ein bestimmtes Paar oder Triplett 91 Auswahlmöglichkeiten, der nächste hat 90 usw. Die Gesamtzahl der Möglichkeiten, wie dies bei den Geburtstagen der ersten 91 Aliens geschehen kann, beträgt . Die verbleibenden Mitglieder der Drillinge müssen auf die Geburtstage der Paare fallen, und die Wahrscheinlichkeit dafür liegt bei . Wir multiplizieren die Wahrscheinlichkeiten für diese alle zusammen, um eine Gesamtzahl möglicher Wege zu erhalten, wie die Kollisionskriterien erfüllt werden können: $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)

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

An diesem Punkt ist das Muster klar, wenn wir Singletons, Paare und Tripletts, ersetzen wir 84 mit 5 mit und 2 mit eine verallgemeinerte Formel zu erhalten. Ich denke, es ist auch klar, dass die Anzahl der möglichen Arten, die Geburtstage im Allgemeinen , , wobei m die Gesamtzahl der Außerirdischen in dem Problem ist. Daher ist die Wahrscheinlichkeit, die Kollisionskriterien zu erfüllen, die Anzahl der Möglichkeiten, die Kollisionskriterien zu erfüllen, geteilt durch die Anzahl der Möglichkeiten, wie die Außerirdischen geboren werden könnten, oder . $a$ $b$ $c$ $a,$ $b,$ $c$ $n^m$ $q_n=\frac{r_n}{n^m}$

Eine andere interessante Sache erschien in der Formel von . Sei Und sei sei der verbleibende Teil von so dass . Beachten Sie, dass unabhängig von n ist, also können wir einfach als Konstante schreiben ! Da und , können wir tatsächlich Faktor aus der Summe in dem Nenner. Zu diesem Zeitpunkt wird es mit dem Teil vom Zähler abgebrochen, um . Wir können vereinfachen $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$ weiter, wenn wir (oder dies kann als die Anzahl der eindeutigen Geburtstage in der Gruppe der Außerirdischen angesehen werden), so dass wir erhalten: $s=a+b+c$

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

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

Jetzt haben wir eine (ziemlich) einfache Formel für und daher eine (ziemlich) einfache Formel für , wobei nur angenommen wurde, dass proportional zu (die Wahrscheinlichkeit, die Kollision zu treffen) Kriterien gegeben, dass ). Ich denke, dies ist eine faire Annahme, und jemand, der klüger als ich ist, kann möglicherweise sogar beweisen, dass diese Annahme nach einer multinomialen Verteilung mit . An diesem Punkt können wir mit numerischen Methoden berechnen oder einige Näherungsannahmen treffen, da sich 0 nähert, wenn sich nähert . $p_n$ $E(N)$ $P(N=n)$ $q_n$ $N=n$ $P(N=n)$ $E(N)$ $p_n$ $n$ $\infty$

Cody Maughan
quelle

Es scheint, als würden Sie vorschlagen, den Erwartungswert auf der Grundlage einer Wahrscheinlichkeitsfunktion und nicht einer Wahrscheinlichkeitsmassenfunktion zu berechnen. War das beabsichtigt?

Sextus Empiricus

Die ausgezeichnete Antwort von Cody bietet eine gute Möglichkeit, die Wahrscheinlichkeitsfunktion für , die Anzahl der Tage im Jahr (oder die hintere Verteilung basierend auf einem flachen Prior) auszudrücken, indem ein Teil der Wahrscheinlichkeit herausgerechnet wird, die von unabhängig ist . $N$ $N$

In dieser Antwort möchte ich es genauer aufschreiben und auch eine Möglichkeit bieten, das Maximum dieser Wahrscheinlichkeitsfunktion zu berechnen (und nicht den erwarteten Wert, der viel schwieriger zu berechnen ist).

Wahrscheinlichkeitsfunktion für N.

Die Anzahl der Möglichkeiten, eine Folge von Geburtstagen aus einer Menge von Geburtstagen zu ziehen, mit der Einschränkung, dass die Anzahl der einzelnen Geburtstage, doppelten Geburtstage und dreifachen Geburtstage ist, ist gleich $a+2b+3c$ $n$ $a$ $b$ $c$

\begin{array}{ccl} r_{n} & = & \underset{\begin{array}{ccc} number of ways to \\ pick m unique birthdays \\ out of n days \end{array}}{\underset{⏟}{(\binom{n}{a + b + c})}} \underset{\begin{array}{ccc} number of ways to \\ distribute m birthdays \\ among groups of size a, b and c \end{array}}{\underset{⏟}{\frac{(a + b + c)!}{a! b! c!}}} \underset{\begin{array}{ccc} number of ordered ways to \\ arrange specific \\ single, duplicate, and triplicates \\ among the aliens \end{array}}{\underset{⏟}{\frac{(a + 2 b + 3 c)!}{1!^{a} 2!^{b} 3!^{c}}}} \\ = & \frac{n!}{(n - a - b - c)!} \times \frac{(a + 2 b + 3 c)}{a! b! c! 1!^{a} 2!^{b} 3!^{c}} \end{array}

$\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}$

und nur der erste Term auf der rechten Seite ist von abhängig. wir also die anderen Terme enden wir mit einem einfachen Ausdruck für eine Wahrscheinlichkeitsfunktion $n$

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

$\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}$

wo wir der Notation von Cody folgen und , um die Anzahl der Außerirdischen und die Anzahl der eindeutigen Geburtstage zu bezeichnen. $m$ $s$

Maximale Wahrscheinlichkeitsschätzung für N.

Wir können diese Wahrscheinlichkeitsfunktion verwenden, um die maximale Wahrscheinlichkeitsschätzung für abzuleiten . $N$

Beachten Sie, dass

L (n) = L (n - 1) {(\frac{n - 1}{n})}^{m} \frac{n}{n - s}

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

und das Maximum wird kurz vor dem für das $n$

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

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

oder

s = n (1 - {(1 - 1 / n)}^{m})

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

Dies ist ungefähr für großes (unter Verwendung einer Laurent-Reihe, die Sie finden können, indem Sie und die Taylor-Reihe für in den Punkt schreiben ). $n$ $x = 1/n$ $x$ $x=0$

s \approx \sum_{k = 0}^{l} (\binom{m}{k}) (- n)^{- k} + O (n^{- (l + 1)})

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

Wenn Sie nur den Term erster Ordnung Sie: $s \approx m - \frac{m(m-1)}{2 n}$

n_{1} \approx \frac{(\binom{m}{2})}{m - s}

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

Unter Verwendung der Term zweiter Ordnung als auch Sie bekommen , :: $s \approx m - \frac{m(m-1)}{2 n} + \frac{m(m-1)(m-2)}{6 n^2}$

n_{2} \approx \frac{(\binom{m}{2}) + \sqrt{{(\binom{m}{2})}^{2} - 4 (m - s) (\binom{m}{3})}}{2 (m - s)}

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

Im Fall von Außerirdischen, unter denen es eindeutige Geburtstage gibt, erhalten Sie die Näherung und . Wenn Sie die Gleichung numerisch lösen, erhalten Sie die wir auf , um die MLE zu erhalten. $m=100$ $s=91$ $n_1 \approx 550$ $n_2 \approx 515.1215$ $n=516.82$ $n=516$

Sextus Empiricus
quelle