Probabilidad de elegir todos los elementos en un conjunto

Question

Estaba estudiando la paradoja de los cumpleaños y me puse curioso acerca de un problema relacionado, pero ligeramente diferente. Digamos que tengo un conjunto S, que tiene n elementos únicos. Si elijo aleatoriamente k elementos del conjunto (asumiendo una probabilidad igual de elegir cualquier elemento), la probabilidad de que haya elegido todos los elementos en el conjunto, cuando k=n, es n!/n^n.

Ahora, ¿cuál sería el valor de k para que la probabilidad de elegir todos los elementos en el conjunto sea > 0.9 (o alguna constante)?

Una variación más simple sería - ¿cuántas veces debo lanzar una moneda para tener una probabilidad > 0.9 de haber lanzado cara y cruz al menos una vez?

Answer 1

Tu primera pregunta es sobre un problema famoso llamado el Problema del coleccionista de cupones.

Mira en el artículo de Wikipedia, bajo estimaciones finales. Eso te dará suficiente información para estimar, con una precisión razonable, el $k$ que te da una probabilidad del $90$ por ciento de haber visto una colección completa de cupones.

Answer 2

La probabilidad general de haber seleccionado todos los elementos después de un tamaño de muestra $k$ con reemplazo es

$$\frac{S_2 (k,n) \; n!}{ n^k} $$

donde $S_2 (k,n)$ es un número de Stirling de segunda clase. Quieres que esto sea mayor a 0.9.

Para $n=2$, tienes $S_2 (k,2) = 2^{k-1}-1$ para $k \gt 2$ así que quieres

$$\frac{(2^{k-1}-1) \times 2}{ 2^k} \gt 0.9 $$

lo cual es verdadero cuando $2^{k-1} \gt 10$, entonces con números enteros obtienes $k \ge 5$.

Answer 3

Pista: Si lanzas una moneda $k$ veces y no es cierto que hayan salido tanto caras como cruces, ¿qué deben ser tus lanzamientos?

Si no estás seguro, prueba con un valor pequeño de $k$, por ejemplo $k = 3$. Lista todos los posibles lanzamientos, y tacha aquellos que tienen tanto caras como cruces. ¿Qué queda?