Mezcla de distribuciones binomiales negativas (técnicamente algunas de ellas son geométricas)

Question

Tengo algo que estoy tratando de calcular.

Digamos que un número se genera uniformemente de 1 a 4.

¿Cuál sería el número esperado de generaciones necesarias para obtener al menos 3 1s y que todos los demás números se generen al menos una vez?

Sé cómo calcular al menos 3 1s ya que sería una distribución binomial negativa con p=3/4 y r=3.

Sé cómo calcular al menos que cada número aparezca una vez, ya que son distribuciones geométricas (o binomial negativa con r=1).

¿Cómo puedo unir estos conceptos para obtener un valor esperado?

Answer 1

Esto es una generalización de el problema del coleccionista de cupones . Los dos enfoques que se pueden adoptar al respecto se utilizan en las dos respuestas en Problema de cobro de cupones: $4$ cupones con $p_1 = p_2 = \frac{1}{8}$ y $p_3 = p_4 = \frac{3}{8}$ .

En el espíritu de la respuesta de Ross, se puede definir un estado $(j,k)$ avec $0\le j,k\le3$ en el que has generado $j$ $1$ s y $k$ de los otros números al menos una vez. Entonces el número esperado $a_{jk}$ de las generaciones restantes satisface la recurrencia

$$ a_{jk}=1+\frac14a_{j+1,k}+\frac k4a_{jk}+\frac{3-k}4a_{j,k+1}\;, $$

donde los índices no se incrementan más allá de $3$ y el valor inicial es $a_{33}=0$ . El resultado es

\begin{array}{c|cccc} j\setminus k&0&1&2&3\\\hline 0&\frac{1915}{144}&\frac{349}{27}&\frac{25}2&12\\ 1&\frac{125}{12}&\frac{88}9&9&8\\ 2&\frac{25}3&\frac{22}3&6&4\\ 3&\frac{22}3&6&4&0\\ \end{array}

Así, el número esperado de generaciones es $a_{00}=\frac{1915}{144}\approx13.3$ .

En el espíritu de mi respuesta, podemos aplicar inclusión-exclusión a las cuatro condiciones $A_i$ que has generado $i$ un número suficiente de veces ( $3$ para $i=1$ y $1$ en caso contrario). Sea $N_i$ denotan el número de generaciones necesarias hasta $A_i$ se cumpla, y que $N=\max_iN_i$ denotan el número de generaciones necesarias hasta que todas las condiciones $A_i$ se cumplen. Entonces

\begin{eqnarray*} \mathsf E[N] &=& \sum_{n=0}^\infty\mathsf P(N\gt n) \\ &=& \sum_{n=0}^\infty\mathsf P\left(\bigvee_{i\in\{1,2,3,4\}}N_i\gt n\right) \\ &=& \sum_{n=0}^\infty\sum_{\emptyset\ne S\subseteq\{1,2,3,4\}}(-1)^{|S|+1}\mathsf P\left(\bigwedge_{i\in S}N_i\gt n\right)\;. \end{eqnarray*}

Ahora hay dos casos. Si $1\notin S$ tenemos

$$ \mathsf P\left(\bigwedge_{i\in S}N_i\gt n\right)=4^{-n}(4-|S|)^n\;. $$

Si $1\in S$ tenemos

$$ \mathsf P\left(\bigwedge_{i\in S}N_i\gt n\right)=\sum_{j=0}^2\binom nj4^{-n}(4-|S|)^{n-j}\;. $$

Dividiendo la suma entre $S$ en estos dos casos, obtenemos

\begin{eqnarray*} \sum_{n=0}^\infty\sum_{\emptyset\ne S\subseteq\{2,3,4\}}(-1)^{|S|+1}\mathsf P\left(\bigwedge_{i\in S}N_i\gt n\right) &=& \sum_{n=0}^\infty\sum_{k=1}^3(-1)^{k+1}\binom3k4^{-n}(4-k)^n \\ &=& \sum_{k=1}^3(-1)^{k+1}\binom3k\frac4k \\ &=& 12-6+\frac43 \\ &=& \frac{22}3 \end{eqnarray*}

y

\begin{eqnarray*} \sum_{n=0}^\infty\sum_{S\subseteq\{2,3,4\}}(-1)^{|S|}\mathsf P\left(\bigwedge_{i\in S\cup\{1\}}N_i\gt n\right) &=& \sum_{n=0}^\infty\sum_{j=0}^2\sum_{k=0}^3(-1)^k\binom3k\binom nj4^{-n}(4-(k+1))^{n-j} \\ &=& 4\sum_{j=0}^2\sum_{k=0}^3(-1)^k\binom3k\left(\frac1{k+1}\right)^{j+1} \\ &=& 12-4\left(\frac32-1+\frac14+\frac34-\frac13+\frac1{16}+\frac38-\frac19+\frac1{64}\right) \\ &=& \frac{859}{144}\;. \end{eqnarray*}

Juntos, esto es

$$ \frac{22}3+\frac{859}{144}=\frac{1915}{144}\approx13.3\;, $$

de acuerdo con el primer resultado.

Answer 2

He aquí otra forma de obtener la solución, utilizando la "Poissonización". En lugar de generar números en tiempos discretos, considere $4$ procesos de Poisson independientes con tasa $1$ uno por cada número.

Los tiempos entre llegadas de un proceso de Poisson están distribuidos geométricamente de forma independiente, por lo que en el tiempo $t$ la probabilidad de que un proceso dado haya generado su número es $1-\mathrm e^{-t}$ y la probabilidad de que el proceso que genera $1$ s ha generado tres $1$ s viene dada por la función de distribución acumulativa $1-\mathrm e^{-t}\left(1+t+\frac12t^2\right)$ de un Erlang- $3$ distribución la distribución de la suma de $3$ variables independientes idénticamente distribuidas geométricamente. La suma de las $4$ de Poisson es a su vez un proceso de Poisson, con tasa $4$ . Como se muestra en esta respuesta el número esperado de generaciones necesarias es igual al número de generaciones que se espera que se produzcan en el tiempo esperado necesario, lo que en este caso da como resultado

$$ 4\int_0^\infty\left(1-\left(1-\mathrm e^{-t}\right)^3\left(1-\mathrm e^{-t}\left(1+t+\frac12t^2\right)\right)\right)\mathrm dt=\frac{1915}{144}\;, $$

de acuerdo con los otros dos enfoques.