Imagine we had a class with ${N}$ students and each week they hand in a sheet of homework. Now, you choose a set of ${M}$ of them at random and correct only those ${M}$. At the end, the grade assigned to a student is the average among all of his homework sheets that you corrected. How many weeks does it take for every student to have a grade?

Comment: I came up with this question because I have implemented such a system and I wanted to choose ${M}$ wisely as to have a grade for each student every ${4}$ weeks.

Coupons collector problem.

It is easy to see that this problem is related to the classical coupon collector problem. The problem reads as follows: you have ${N}$ coupons and each time you buy one (picked uniformly at random from the ${N}$ possible ones) and the question is how long it takes you on average to get the full collection. The answer here is

$\displaystyle {\mathbb{E}}[T] = N H_N\,,$

where ${T}$ is the random variable corresponding to the number of coupons it takes you to get the full collection, and ${H_N = 1+\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{N}}$.

The proof follows easily upon noticing that, once you have ${i}$ different coupons, you have to wait on average ${\left(\frac{N-i}{N}\right)^{-1}}$ to get a new one.

It is also not difficult to prove that, even though what we have above is the expected value, the actual value of ${T}$ is usually not much bigger than ${N\log N}$ (remember that we may estimate ${H_N \approx \int_1^N\frac{dx}{x}=\log N}$). Indeed,

$\displaystyle \Pr\left(T > k\right) \leq N \, \left(1 - \frac{1}{N}\right)^k\leq N \,\exp(-k/N)\,,$

because ${\left(1 - \frac{1}{N}\right)^k}$ is the probability of never getting (up to time ${k}$) a given coupon. The event ${T > k}$ is the union of the events “not getting a given coupon”, thus we have bounded the probability of the union with the sum ${\Pr(\cup_i A_i)\leq \sum_i \Pr(A_i)}$.

Thus, if ${k = N \log N + c\,N}$ we get

$\displaystyle \Pr\left(T > N \log N + c\,N \right) \leq e^{-c}\,.$

Teacher’s problem. Back to our problem, if ${T}$ represents the number of weeks it takes us to have a grade for every single student, intuitively we should have (${M>1}$)

$\displaystyle \mathbb{E}[T] \leq" \frac{N}{M} H_N \,.$

If we look at the sequence of sets of ${M}$ elements we get, and we write them all in a line in some order, we get a possible outcome for the coupons collector problem… but it is a bit better than in the coupons collector’s case, because we are guaranteed that the first ${M}$ coupons are distinct, the second group of ${M}$ coupons are distinct, and so on. What is better, these cases have higher probability than before, so one expects to have such an inequality (I am not claiming this constitutes a proof!). This establishes, though, the parallel between the two problems, now we expect to have nearly the same results, but with a factor of ${1/M}$ involved.

We note that the probability of never getting a given student ${i}$ in ${k}$ iterations is

$\displaystyle \left(\frac{\binom{N-1}{M}}{\binom{N}{M}} \right)^k = \Big( 1 - \frac{M}{N} \Big)^k \leq \exp\left(-k\,\frac{M}{N}\right)\,.$

Thus we also get

$\displaystyle \Pr(T > k) \leq N \exp\left(-k\,\frac{M}{N}\right)\,.$

Considering ${k = \frac{N}{M} \log N + \frac{N}{M} c}$ we get

Proposition 1 We have the bound

$\displaystyle \Pr\left(T > \frac{N}{M} \log N + \frac{N}{M} c\right) \leq e^{-c}\,.$

This means that we never wait much more than ${\frac{N}{M} \log N}$ weeks. However, is ${\frac{N}{M} H_N}$ the expected value as in the case of the coupons collector problem? The answer is negative, but I claim that asymptotically this is not far from the truth.

Proposition 2 We have

$\displaystyle \lim_{N\rightarrow\infty} \Pr\left(T > \frac{N}{M} \log N + \frac{N}{M} c\right) = 1 - e^{-e^{-c}}\,.$

Proof: Indeed, we note that bounding the probability of the union by the sum of the probabilities is just the first term of the inclusion-exclusion process, if we continue we get the so-called Bonferroni’s inequalities

$\displaystyle \sum_{j=1}^{2h} (-1)^{j+1}\binom{N}{j}\,\left(\frac{\binom{N-j}{M}}{\binom{N}{M}} \right)^k \leq \Pr\left(T>k\right) \leq \sum_{j=1}^{2h+1} (-1)^{j+1}\binom{N}{j}\,\left(\frac{\binom{N-j}{M}}{\binom{N}{M}} \right)^k\,, \ \ \ \ \ (1)$

