Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.