Problema de los contenedores y las bolas: ¿número esperado de bolas colocadas dado el número de contenedores vacíos y no vacíos?

Question

Dados son$m$ bins con la misma probabilidad de elegir uno de ellos. El número desconocido de bolas$n$ se coloca en los contenedores y, al final de la colocación, observamos el número de contenedores vacíos$m_e$ y los contenedores no vacíos$m_{n}$.

Dado$m$,$m_e$,$m_n$, ¿cuál es el número más probable de bolas$n$, que se han colocado en contenedores?

(UPD) posible información adicional: también se puede conocer el número de contenedores con exactamente una bola.

Answer 1

Presumiblemente $m=m_e+m_n$.

La probabilidad de ver a $m_n$ $m$ ocupado es $\dfrac{S_2(n,m_n)\, m!}{m^n \;(m-m_n)!}$ donde $S_2(x,y)$ es un número de Stirling del segundo tipo. No sé una manera fácil de encontrar el$n$, lo que maximiza esto en general, pero es bastante fácil de calcular dado razonablemente pequeño $m$.

Una posible alternativa estimador es $\dfrac{\log(m)-\log(m-m_n)}{\log(m)-\log(m-1)}$, que sigue de decir $E[m_n \mid m, n] = m\left(1 -\left(\frac{m-1}{m}\right)^n\right)$. Este no es un estimador de máxima verosimilitud ni un estimador imparcial para $n$, y normalmente no es un entero, pero viene bastante cerca del estimador de máxima verosimilitud, es ligeramente sesgada hacia arriba al $1 \lt n \lt m$. La tabla siguiente compara los valores de al $m=10$ diferentes $m_n$

 m      m_n   n_MLE    n_alt.est 
10       0     0        0   
10       1     1        1   
10       2     2        2.12  
10       3     3        3.39
10       4     4 or 5   4.85
10       5     6        6.58
10       6     8        8.70
10       7    11       11.43
10       8    15       15.25 
10       9    22       21.85
10      10    infinite  n/a

Answer 2

1) Premisa

Al azar de tiro (put) $n$ bolas en $m$ contenedores (de capacidad ilimitada)
significa que usted considere como equiprobables e independientes de los eventos de la
lanzamiento de la $k$-th pelota en el $j$-th bin
es decir, una secuencia de $n$ eventos independientes, cada una con $m$ resultados equiprobables.
Así, el espacio de los sucesos elementales es el $n$D (hiper)cubo de lado a $1\dots m$, conteniendo $m^n$ puntos (es decir, secuencias).

2) el Problema

Vamos a llamar a $m_e$ $q$ a simplificar la notación. Vamos, a continuación, llamar a $N(n,m,q)$ el número de configuraciones con exactamente $q$ contenedores vacíos, y claramente con el otro $m-q$ que contiene al menos una bola.
La probabilidad de tener una configuración con exactamente $q$ contenedores vacíos, de $m$ contenedores en total y después de haber colocado el $n$th pelota es $$ \bbox[lightyellow] { P(n,m,p) = {1 \over {m^{\n} }}N(n,m,p) }$$ Manteniendo $m$ fijo, con un poco de "abuso" de la notación, sino ayudar a hacer que el desarrollo claro, permitir escribir lo anterior como $$ \bbox[lightyellow] { P(n,m,p) = \wp (p|n) = {{\wp (q \wedge n)} \over {\wp (n)}} }$$

Entonces la cuestión es encontrar $$ \bbox[lightyellow] { \wp (n|p) = {{\wp (q \wedge n)} \over {\wp (q)}} = {{\wp (q \wedge n)} \over {\sum\limits_n {\wp (p|n)\;\wp (n)} }} = {{P(n,m,p)\wp (n)} \over {\sum\limits_n {\wp (p|n)\;\wp (n)} }} } \etiqueta {1}$$