for all ${h\geq 0}$. Here we note that

$\displaystyle \frac{\binom{N-j}{M}}{\binom{N}{M}} = \left(1-\frac{M}{N}\right)\,\left(1-\frac{M}{N-1}\right)\ldots \left(1-\frac{M}{N-j+1}\right) \ \ \ \ \ (2)$

whenever ${j < N}$ (else it is ${0}$). So fixing any ${h\geq 0}$ and ${M}$, letting ${N\rightarrow \infty}$

$\displaystyle \binom{N}{j} \,\left(\frac{\binom{N-j}{M}}{\binom{N}{M}} \right)^k \sim \frac{N^j}{j!} \,\exp\left(-k\,j\,\frac{M}{N}\right)\,,$

for ${j\leq 2h+1}$, which already suggests the claimed result. To actually get it, we must make a better estimate of the remainder term. Note that, in (2) we have

$\displaystyle \left(\frac{\binom{N-j}{M}}{\binom{N}{M}} \right)^k = \left(\left(1-\frac{M}{N}\right)\,\left(1-\frac{M}{N-1}\right)\ldots \left(1-\frac{M}{N-j}\right)\right)^k$

which equals, taking logs and using ${\log(1-x)=-x-x^2/2-x^3/3\ldots}$

$\displaystyle \exp\left(-k \left(\sum_{i=0}^j \sum_{n\geq 1} \frac{(M/(N-i))^n}{n}\right)\right)$

Here we may rewrite this as

$\displaystyle = \exp\left(-k \sum_{i=0}^j M/(N-i) - k \sum_{n\geq 2} \sum_{i=0}^j \frac{(M/(N-i))^n}{n}\right)$

and the second term is quadratic

$\displaystyle \exp\left(-k\,j\,\frac{M}{N} + O(k/N^2)\right)\,.$

Hence if ${k=(N/M)\log N + \frac{N}{M}\,c + o(N)}$ we get

$\displaystyle \binom{N}{j} \,\left(\frac{\binom{N-j}{M}}{\binom{N}{M}} \right)^k = \frac{N^j}{j!}\left(1+O(1/N)\right) \, \exp(-k\,j\, M/N) \left(1 + O(\log N / N)\right)$

so that

$\displaystyle \binom{N}{j} \,\left(\frac{\binom{N-j}{M}}{\binom{N}{M}} \right)^k= \frac{(e^{-c})^j}{j!} + O(\log N / N)$

because ${\exp(-k\,j\, M/N) = e^{-c\,j}/N^j = O(N^{-j})}$. Thus, from (1) we get

$\displaystyle \sum_{j=1}^{2h} (-1)^{j+1} \frac{(e^{-c})^j}{j!} \leq \liminf_{N\rightarrow\infty} \Pr\left(T>k\right) \leq \limsup_{N\rightarrow\infty} \Pr\left(T>k\right) \leq \sum_{j=1}^{2h+1} (-1)^{j+1}\frac{(e^{-c})^j}{j!}\,, \ \ \ \ \ (3)$

but the two extremes converge to ${1-e^{e^{-c}}}$ as ${h\rightarrow\infty}$, thus the result. $\Box$

Applying this to my class. In my case I usually have ${16}$ students and I would like ${T}$ to be ${4}$ so I will want to have

$\displaystyle \frac{16}{M} \log 16 + \frac{16}{M} c = 4\,,\qquad e^{-c}=1/10\,,$

in order to apply our inequality and have at most ${10}$% of probability leaving out some student… thus ${c = \log(10) \approx 2.3}$ and ${M \approx 20.3}$ (which is, of course, nonsense… because then ${M>N}$). The problem here is that we are making a gross estimation for such a small ${N}$, thus, in fact, looking more directly at

$\displaystyle \Pr(T>4) \leq N \left(1 - \frac{M}{N}\right)^4$

and setting ${N \left(1 - \frac{M}{N}\right)^4 = 1/10}$, we get ${M\approx 11.5}$, i.e. ${M\geq 12}$. The actual minimal value of ${M}$ is indeed ${12}$… by inspection, bad news for me (I was using ${M=6}$). In fact, to have probability roughly 1/2-1/2, we must pick ${M=9}$.

This proof is essentially that of [1] for the Coupon’s Collector problem.

References

1. Erdős, Paul; Rényi, Alfréd (1961), On a classical problem of probability theory (PDF), Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 6: 215–220.