Coupon Collector Score

Solution 1:

I initially misread the post; this answer computes the expected number of points after $m$ draws, not after getting $m$ distinct draws.

Call a group dead if all of its coupons have been chosen previously, and alive otherwise.

Lemma If there are currently $a$ alive groups, the expected number of points from your next coupon is $a$.

Proof: Suppose you have already $k_i$ coupons from the $i^{th}$ group, for each $i\in \{1,\dots,n\}$. Let $X$ be the number of points from your next coupon. For each $i\in \{1,\dots,n\}$, let $G_i$ be the event that the next coupon is from group $i$.

$$ E[X]=\sum_{i=1}^n P(G_i)E[X\mid G_i]=\sum_{i=1}^n p_i\cdot \left(\begin{cases} \displaystyle\frac{N_i-k_i}{N_i}\times \frac{N_i}{p_i(N_i-k_i)} & k_i < N_i \\ 0 & k_i=N_i \end{cases}\right) =\text{#}\{i\mid k_i<N_i\} $$

Now, let $X_t$ be the number of points you get on draw number $t$, for $t\in \{1,2,3,\dots\}$. Then \begin{align} E[X_t] &= E[\text{# alive groups before turn $t$}] \\&= \sum_{i=1}^n P(\text{group # $i$ alive before turn $t$}) \\&= \sum_{i=1}^n P\left(\bigcup_{j=1}^{N_i}\{\text{$j^\text{th}$ coupon in group $i$ not yet chosen}\}\right) \\&= \sum_{i=1}^n \sum_{j=1}^{N_i} (-1)^{j-1}\binom{N_i}{j} \left(1-p_i\frac{j}{N_i}\right)^{t-1} \end{align}

The last equation is a routine application of the principle of inclusion-exclusion. Therefore, if you draw $m$ coupons total, the expected number of points is $$ \begin{align} \sum_{t=1}^mE\left[ X_t\right] &= \sum_{i=1}^n \sum_{j=1}^{N_i} (-1)^{j-1}\binom{N_i}{j} \sum_{t=1}^m\left(1-p_i\frac{j}{N_i}\right)^{t-1} \\&= \sum_{i=1}^n \sum_{j=1}^{N_i} (-1)^{j-1}\binom{N_i}{j} \frac{1-(1-p_ij/N_i)^m}{p_ij/N_i} \\&= \boxed{\sum_{i=1}^n \frac{N_i}{p_i}\sum_{j=1}^{N_i} (-1)^{j-1}\binom{N_i}{j}\frac1j\cdot \left(1-\left(1-p_i\frac{j}{N_i}\right)^m\right)} \end{align} $$