Esto claramente demuestra que nos falta información para resolver el problema: P(n).
Es que tenemos que saber la probabilidad de que las bolas se lanzó $(0),\, 1,\, 2,\, \cdots$.

Suponiendo que sea un uniforme de probabilidad, entre el $0$ y, digamos, $u$, entonces es constante y simplifica, dejando $$ \bbox[lightyellow] { \wp (n|q)\left| {\;n\,{\rm uniforme}\;{\rm distr}.} \right. = P(n,m,p) = {{P(n,m,p)} \over {\sum\limits_{n\, \en \;{\rm rango}} {P(n,m,p)} }} } \etiqueta {1.a}$$

3) P(n,m,p) y Q(n,m,p) fórmula

En este otro post se explica cómo llegamos a demostrar que $$ \bbox[lightyellow] { \eqalign{ & N(n,m,p) = \left( \matriz{ m \cr q \cr} \right)N(n,m - q,0) = {{m.} \over {p!}}\left\{ \matriz{ n \cr m - q \cr} \right\}\quad \Rightarrow \cr & \Rightarrow \quad P(n,m,p) = \left[ {0 = n} \right]\left[ {0 = m} \right]\left[ {0 = q} \right] + \left[ {1 \le m} \right]{{m.} \over {m^{\n} \;p!}}\left\{ \matriz{ n \cr m - q \cr} \right\} \cr} } \etiqueta {2}$$ donde $[P]$ es el soporte de Iverson $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$

Ahora es $$ \bbox[lightyellow] { \eqalign{ & \sum\limits_{0\, \le \,k} {\left\{ \matriz{ k \hfill \cr n \hfill \cr} \right\}\;\left( {{1 \over z}} \right)^{\,k} } \;\left| {\;0 \le {\rm integer}\;n} \right.\quad = \cr Y = {1 \over {\left( {z - 1} \right)\left( {z - 2} \right) \cdots \left( {z n} \right)}} = {1 \over {\left( {z - 1} \right)^{\,\underline {\n\,} } }} = z^{\,\overline {\, - n\,} } = {{\Gamma \left( {z n} \right)} \over {\Gamma \left( z \right)}} \cr} } $$ donde $z^{\,\underline {\,n\,} }$ $z^{\,\overline {\, n\,}} $ denotar la caída y el levantamiento de factorial, respectivamente.

De modo que, para el rango de $n$ va en el límite de la $\infty$ obtenemos (dejando aparte el caso de $0=m$): $$ \bbox[lightyellow] { \sum\limits_{0\, \le \,n} {P(n,m,p)} = \sum\limits_{0\, \le \,n} {{{m.} \over {\;p!}}\left\{ \matriz{ n \cr m - q \cr} \right\}\left( {{1 \over m}} \right)^{\n} } = {{m.} \over {\;p!}}{{\Gamma \left( q \ \ derecho)} \over {\Gamma \left( m \right)}} } $$ y $$ \bbox[lightyellow] { \wp (n|q) = P(n,m,p) = {1 \over {m^{\n} \;}}{{\Gamma \left( m \right)} \over {\Gamma \left( q \ \ derecho)}}\left\{ \matriz{ n \cr m - q \cr} \right\} } \etiqueta {3}$$

Es digno de notar que, por $q=0$ y $1 \le m$, $ Q(n,m,q)$ es null. Eso es debido a que la información "no hay ningún recipiente vacío" sólo implica que $m \le n$, y el rango que se asume para $n$ se extiende hasta el infinito.

4) el valor esperado para $n$

Desde $$ \bbox[lightyellow] { \sum\limits_{0\, \le \,k} {k\left\{ \matriz{ k \hfill \cr n \hfill \cr} \right\}\;z^{\,k} } \; = z{d \over {dz}}\sum\limits_{0\, \le \,k} {\left\{ \matriz{ k \hfill \cr n \hfill \cr} \right\}\;z^{\,k} } = z{d \over {dz}}{{\Gamma \left( {1/z n} \right)} \over {\Gamma \left( {1/z} \right)}} = {{\Gamma \left( {1/z n} \right)} \over {z\;\Gamma \left( {1/z} \right)}}\left( {\psi (1/z) - \psi (1/z - n)} \right) } $$

