Grading a class

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.


  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.

This entry was posted in Asymptotics, Combinatorics, Computation, Probability. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s