# A combinatorial problem in probability.

A class has a set of students say N, the teacher passes the attendance roster to any one of the N students randomly. Now each student when given the roster, first checks if they already signed it, if not they sign it. Then the student check if the roster contains N signatures, if so the student hands the roster back to the teacher, otherwise he randomly selects one student and passes the roster. In average how many student the roster will be passed on before being handed over to the professor? What if each student cannot pass the roster to every other student instead only to a limited number of students. Lets say it is D, and this number is same for all students (i.e, the students passing graph is D-regular) what will be the average value of number of passes?

-
I think the first question is what's known as "the coupon collector's problem", and you will probably find much discussion of it under that name. – Gerry Myerson Sep 11 '13 at 13:38

What you are looking for is the average over all nodes $u$, of the "cover time starting from $u$" (see http://www.mpi-inf.mpg.de/departments/d1/teaching/ws11/SGT/Lecture7.pdf) of the "students passing graph" you mentioned.

-