Luego, siempre en el caso de una distribución uniforme para $n$, con un rango de estending en el límite de la $\infty$, obtenemos $$ \bbox[lightyellow] { \eqalign{ & E(n)\quad \left| {\,1 \le q \le m} \right.\quad = \cr & = \sum\limits_{0\, \le \,n} {n\;Q(n,m,p)} = {{\Gamma \left( m \right)} \over {\Gamma \left( q \ \ derecho)}}\sum\limits_{0\, \le \,n} {n\;\left\{ \matriz{ n \cr m - q \cr} \right\}\left( {{1 \over {m\;}}} \right)^{\n} } = \cr & = m\left( {\psi (m) - \psi (q)} \right) \cr} } \etiqueta {4}$$ que se representa a continuación

De nuevo, tenga en cuenta que , para$q=0$$1 \le m$, el valor esperado de $n$ sube hasta el infinito, por la razón que se dijo anteriormente.

5) max probable valor de $n$

Usted está solicitando para el modo de $Q(n,m,q)$. Desgraciadamente su fórmula no permite encontrar el modo analíticamente.
Sin embargo, la trama de $Q$ vs $n$, en $m$$q$, es claramente positiva sesgada.
Por lo tanto, el modo de poner un poco más bajo que el promedio, y por lo tanto el conocimiento de $E[n]$ es de ayuda en la búsqueda del modo numéricamente.

Answer 3

Supongamos que tenemos $m$ contenedores de los cuales, $m_e$ están vacías (y la no-vaciar las papeleras se $m_n=m-m_e$). Supongamos también que $m_e > 0$, de lo contrario hay muy poca información de la que podemos obtener, como se discute en los comentarios.

Si pudiéramos calcular la probabilidad de tener $i$ bolas, dada esta observación, entonces podemos calcular el valor esperado de bolas, o el estimador de máxima verosimilitud, u otras preguntas acerca de la estimación del número de bolas. Por lo que estamos buscando $P(\text{balls} = i | m_e,m )$.

La aplicación de la regla de Bayes se obtiene:

$$P(\text{balls} = i | m_e,m ) = \frac{P(m_e,m|\text{balls}=i)\cdot P(\text{balls}=i)}{\sum_{i=m_n}^\infty P(m_e,m|\text{balls}=i)\cdot P(\text{balls}=i)}$$

Observe que las bolas tienen que ser al menos tan numerosos como los no-vaciar las papeleras.

También notamos la importancia de conocer la probabilidad anterior de $P(\text{balls} =i)$. Sin ninguna otra información sobre esto, vamos a suponer que todos los valores de $i$ son equiprobables, por lo que estos términos pueden cancelar en la fórmula.

¿Qué es $P(m_e,m|\text{balls}=i)$? En otras palabras, dado que se distribuyó $i$ bolas en los contenedores, ¿cuál es la probabilidad de que tenemos exactamente $m_e$ bandejas vacías, de $m$ total de las papeleras? Si la distribución se realiza en un uniforme de manera aleatoria, entonces esta probabilidad es igual a $\dfrac{S_2(i,m_n)\cdot m!}{m^n \cdot m_e!}$.

Edit: al principio pensé que se trataba de una fórmula más simple, que era más analíticamente manejable. Después de ver a Henry respuesta me di cuenta de mi error. Me temo que mi análisis se detiene aquí. Usted puede computacionalmente calcular estas probabilidades para el pequeño número de pelotas y botes de basura. También puede calcular $P(\text{balls} = i | m_e,m )$, especialmente si usted asume un máximo número posible de pelotas (de modo que la suma en el numerador de la regla de Bayes se convierte en manejable).