El problema del coleccionista de cupones para obtener al menos la mitad de los cupones

Question

Estoy viendo el problema del Coleccionista de Cupones. El resultado clásico es que tenemos que recoger $n \ln(n) + O(n)$ por término medio tener al menos un cupón de cada tipo.

Estoy buscando el número de cupones que debemos reunir para tener al menos $\frac{n}{2}$ diferentes cupones, y tengo una duda sobre cómo proceder.

Visto como un problema de bolas y cubos, esto equivale a determinar el número de bolas que hay que lanzar para tener menos de $\frac{n}{2}$ cubos de basura vacíos. Si tiramos $m$ bolas en $n$ se sabe que el número esperado de recipientes vacíos será menor o igual a $e^{-m/n}$ . Por lo tanto, dejando que $m = \ln(2) \cdot n$ Tengo lo que quiero.

Sin embargo, si intento resolverlo como en [1] o [2], obtengo que el número de bolas es en promedio $nH_{n/2} \approx n \ln(n/2) + O(n)$ donde $H_{n}$ es el $n$ -número armónico.

Otro enfoque consiste en contar todas las soluciones que son aceptables ( $n/2$ , $n/2 + 1$ , ..., $n$ contenedores no vacíos) dando lugar a $n(H_n - H_{n/2}) \approx n\ln(2) + O(n)$ que es lo que quiero.

¿Qué enfoque es el correcto?

[1] Mitzenmacher, Michael, y Eli Upfal. Probabilidad y computación: Randomized algorithms and probabilistic analysis. Cambridge university press, 2005.
[2] Motwani, Rajeev, y Prabhakar Raghavan. Randomized algorithms. Chapman & Hall/CRC, 2010.

Answer 1

Creo que la respuesta es efectivamente asintótica a $n\ln2$ .

Una forma tradicional de resolver el problema original es la siguiente: dejemos que $X_k$ sea la variable aleatoria que describe, una vez que tenemos $k$ distintos cupones, cuántos cupones más necesitamos obtener antes de tener $k+1$ cupones distintos. Dado que la probabilidad de que un nuevo cupón sea diferente del primero $k$ los cupones es $1-\frac{k}n$ La distribución de $X_k$ es geométrico con el parámetro $(1-\frac{k}n)^{-1} = \frac n{n-k}$ y, por lo tanto, tiene una expectativa $\frac n{n-k}$ . La cantidad total de tiempo que se necesita para tener todos los $n$ los cupones distintos es $\sum_{k=0}^{n-1} X_k$ por la linealidad de la expectativa (ni siquiera utilizamos el hecho de que la $X_k$ son independientes), el tiempo esperado es $\sum_{k=0}^{n-1} \frac n{n-k} = nH_n$ .

Pero si sólo queremos medir el tiempo para conseguir la mitad de los cupones, la suma relevante es ahora $\sum_{k=0}^{n/2-1} \frac n{n-k} = nH_n - nH_{n/2} \sim n\ln2$ .