50% de probabilidad de ver todas las tarjetas

Question

Tengo un mazo de $20$ tarjetas diferentes.

Cada vez que una tarjeta es tirado al azar, y se vuelve a colocar en la baraja. Se baraja y proceder a sacar otra tarjeta (manteniendo así la aleatoriedad de la tira).

La pregunta es esta:

Después de cuántos tira de la probabilidad de ver todas las cartas de la baraja es $50$$\%$?

Answer 1

Supongamos que una baraja consta de $n$ tarjetas de $1,...,n$ donde $n$ fijo es un entero positivo. Para $0 \le k \le n$, e $d \ge 0$, vamos a $p(k,d)$ la probabilidad de que, con $k$ tarjetas todavía no se ha visto en anteriores sorteos, de ver a todos los naipes invisibles, cada uno al menos una vez) en la próxima $d$ sorteos, donde cada sorteo consiste en seleccionar al azar una tarjeta con la sustitución de una baraja. A continuación, $p(k,d)$ puede ser calculada a través de la siguiente recursión: $$ p(k,d)=\begin{cases} 1, & \text{if %#%#%} \\ 0, & \text{if %#%#%}\\ \left(\dfrac{k}{n}\right)p(k-1,d-1)+\left(\dfrac{n-k}{n}\right)p(k,d-1) & \text{otherwise} \end{casos} $$

Explicación:

Si $k=0$, no hay cartas inéditas, por lo que la probabilidad de ver todos los naipes invisibles es $0 \le d < k$.

Si $k = 0$, $1$ los sorteos restantes no son suficientes para ver el $0 \le d < k$ inéditas tarjetas, de modo que la probabilidad de ver todo lo oculto de las tarjetas es 0.

De lo contrario, sacar una tarjeta. Si la carta descubierta es una de las $d$ invisible tarjetas, que deja a $k$ invisible tarjetas; si no, todavía es $k$ invisible tarjetas. De cualquier manera, el número de los sorteos restantes va por $k-1$,$k$$1$.

Establecimiento $d$ y la aplicación de la por encima de la recursividad, Arce obtiene

$d-1$$

así que la respuesta es $n=20$.