I'm trying to solve the problem of 100 prisoners and light bulb using generating functions.
The problem is a random prisoner out of 100 is sent a room with a light bulb in it each hour. How can you guarantee that all prisoners have been in the room at least once and what is the expected number of turns for this?
Solution is prisoners choose 1 person among themselves calling him counter. If a prisoner enters the room he turns the light on if it is off and leaves it if it is on but each prisoner turns the light on only one time ie if a prisoner turned the light on once he will not do so again. When counter enters he turns the light off if it is on and leaves it if it is off. This way if counter turns the light off 99 times they guarantee that everyone has been in the room.
Now if x^k denotes the probability that this process ends in k turns i can use the generating function of x^k's to find the expected value. However i have no idea how i can find the probability.
Generating functions don't look like the right way to go to me, because as you say, it will be difficult to calculate the probability that the process takes a particular number of turns. Instead, I suggest you attack it like the coupon collector's problem. Suppose $k$ prisoners, other than the counter have entered the room. We need the counter to enter the room and turn of the light and then we need some prisoner who has not yet entered to enter the room.
The probability that the counter is chosen to enter the room is ${1\over100}.$ Since we have a geometric distribution the expected number of turns until he enters the room is $100$. Then we need a new prisoner to enter. There are $99-k$ new prisoners, so the expected number of turns until one of them enters is ${100\over99-k}.$
I'm certain you'll be able to work it out now. One note of caution though: the answer depends on whether the light is initially on or off.