(Nota: Este es el correcto análisis de la $k$ consultas no necesariamente distintos, pero he publicado este por separado como una respuesta porque mi anterior ya era demasiado largo y desordenado.)
Después de la $N = nk$ bolas se colocan en la $m$ papeleras, supongamos que una fracción $q$ de los contenedores están vacíos. Cuando hacemos el $k$ de las consultas, la probabilidad de que una consulta en particular se encuentra con un no-recipiente vacío es exactamente $(1 - q)$, ya que la consulta podría encontrar alguno de los $m$ contenedores con igual probabilidad. Además, incluso a pesar de que los contenedores no son independientes, de la $k$ de las consultas que nos hacen son totalmente independientes, por lo que la probabilidad de que todo encuentro no vacía las papeleras es exactamente $(1-q)^k$.
La respuesta final (la probabilidad) se obtuvo al considerar todos los posibles valores de $q$, ponderados por su probabilidad: la probabilidad de que todos los $k$ de las consultas de ver a un vacío de reciclaje es $$\sum_{\alpha} \Pr(q = \alpha)(1-\alpha)^k$$ where the sum is over values $\alpha \en [0, 1]$ that $q$ can take, namely values of the form $\frac{r}{m}$ for $0 \le r \le m$. Ninguna aproximación aquí.
La cuestión de la independencia de las tolvas viene cuando tratamos de decir lo que la fracción $q$ podría ser. La probabilidad de un intervalo en particular (digamos bin $i$) está vacío es $p = \left(1 - \frac1m\right)^N$, ya que para este recipiente vacío, cada una de las $N$ bolas debe haber pasado a cualquiera de los otros $(m - 1)$ papeleras aparte de este. Esta probabilidad $p$ es también el valor esperado de la fracción $q$.
(Para probar este rigurosamente: definir la variable de indicador $X_i$ $1$ si bin $i$ está vacía, y $0$ lo contrario. El número total de bandejas vacías $X = X_1 + X_2 + \dots + X_m$ valor esperado $E[X] = E[X_1 + \dots + X_m] = E[X_1] + \dots + E[X_m] = mE[X_1]$ por la linealidad de lo esperado, por lo que el valor esperado de la fracción $q$ (que es el mismo que$X/m$)$E[q] = E[X/m] = E[X]/m = E[X_1] = p.$)
El valor real de $q$ puede variar y ser diferente de su valor esperado $p$. Sin embargo, la probabilidad de estar lejos de $p$ es muy bajo: a medida que nos alejamos de $p$, la probabilidad de $q$ tomando ese valor decae exponencialmente. Como $p \approx e^{-N/m}$, esto también significa que la probabilidad de $q$ estar lejos de $e^{-N/m}$ también es muy bajo. (Todavía tenemos que probar esto.)
Por lo que la probabilidad de todos los $k$ papeleras de ser no vacío, que es
$\sum_{\alpha} \Pr(q = \alpha)(1-\alpha)^k$, es efectivamente el mismo que $\left(1 - e^{-N/m} \right)^k$ $q$ toma un valor de alrededor de $e^{-N/m}$ con abrumadoramente alta probabilidad.
De izquierda a demostrar: que $q$ es poco probable que sea lejos de $e^{-N/m}$. Es un poco engorroso para analizar la fracción $q$, ya que depende de que todos los recipientes, y no son independientes. Un enfoque es obligado el error causado por la independencia de la asunción. Mitzenmacher y Upfal, en su libro de Probabilidad y la Informática: estudio Aleatorizado de Algoritmos y Análisis Probabilistas, dar un elegante técnica para hacer precisamente esto.
Centrémonos en una bandeja determinada $i$ de la $m$ papeleras. Tener en cuenta el número de bolas en el recipiente $i$, después de $N$ bolas se han caído de forma independiente y uniformemente al azar en el $m$ papeleras. Para cada bin $i$, este número ( $X_i$ ) sigue la distribución binomial: la probabilidad de que el reciclaje ha $r$ bolas es
$\Pr[X_i = r] = \binom{N}{r}\left(\frac1m\right)^r\left(1-\frac1m\right)^{N-r}.$ Esto es aproximadamente una distribución de Poisson con parámetro de $\lambda = \frac{N}{m}$, o en otras palabras $\Pr[X_i = r] \approx e^{-\lambda}(\lambda^r / r!)$.
Motivados por esto, por la $m$ papeleras de todos los vistos juntos, van a presentar lo que ellos llaman la aproximación de Poisson. Considere la posibilidad de $m$ papeleras con el número de bolas en cada bin $i$ (llamar a este número $Y_i$) como de forma independiente distribuido, siguiendo una distribución de Poisson con parámetro de $\lambda = \frac{N}{m}$. Por supuesto, en esta distribución, el número total de bolas a través de la $m$ papeleras podría variar, aunque es $N$ en la espera. Sin embargo, es sorprendentemente sencillo ejercicio para demostrar que
- La distribución de $(Y_1, \dots, Y_m)$ cuando acondicionado en $\sum_{i=1}^{m} Y_i = N$ es la misma que la distribución de $(X_1, \dots, X_m)$.
- Cualquier evento que se lleva a cabo con una cierta probabilidad de $p$ en la "aproximación de Poisson escenario" se lleva a cabo con la probabilidad en la mayoría de los $pe\sqrt{N}$ en la "misma situación".
Esta desigualdad anterior es demostrado por mostrar que para cualquier función no negativa $f(x_1, \dots, x_m)$ (tales como el indicador de la función de un evento), tenemos
$$\begin{align}
E[f(Y_1, \dots, Y_m)]
&\ge E\left[f(Y_1, \dots, Y_m) | \sum_i Y_i = N\right]\Pr(\sum_i Y_i = N) \\
&= E[f(X_1, \dots, Y_m)] \Pr(\sum_i Y_i = N) \\
&\ge E[f(X_1, \dots, Y_m)] (1 / e\sqrt{N})
\end{align}
$$
como $\Pr(\sum_i Y_i = N) = e^{-N} (N^N / N!)$$N! \le e\sqrt{N} (N/e)^N$.
Así, probar algo así(?) $\Pr(|q - p|) \ge \epsilon) \le 2e\sqrt{m}e^{-m\epsilon^2 / 3p}$ el uso de este y el Chernoff obligado.
De hecho, que demuestren el uso de martingales y la Azuma-la desigualdad de Hoeffding (12.5.3, p. 308) que $\Pr(|q - p| \ge \frac{\lambda}{m}) \le 2\exp(-2\lambda^2/m)$.
Incluso tienen un ejercicio (12.19, p. 313) que muestra que el $\Pr(|q - p| \ge \frac{\lambda}{m}) \le 2\exp(-\lambda^2(2m - 1) / (m^2 - p^2m^2))$.
