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?
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.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.