Decir que tengo una bolsa con 100 canicas únicos. Con reemplazo, escoger a 10 canicas a la vez, al azar.

Question

Decir que tengo una bolsa con 100 canicas únicos. Con reemplazo, escoger a 10 canicas a la vez, al azar. Cuántas veces tendré que recoger las canicas (una selección de 10 canicas) para tener un 95% de probabilidades de haber visto al menos una vez cada mármol.

Answer 1

Las simulaciones muestran que usted necesita 73 o 72 picks (probablemente esta, $10^7$ dar vueltas $p = 0.950612$) y no conozco ningún método eficaz para calcular exactamente (por supuesto, eso no quiere decir que no hay uno).

irb(main):021:0> average(1000000) do g(100,10,73)? 1:0 end
=> 0.955118
irb(main):022:0> average(1000000) do g(100,10,72)? 1:0 end
=> 0.950215
irb(main):023:0> average(1000000) do g(100,10,71)? 1:0 end
=> 0.945348

Si quieres algunas fórmulas, entonces muy bruto estimado usando la desigualdad de Markov da $\frac{49.9}{1-0.95} \simeq 998$ veces. Con una diferencia, se podría asumir que reemplazar cada uno de mármol después de la cosecha (que es la que escoja una de mármol y, a continuación, reemplazar, y de nuevo un mármol, y de nuevo la sustituya) y, a continuación, esto se llama el cupón colector del problema.

El tiempo de espera para ver todos únicos canicas es $n\mathcal{H}_n$ donde $n$ es el número de canicas y $\mathcal{H}_n = \sum_{k=1}^{n} \frac{1}{k}$ $n$- ésimo número armónico. El uso de este cálculo se puede utilizar la Markov en la desigualdad

$$P(X \geq t) \leq \frac{\mathbb{E}X}{t}$$

to bound the necessary number of picks. With $n = 100$ we get

$$P(X \geq t) \leq \frac{100\mathcal{H}_{100}}{t}\leq5\%$$

that is, $0.05 t \geq 100 \mathcal{H}_{100} \approx 518.737$, so $t \geq 10375$. Escoger 10 en un momento, usted tendrá que recoger 1038 veces.

Espero que esta ayuda ;-)

Answer 2

@dtldarek. Lo siento publicar un comentario como respuesta, pero aún no tengo la suficiente reputación para dejar un comentario. @dtldarek: ¿podría usted por favor mira mi pregunta (y respuesta) y los comentarios sobre ella (la pregunta es reportado en ShreevatsaR comentario anterior). Básicamente es similar a la de este caso, pero en lugar de la única canicas, cada mármol de color está representado k veces (por ejemplo, k=5 en la pregunta anterior). Tengo la sensación de que la respuesta dada fue que en lugar de tratar el problema como k=1 (de manera similar a la pregunta anterior, donde las canicas son únicos). Me sería muy greatfull. Gracias