This answer isn't rigorous in justifying approximations, but the result is confirmed numerically.
I'll call the $N$ different coupons colours to distinguish them more clearly from the coupons drawn.
Let $M=\alpha N\log N$, and consider the limit $N\to\infty$ for fixed $\alpha$. First, let's calculate the variance of the number of coupons drawn in the unmodified coupon collector's problem. As the expectation is obtained as the sum of the expectations of $N$ independent values, the variance is the sum of the variances of these values. The number of draws to get a new colour when $k$ colours are still missing is geometrically distributed with $p=k/N$ and thus expectation $1/p=N/k$ and variance $(1-p)/p^2=(N^2-kN)/k^2$. The sum of the expectations is the well-known result
$$
\sum_{k=1}^N\frac Nk=NH_N\sim N\log N\;,
$$
where $H_N$ is the $N$-th harmonic number. The sum of the variances is
$$
\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\;.
$$
Thus the standard deviation is asymptotically a fixed fraction $\pi/\sqrt6$ of $N$, and by Chebyshev's inequality for fixed $\alpha\gt1$ the process asymptotically almost surely ends before expiration sets in, so the expected number of coupons in this case is just the unmodified expected number $NH_N$.
On the other hand, for the same reason, for fixed $\alpha\lt1$ the process asymptotically almost surely doesn't end before expiration sets in, so the expected number of coupons in this case is $M$ plus the expected number of coupons drawn after the onset of expiration.
To estimate the latter, let's first estimate the probability that all $N$ colours are represented in $M$ uniformly independently drawn coupons. According to Byron's answer to this question, this is
$$
\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}\;.
$$
We can approximate this by
$$
\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)
$$
for $N\to\infty$ if the terms of the series become negligible before the approximation breaks down. To check this, consider the logarithm of the absolute value of the (approximated) terms,
$$
\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\;,
$$
and set the derivative with respect to $k$ to zero:
$$
-\log k+\log(N-k)-\alpha\log N=0
$$
to find the maximum at $k=N/(1+N^\alpha)$. Thus for $N\to\infty$ the maximum shifts towards vanishing fractions of $N$, and the approximation is asymptotically valid.
Now a first estimate of the expected number of coupons drawn after the onset of expiration would be $\exp\left(N^{1-\alpha}\right)$, the result if at every draw the $M$ unexpired coupons were independent of the ones at previous draws. This already exhibits the desired feature of interpolating between exponential behaviour for $\alpha\to0$ and $N\log N$ behaviour for $\alpha\to1$. (Remember that $M=\alpha N\log N$ gets added to this to obtain the total expected number of coupons.)
To improve the estimate, we need to condition on the previous batches not containing all colours. Since asymptotically a batch almost surely doesn't contain all colours, the denominator in the definition of the conditional probability tends to $1$, and the probability for the current batch to contain all colours conditioned on the previous batches not containing all colours is asymptotically equal to the probability that the current batch contains all colours and the previous batches didn't.
The most important part of the condition, which is independent of the colours of recently expired coupons, is simply that the $M-1$ unexpired coupons we already had last time don't contain all $N$ colours. The probability that $M$ coupons contain all $N$ colours but the first $M-1$ of them don't is
$$
\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}
$$
Thus we obtain an improved estimate for the expected number of draws after the onset of expiration, $N^{\alpha}\exp\left(N^{1-\alpha}\right)$. In fact this will turn out to be asymptotically correct, but we need to check the effect of the conditions implied by the colours of the recently expired coupons.
To do so, imagine the drawing process reversed in time, with recently drawn coupons being removed and recently expired coupons being added. We can interpret the above calculation to show that, conditional on all $M$ coupons containing all $N$ colours, removing one coupon has a probability of $1-N^{-\alpha}$ of removing a unique colour, whereas with probability $N^{-\alpha}$ all colours remain represented. This result remains valid if we remove further coupons; the changes in $M$ and $N$ by $O(1)$ only change the result by a factor $1+O(N^{-1})$. Thus, asymptotically, conditional on all $M$ coupons containing all $N$ colours, each removed recently drawn coupon independently has a probability of $1-N^{-\alpha}$ of reducing the number of colours represented by one.
On the other hand, the recently expired coupons are not affected by the condition that our current set of coupons contains all colours, so the probability of regaining a particular missing colour by adding a recently expired coupon back in is just $1-N^{-1}$.
With this model, we can obtain a systematic expansion of the steady-state probability of completing the colours on a given draw, by considering increasing numbers of missing colours. I'll show the calculation for one additional missing colour, which is straightforward and demonstrates that the corrections don't affect the asymptotic behaviour.
We know that one colour immediately goes missing when we remove the coupon just drawn. Let $j+1$ be the number of recently drawn coupons we need to remove beyond that to lose another colour, and let $l+1$ be the number of expired coupons we have to recoup to replace the colour of the coupon just drawn. Then this history is excluded if $l\le j$, since in that case the colour just drawn gets replaced before another one goes missing, implying a full set of $N$ colours in the past. Thus we want the fraction of histories for which $l\gt j$. This is
$$
\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}
$$
Multiplying this by the probability $N^{-\alpha}\exp\left(-N^{1-\alpha}\right)$ and taking the reciprocal yields an improved estimate for the expected number of coupons drawn after the onset of expiration, $N^\alpha\exp\left(N^{1-\alpha}\right)\left(1+N^{\alpha-1}\right)$. Note that the correction doesn't affect the asymptotic behaviour, since $1+N^{\alpha-1}\sim1$.
I also carried out the calculations for two and three additional missing colours, which are a bit more involved. I won't bore you with the details; the result is that the expected number of coupons is multiplied by rational functions of $N^{\alpha-1}$ that go to $1$ for $N^{\alpha-1}\to0$. The expansion only seems to converge for rather small values of $N^{\alpha-1}$, but that doesn't matter asymptotically.
Thus, the analysis suggests that the expected number of coupons drawn after the onset of expiration is asymptotic to $N^{\alpha}\exp\left(N^{1-\alpha}\right)$. This is difficult to test numerically for most $\alpha$, since for $\alpha$ close to $1$ the expansion in $N^{1-\alpha}$ converges very slowly and for $\alpha$ close to $0$ the expected number of draws is prohibitively large. A reasonable compromise is $\alpha=0.8$, for which the following table shows the average number of coupons drawn after the onset of expiration in $5000$ runs for $N=10\cdot2^n$ with $n=0,\dotsc,12$ and $M$ the closest integer to $0.8N\log N$. Also shown is the ratio to the asymptotic result $N^{\alpha}\exp\left(N^{1-\alpha}\right)$ and to the result of the first-order correction, $N^{\alpha}\exp\left(N^{1-\alpha}\right)\left(1+N^{\alpha-1}\right)$. Both ratios appear to be approaching $1$, the corrected one more quickly.
$$
\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}
$$
Here's the code I used to produce the table.
What follows is a computational contribution where we derive a closed
form (as opposed to an infinite series) of the expected number of
draws required to see all coupons at least twice when a number $n'$ of
coupons from the $n$ types where $n' < n$ have already been collected
in two instances. We then observe that the expectation does not
simplify. It seems like a rewarding challenge to compute the
asymptotics for these expectations using probabilistic methods and
compare them to the closed form presented below.
Using the notation from this MSE
link we have from
first principles that
$$P[T = m] = \frac{1}{n^m}\times {n-n'\choose 1}\times
(m-1)! [z^{m-1}] \exp(n'z)
\left(\exp(z) - 1 - z\right)^{n-n'-1}
\frac{z}{1}.$$
We verify that this is a probability distribution. We get
$$\sum_{m\ge 2} P[T=m]
\\ = (n-n') \sum_{m\ge 2} \frac{1}{n^m}
(m-1)! [z^{m-2}] \exp(n'z)
\left(\exp(z) - 1 - z\right)^{n-n'-1}
\\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m}
(m+1)! [z^{m}] \exp(n'z)
\left(\exp(z) - 1 - z\right)^{n-n'-1}
\\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m}
(m+1)! [z^{m}] \exp(n'z)
\\ \times \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} \exp((n-n'-1-p)z)
(-1)^{p} (1+z)^p
\\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m}
(m+1)!
\\ \times [z^{m}]
\sum_{p=0}^{n-n'-1} {n-n'-1\choose p} \exp((n-1-p)z)
(-1)^{p} (1+z)^p
\\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m}
(m+1)!
\\ \times
\sum_{p=0}^{n-n'-1} {n-n'-1\choose p}
\sum_{q=0}^{m}
[z^{m-q}] \exp((n-1-p)z)
(-1)^{p} [z^q] (1+z)^p
\\ = (n-n') \frac{1}{n^2} \sum_{m\ge 0} \frac{1}{n^m}
(m+1)!
\\ \times
\sum_{p=0}^{n-n'-1} {n-n'-1\choose p}
\sum_{q=0}^{m}
\frac{(n-1-p)^{m-q}}{(m-q)!}
(-1)^{p} {p\choose q}.$$
Re-arranging the order of the sums now yields
$$(n-n') \frac{1}{n^2} \sum_{p=0}^{n-n'-1} {n-n'-1\choose p}
\\ \times \sum_{m\ge 0} \frac{1}{n^m} (m+1)!
\sum_{q=0}^{m}
\frac{(n-1-p)^{m-q}}{(m-q)!}
(-1)^{p} {p\choose q}
\\ = (n-n') \frac{1}{n^2} \sum_{p=0}^{n-n'-1} {n-n'-1\choose p}
\\ \times
\sum_{q\ge 0} (-1)^{p} {p\choose q}
\sum_{m\ge q} \frac{1}{n^m} (m+1)!
\frac{(n-1-p)^{m-q}}{(m-q)!}.$$
Simplifying the inner sum we get
$$\frac{1}{n^q} \sum_{m\ge 0} \frac{1}{n^m} (m+q+1)!
\frac{(n-1-p)^{m}}{m!}
\\ = \frac{(q+1)!}{n^q} \sum_{m\ge 0} \frac{1}{n^m}
{m+q+1\choose q+1} (n-1-p)^m
\\ = \frac{(q+1)!}{n^q} \frac{1}{(1-(n-1-p)/n)^{q+2}}
= (q+1)! n^2 \frac{1}{(p+1)^{q+2}}.$$
We thus obtain for the sum of the probabilities
$$\sum_{m\ge 2} P[T=m] =
(n-n') \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} (-1)^{p}
\sum_{q=0}^p {p\choose q}
(q+1)! \frac{1}{(p+1)^{q+2}}.$$
Repeat to instantly obtain for the expectation
$$\bbox[5px,border:2px solid #00A000]{
E[T] = n (n-n') \sum_{p=0}^{n-n'-1} {n-n'-1\choose p} (-1)^{p}
\sum_{q=0}^p {p\choose q}
\frac{(q+2)!}{(p+1)^{q+3}}.}$$
Now to simplify these we start with the inner sum from the probablity
using the fact that
$$\sum_{q=0}^p {p\choose q} (q+1)! \frac{1}{(p+1)^{q+1}} = 1$$
which was proved by residues at the cited link from the introduction.
We then obtain
$$(n-n') \sum_{p=0}^{n-n'-1} {n-n'-1\choose p}
\frac{(-1)^{p}}{p+1}
\\ = \sum_{p=0}^{n-n'-1} {n-n'\choose p+1} (-1)^p
= - \sum_{p=1}^{n-n'} {n-n'\choose p} (-1)^p
\\ = 1 - \sum_{p=0}^{n-n'} {n-n'\choose p} (-1)^p
= 1 - (1-1)^{n-n'} = 1$$
which confirms it being a probability distribution. We will not
attempt this manipulation with the expectation, since actual
computation of the values indicates that it does not simplify as
announced earlier. For example, these are the expectations for the
pairs $(2n', n'):$
$$4,11,{\frac {347}{18}},{\frac {12259}{432}},
{\frac {41129339}{1080000}},{\frac {390968681}{8100000}},
{\frac {336486120012803}{5717741400000}}, \ldots$$
and for pairs $(3n', n'):$
$${\frac {33}{4}},{\frac {12259}{576}},{\frac {390968681}{10800000}},
{\frac {2859481756726972261}{54646360473600000}}, \ldots$$
The reader who seeks numerical evidence confirming the closed form or
additional clarification of the problem definition used is asked to
consult the following simple C program whose output matched the
formula on all cases that were examined.
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <time.h>
int main(int argc, char **argv)
{
int n = 6 , np = 3, j = 3, trials = 1000;
if(argc >= 2){
n = atoi(argv[1]);
}
if(argc >= 3){
np = atoi(argv[2]);
}
if(argc >= 4){
j = atoi(argv[3]);
}
if(argc >= 5){
trials = atoi(argv[4]);
}
assert(1 <= n);
assert(1 <= np && np < n);
assert(1 <= j);
assert(1 <= trials);
srand48(time(NULL));
long long data = 0;
for(int tind = 0; tind < trials; tind++){
int seen = np; int steps = 0;
int dist[n];
for(int cind = 0; cind < n; cind++){
if(cind < np)
dist[cind] = j;
else
dist[cind] = 0;
}
while(seen < n){
int coupon = drand48() * (double)n;
steps++;
if(dist[coupon] == j-1)
seen++;
dist[coupon]++;
}
data += steps;
}
long double expt = (long double)data/(long double)trials;
printf("[n = %d, np = %d, j = %d, trials = %d]: %Le\n",
n, np, j, trials, expt);
exit(0);
}
Best Answer
The expected value of the number of purchases until you have obtained the complete collection is $E_n=\sum\limits_{i=1}^{n}\frac{n}{n-i+1}=n\sum\limits_{k=1}^{n}\frac1k$. For reasons of symmetry $E(X_i)=\frac{E_n}{n}=\sum\limits_{k=1}^{n}\frac1k$ for all $i$.