Límites de la tirada

Question

Dado un $n$ -en vista de la muerte justa, muestran que la probabilidad $P$ que todos los rostros de $1$ a $11$ mostrar cuando se hace $3n$ -Rollos está limitado por

$1 - 11 \cdot \frac {(n-1)^{3n}}{n^{3n}} \leq P \leq 1 - 11 \cdot \frac {11(n-1)^{3n}}{n^{3n}} + 5 \cdot 11 \cdot \frac {(n-2)^{3n}}{n^{3n}}$

Estoy realmente atascado en esto. Me imaginé que la probabilidad exacta es muy difícil de encontrar y los números de Stirling están involucrados. Así que la única oportunidad que tengo es averiguar qué eventos se usaron para ese límite. Mi conjetura es que la izquierda viene de la suposición de que (Edit: Advertencia: esto no es del todo correcto, compruebe los comentarios )

$ \mathbb {P}($ Los rostros 1-11 no ocurren en absoluto $)= \frac {|E|}{|Q|}= \frac {11 \cdot (n-1)^{3n}}{n^{3n}}$

Y si se mira el complemento es que todas las caras 1-11 por lo menos ocurren una vez. Seguramente este es un límite inferior pero como podría conseguir el límite superior, espero no haber pasado por alto algo muy fácil.

Answer 1

La respuesta se puede obtener mediante una aplicación bastante estándar de la Desigualdades de Bonferroni . Generalizamos un poco este problema. Fijar $1 \leq m \leq n$ y $M \geq m$ . Queremos encontrar la probabilidad de ver cada elemento del conjunto $\{1,\ldots,m\}$ en $M$ rollos de nuestro $n$ -madre de la cara.

Dejemos que $A_i$ sea el caso de que el $i$ El resultado no se ha producido en la primera $M$ lanzamientos del dado. Sea $A = \cup_{i=1}^m A_i$ sea el caso de que no todos los $\{1,\ldots,m\}$ se ven en la primera $M$ tiros. Nos interesa el complemento, $\bar{A}$ de este evento.

Una aplicación directa de las desigualdades de Bonferroni muestra que $$ \renewcommand{\Pr}{\mathbb{P}} \sum_{i=1}^m \;\Pr(A_i) - \sum_{1 \leq i < j \leq m} \Pr(A_i \cap A_j) \leq \Pr(A) \leq \sum_{i=1}^m \;\Pr(A_i) \> . $$

Pero, $\Pr(A_i) = (1-1/n)^M$ para cada $i$ y $\Pr(A_i \cap A_j) = (1-2/n)^M$ para cada par $i \neq j$ . Esto da como resultado $$ m\Big(1-\frac{1}{n}\Big)^M - \frac{m(m-1)}{2}\Big(1-\frac{2}{n}\Big)^M \leq \Pr(A) \leq m \Big(1-\frac{1}{n}\Big)^M $$

Utilizando el hecho de que $\Pr(\bar{A}) = 1 - \Pr(A)$ y conectando $m = 11$ y $M = 3 n$ da el resultado.

---

Tenga en cuenta que si $M$ es relativamente grande con respecto a $n$ y $m$ entonces podemos obtener un límite exponencial. En particular, si, para $c > 0$ , $M = n \log m + c n$ entonces $$ m(1-1/n)^M = m (1 - 1/n)^{n \log m + c n} \leq e^{-c} $$ y así la probabilidad de ver todos los elementos de $\{1,\ldots,m\}$ en $M = n \log m + c n$ lanza es $$ \Pr(\bar{A}) \geq 1 - e^{-c} \> . $$