Esta respuesta no es rigurosa para justificar las aproximaciones, pero el resultado se confirma numéricamente.
Llamaré al $N$ diferentes cupones colores para distinguirlos más claramente de los cupones dibujados.
Dejemos que $M=\alpha N\log N$ y considerar el límite $N\to\infty$ por el hecho de ser fijo $\alpha$ . En primer lugar, vamos a calcular la varianza del número de cupones sorteados en el problema del recolector de cupones sin modificar. Como la expectativa se obtiene como la suma de las expectativas de $N$ valores independientes, la varianza es la suma de las varianzas de estos valores. El número de extracciones para obtener un nuevo color cuando $k$ los colores siguen faltando es distribuido geométricamente con $p=k/N$ y por lo tanto la expectativa $1/p=N/k$ y la varianza $(1-p)/p^2=(N^2-kN)/k^2$ . La suma de las expectativas es el conocido resultado
$$ \sum_{k=1}^N\frac Nk=NH_N\sim N\log N\;, $$
donde $H_N$ es el $N$ -número armónico. La suma de las varianzas es
$$ \sum_{k=1}^N\frac{N^2-kN}{k^2}\sim\frac{\pi^2}6N^2-N\log N\sim\frac{\pi^2}6N^2\;. $$
Así, la desviación estándar es asintóticamente una fracción fija $\pi/\sqrt6$ de $N$ y por La desigualdad de Chebyshev por el hecho de ser fijo $\alpha\gt1$ el proceso termina asintóticamente de forma casi segura antes de que se produzca el vencimiento, por lo que el número esperado de cupones en este caso es simplemente el número esperado sin modificar $NH_N$ .
Por otro lado, por la misma razón, para los fijos $\alpha\lt1$ el proceso asintóticamente casi seguro no termina antes de la expiración, por lo que el número esperado de cupones en este caso es $M$ más el número esperado de cupones extraídos tras el inicio de la caducidad.
Para estimar esta última, estimemos primero la probabilidad de que todos los $N$ los colores están representados en $M$ cupones uniformes e independientes. Según la respuesta de Byron a esta pregunta Esto es
$$ \sum_{k=0}^N (-1)^k {N\choose k}\left(1-{k\over N}\right)^M=\sum_{k=0}^N (-1)^k {N\choose k}\left(1-{k\over N}\right)^{\alpha N\log N}\;. $$
Podemos aproximar esto mediante
$$ \sum_{k=0}^N (-1)^k {N\choose k}\mathrm e^{-k\alpha\log N}=\sum_{k=0}^N (-1)^k {N\choose k}\left(N^{-\alpha}\right)^k=\left(1-N^{-\alpha}\right)^N\sim\exp\left(-N^{1-\alpha}\right) $$
para $N\to\infty$ si los términos de la serie se hacen despreciables antes de que la aproximación se rompa. Para comprobarlo, considera el logaritmo del valor absoluto de los términos (aproximados),
$$ \log\left(\binom Nk\mathrm e^{-k\alpha\log N}\right)\approx N\log N-k\log k-(N-k)\log(N-k)-k\alpha\log N\;, $$
y fijar la derivada con respecto a $k$ a cero:
$$ -\log k+\log(N-k)-\alpha\log N=0 $$
para encontrar el máximo en $k=N/(1+N^\alpha)$ . Así, para $N\to\infty$ el máximo se desplaza hacia fracciones de $N$ y la aproximación es asintóticamente válida.
Ahora, una primera estimación del número esperado de cupones extraídos tras el inicio del vencimiento sería $\exp\left(N^{1-\alpha}\right)$ el resultado si en cada sorteo el $M$ Los cupones no vencidos eran independientes de los de los sorteos anteriores. Esto ya muestra la característica deseada de interpolar entre el comportamiento exponencial para $\alpha\to0$ y $N\log N$ comportamiento para $\alpha\to1$ . (Recuerde que $M=\alpha N\log N$ se suma a esto para obtener el número total esperado de cupones).
Para mejorar la estimación, debemos condicionarla a que los lotes anteriores no contengan todos los colores. Dado que, asintóticamente, es casi seguro que un lote no contenga todos los colores, el denominador en la definición de la probabilidad condicional tiende a $1$ y la probabilidad de que el lote actual contenga todos los colores condicionada a que los lotes anteriores no contengan todos los colores es asintóticamente igual a la probabilidad de que el lote actual contenga todos los colores y los lotes anteriores no.
La parte más importante de la condición, que es independiente de los colores de los cupones recién caducados, es simplemente que el $M-1$ los cupones no caducados que ya teníamos la última vez no contienen todo $N$ colores. La probabilidad de que $M$ los cupones contienen todos $N$ colores pero el primero $M-1$ de ellos no es
$$ \begin{align} &\sum_{k=0}^N (-1)^k {N\choose k}\left(1-{k\over N}\right)^M-\sum_{k=0}^N (-1)^k {N\choose k}\left(1-{k\over N}\right)^{M-1} \\ \sim&\sum_{k=0}^N (-1)^k {N\choose k}\left(1-{k\over N}\right)^M-\sum_{k=0}^N (-1)^k {N\choose k}\left(1-{k\over N}\right)^M\left(1+{k\over N}\right) \\ =&\sum_{k=0}^N (-1)^k {N\choose k}\left(1-{k\over N}\right)^M\left(-\frac kN\right) \\ \sim&\sum_{k=0}^N (-1)^k {N\choose k}\left(N^{-\alpha}\right)^k\left(-\frac kN\right) \\ =&N^{-\alpha}\left(1-N^{-\alpha}\right)^{N-1} \\ \sim&N^{-\alpha}\exp\left(-N^{1-\alpha}\right)\;. \end{align} $$
Así obtenemos una estimación mejorada del número esperado de sorteos tras el inicio de la expiración, $N^{\alpha}\exp\left(N^{1-\alpha}\right)$ . De hecho, esto resultará ser asintóticamente correcto, pero tenemos que comprobar el efecto de las condiciones implícitas en los colores de los cupones recién caducados.
Para ello, imagine que el proceso de sorteo se invierte en el tiempo, eliminando los cupones recién extraídos y añadiendo los cupones recién caducados. Podemos interpretar el cálculo anterior para mostrar que, condicionado a todos los $M$ cupones que contienen todos los $N$ colores, la eliminación de un cupón tiene una probabilidad de $1-N^{-\alpha}$ de eliminar un único color, mientras que con probabilidad $N^{-\alpha}$ todos los colores permanecen representados. Este resultado sigue siendo válido si eliminamos más cupones; los cambios en $M$ y $N$ por $O(1)$ sólo cambian el resultado por un factor $1+O(N^{-1})$ . Por lo tanto, asintóticamente, condicionado a todos los $M$ cupones que contienen todos los $N$ colores, cada cupón retirado recientemente de forma independiente tiene una probabilidad de $1-N^{-\alpha}$ de reducir el número de colores representados por uno.
Por otro lado, los cupones recientemente caducados no se ven afectados por la condición de que nuestro conjunto actual de cupones contenga todos los colores, por lo que la probabilidad de recuperar un color concreto que falta añadiendo de nuevo un cupón recientemente caducado es simplemente $1-N^{-1}$ .
Con este modelo, podemos obtener una expansión sistemática de la probabilidad en estado estacionario de completar los colores en un sorteo determinado, considerando un número creciente de colores perdidos. Mostraré el cálculo para un color adicional que falta, que es sencillo y demuestra que las correcciones no afectan al comportamiento asintótico.
Sabemos que un color desaparece inmediatamente cuando quitamos el cupón recién dibujado. Sea $j+1$ es el número de cupones recién extraídos que tenemos que eliminar más allá de eso para perder otro color, y dejemos que $l+1$ sea el número de cupones caducados que tenemos que recuperar para sustituir el color del cupón que se acaba de sortear. Entonces este historial se excluye si $l\le j$ ya que en ese caso el color que se acaba de dibujar se sustituye antes de que falte otro, lo que implica un conjunto completo de $N$ colores en el pasado. Por lo tanto, queremos la fracción de historias para las que $l\gt j$ . Esto es
$$ \begin{align} &\sum_{j=0}^\infty N^{-\alpha}\left(1-N^{-\alpha}\right)^j\sum_{l=j+1}^\infty N^{-1}\left(1-N^{-1}\right)^l \\ =&\sum_{j=0}^\infty N^{-\alpha}\left(1-N^{-\alpha}\right)^j\left(1-N^{-1}\right)^{j+1} \\ \sim&\frac{N^{-\alpha}}{N^{-\alpha}+N^{-1}} \\ =& \frac1{1+N^{\alpha-1}}\;. \end{align} $$
Multiplicando esto por la probabilidad $N^{-\alpha}\exp\left(-N^{1-\alpha}\right)$ y tomando el recíproco se obtiene una estimación mejorada del número esperado de cupones extraídos tras el inicio de la caducidad, $N^\alpha\exp\left(N^{1-\alpha}\right)\left(1+N^{\alpha-1}\right)$ . Nótese que la corrección no afecta al comportamiento asintótico, ya que $1+N^{\alpha-1}\sim1$ .
También he realizado los cálculos para dos y tres colores adicionales que faltan, que son un poco más complicados. No les aburriré con los detalles; el resultado es que el número esperado de cupones se multiplica por funciones racionales de $N^{\alpha-1}$ que van a $1$ para $N^{\alpha-1}\to0$ . La expansión sólo parece converger para valores bastante pequeños de $N^{\alpha-1}$ pero eso no importa asintóticamente.
Así, el análisis sugiere que el número esperado de cupones extraídos tras el inicio del vencimiento es asintótico a $N^{\alpha}\exp\left(N^{1-\alpha}\right)$ . Esto es difícil de comprobar numéricamente para la mayoría de $\alpha$ ya que para $\alpha$ cerca de $1$ la expansión en $N^{1-\alpha}$ converge muy lentamente y para $\alpha$ cerca de $0$ el número esperado de sorteos es prohibitivo. Un compromiso razonable es $\alpha=0.8$ para el que el siguiente cuadro muestra el número medio de cupones extraídos tras el inicio del vencimiento en $5000$ corre por $N=10\cdot2^n$ con $n=0,\dotsc,12$ y $M$ el número entero más cercano a $0.8N\log N$ . También se muestra la relación con el resultado asintótico $N^{\alpha}\exp\left(N^{1-\alpha}\right)$ y al resultado de la corrección de primer orden, $N^{\alpha}\exp\left(N^{1-\alpha}\right)\left(1+N^{\alpha-1}\right)$ . Ambas proporciones parecen acercarse a $1$ la corregida más rápidamente.
$$ \begin{array}{r|r|r|r|r|r|r} N&M&\langle\text{#draws}\rangle&N^{0.8}\exp(N^{0.2})&\cdot\,(1+N^{-0.2})&\text{ratio}&\text{corrected}\\\hline 10 & 18 & 28 & 31 & 50 & 0.9115 & 0.5589\\ 20 & 48 & 62 & 68 & 105 & 0.9196 & 0.5936\\ 40 & 118 & 158 & 155 & 229 & 1.0226 & 0.6918\\ 80 & 280 & 428 & 368 & 521 & 1.1638 & 0.8217\\ 160 & 650 & 1097 & 916 & 1247 & 1.1976 & 0.8790\\ 320 & 1477 & 3019 & 2403 & 3161 & 1.2563 & 0.9550\\ 640 & 3308 & 8994 & 6703 & 8544 & 1.3418 & 1.0527\\ 1280 & 7326 & 25913 & 20055 & 24850 & 1.2921 & 1.0428\\ 2560 & 16072 & 85089 & 65037 & 78573 & 1.3083 & 1.0829\\ 5120 & 34984 & 294659 & 231341 & 273258 & 1.2737 & 1.0783\\ 10240 & 75645 & 1122292 & 915127 & 1059479 & 1.2264 & 1.0593\\ 20480 & 162647 & 4998493 & 4089855 & 4651474 & 1.2222 & 1.0746\\ 40960 & 348008 & 24025351 & 21028673 & 23542526 & 1.1425 & 1.0205\\ \end{array} $$
Este es el código Solía producir la mesa.
