This would work of course, but is it optimal? For instance, this would also work, I think:

Alice counts the times she finds the light on, and ensures that it is always off when she leaves the room. Everyone else turns on the light the first time they find it off, and then never touches it again. This way, between visits of Alice, at most one prisoner will turn on the light, and no prisoner turns it on more than once. Therefore the number of times Alice finds the light on is no more than the number of different prisoners that have entered the room. Each prisoner knows he has been counted once he has turned the light on, since he is the only one who touched the switch since Alice last visited. When Alice counts to n-1, she knows everyone has visited the room.

What does optimal mean here? It could only reasonably mean that the prisoners are freed in the shortest time. So what is the expected time they must wait until Alice has counted to n-1? This is a rather elaborate calculation in probability, so the prisoners turn to the actuary (who is in prison for embezzlement) for some answers.

He explains that using Bayes theorem, P(X|Y)*P(Y) = P(X&Y) = P(Y|X)*P(X) and the linearity of expected value, E(X|Y)*P(Y) + E(X|~Y)*P(~Y) = E(X) you can calculate the expected time in prison like this:

Suppose Alice has just visited the room, and let K be the number of days that pass before her next visit (so she visits again K+1 days from now), let n be the number of prisoners, let c be the number of times she has found the light on so far, and let P(ON) and P(OFF) be the probabilities that she finds the light on or off on her next visit. Then E(K)=1/n, P(K=k) = 1/n*((n-1)/n)^k, P(K=k|OFF) = 1/n*(c/n)^k, which are fairly obvious.

Bayes theorem then gives P(K=k|OFF) = (1-c/n)*(c/n)^k, and from this you can calculate E(K|OFF) = c/(n-c). and linearity gives E(K|ON) = ((n-1)(n-c)-c/(n-c))/(n-c-1). Now let m be the number of times Alice visits and L be the number of days that pass before she next finds it on. Each time she finds it is off, c does not change, so all the calculations regarding the time until her next visit also do not change.

Therefore, the expected number of days until she next finds the light on is found by summing over all possible m to get the expected total time wasted on visits where the light is off, plus the expected time for the one visit where it was on. This gives E(L) = (1+E(K|ON))P(ON) + sum(m(1+E(K|OFF))P(OFF)^m = n(1/(n-c-1) - 1/(n-c) + 1 - 1/(n-c)^2).

Now we know how long we expect to wait from count = c to count = c+1. Therefore, we must sum this up from c=0 to c=n-2 to find the total expected time E(T). The result is E(T) = n^2 - n/(n-1) - a, where a = sum(1/c^2) from 2 to n. Putting n=100 into this gives 9935.5 days, which is 26.2 years.

But (continues the actuary) this is absurdly long to wait. Simple probability shows that we can be almost certain much sooner than this. The probability that on day d the count is c is P(c,d), which is obviously equal to P(c-1,d-1)*(1-(c-1)/n) + P(c,d-1)*(c/n). Of course, P(0,0) = P(1,1) = 1 and P(1,0) = 0, so we can recursively calculate the probability P(n,d). It turns out that P(100,1146) = 0.999, and P(100,1375) = 0.9999, P(100,1604) = 0.99999, and P(1833) = 0.999999. That means that in 3.14 years, we have a less than 1/1000 chance of failing, and in exactly 5 years and a week, we have less than one in a million chances of failing. I say we should wait 5 years and then say "let us out, we've all seen the light."

As they are about to kill Alice (who was already a member of Mensa) for coming up with a crazy plan to keep them in prison for 26 years, the game theorist (who is in prison for insider trading on the stock market) steps in to point out that this is a losing move. If they kill her now she will never go into the room, and the warden will keep them here forever.

In the happy ending, they let Alice live, and they all get out of prison in 5 years. Strangely, they all decline to join Mensa, preferring to enter actuarial training.

--Stuart Anderson

It's a pleasure seeing you having fun.

>Alice counts the times she finds the light on, and ensures
>that it is always off when she leaves the room. Everyone
>else turns on the light the first time they find it off, and
>then never touches it again. This way, between visits of
>Alice, at most one prisoner will turn on the light, and no
>prisoner turns it on more than once. Therefore the number
>of times Alice finds the light on is no more than the number
>of different prisoners that have entered the room. Each
>prisoner knows he has been counted once he has turned the
>light on, since he is the only one who touched the switch
>since Alice last visited. When Alice counts to n-1, she
>knows everyone has visited the room.

The problem may be in that the original state of the light is not known. You must account for both possibilities.

Your approach will work if originally the light was off. If it was on and Alice counted it as 1, she is bound to cause an action no one of her fellow prisoners would appreciate. However, if she decides to skip the first count and originally the light was off, she will never reach the revelation point.

>
>What does optimal mean here? It could only reasonably mean
>that the prisoners are freed in the shortest time.

Or, perhaps, the least count that would assure the prisoner release.

>Your approach will work if originally the light was off. If
>it was on and Alice counted it as 1, she is bound to cause
>an action no one of her fellow prisoners would appreciate.
>However, if she decides to skip the first count and
>originally the light was off, she will never reach the
>revelation point.
>
Actually, this is easy to fix. Just add a rule that whoever is picked to go to the room the first day must turn out the light, and then revert to the original rules starting from day 2. This adds one day to their 26.2 year wait.

By the way, I am thinking of this problem as a programming problem, in which there is a controlling process (Alice) that receives a series of 1-bit semaphore flags from some other processes in a message register which is only checked occasionally. Since she can only receive 1 bit, and there is no possibility of somehow encoding extra information into only 1 bit, at most one other prisoner can send her a signal. She must reset the register to a known state so that she can detect the next flag sent, and the other prisoners must not overwrite each other's flags, so only one prisoner may touch the switch between visits from Alice. It was this line of thinking that led me to set up the prisoners' protocol the way I did. This is also where the idea came from in the paragraph just above this one: I am simply initializing the register. It's just "startup code."
>>
>>What does optimal mean here? It could only reasonably mean
>>that the prisoners are freed in the shortest time.
>
>Or, perhaps, the least count that would assure the prisoner
>release.

Well, yes, now that you mention it, although of course the shortest time to freedom would be more to the prisoners' taste. I suspect that the least count would also be the shortest time, but this is not completely clear. For example, Alice needs to count to n-1 in my solution, 2n-3 in yours, but since each prisoner turns the light switch twice, she is twice as likely to detect a signal in the solution you presented, and therefore will increment her count more often. Possibly both solutions lead to approximately the same total waiting time.

Another type of optimality occurs to me now: minimizing the amount of information the other prisoners have to remember. In one solution each prisoner has to remember which of 2 states he is in (I have turned on the light 0 or 1 times before), and in the other, which of 3 states he is in (I have turned on the light 0, 1, or 2 times before). In human terms, the prisoners might forget after a lapse of years, whether they turned the light on once or twice (disastrous!), but they are less likely to forget whether they turned it on at all. In programming terms, the other processes need an internal buffer to hold their current state, and this buffer is smaller (1 bit) with two states than with three states (2 bits). The Alice process needs n states instead of 2n-2 as well.

Come to think of it, this question would make a good problem assignment for an electrical engineering course: design a set of interacting finite state machines with a shared one bit register that solve this problem. In order to do this, they must be good at translating outcome requirements into protocols and protocols into hardware. Of course, most students don't like to be challenged this much, so they would probably complain that the assignment was "unfair."

--Stuart Anderson

I missed that. I just recognised the problem "holistically", as I remembered it from some time ago, without actually reading it.

>Perhaps there are other variants of this
>problem on the internet with different starting assumptions,
>such as an unknown initial bulb state, and the solution you
>presented is for one of those.

Does not look like it. The only discernable difference (besides the initial condition) is that the prisoners are sent to that room "infinitely often, but in a some arbitrary order determined by their jailer." Curious why Winkler settled for 2 actions instead of 1.

>>Your approach will work if originally the light was off. If
>>it was on and Alice counted it as 1, she is bound to cause
>>an action no one of her fellow prisoners would appreciate.
>>However, if she decides to skip the first count and
>>originally the light was off, she will never reach the
>>revelation point.
>>
>Actually, this is easy to fix. Just add a rule that whoever
>is picked to go to the room the first day must turn out the
>light, and then revert to the original rules starting from
>day 2. This adds one day to their 26.2 year wait.

Right.

>By the way, I am thinking of this problem as a programming
>problem, in which there is a controlling process (Alice)
>that receives a series of 1-bit semaphore flags from some
>other processes in a message register which is only checked
>occasionally.

Winkler spends 1.5 page proving an additional fact that, for n > 2 there could be only 1 controlling process, in the sense that an arrangement wherewith more than 1 fellow gets a chance to determine with certainty that all prisoners went to the room is impossible.

Now, at the risk of appearing denser than I really am, let me quote from your message:

"Suppose Alice has just visited the room, and let K be the number of days that pass before her next visit (so she visits again K 1 days from now), let n be the number of prisoners, ... Then E(K)=1/n,..."

I would assume that, as n grows, the wait period grows as well. Thus E(K)=1/n does not seem right.

That's interesting; it never occured to me to consider more. I should think it was fairly obvious that only one is possible. Ultimately, some single counter (let's say Alice but it could be any of them) must become certain that all the prisoners have visited the room. If there is more than one counter, this information must come at least partly by communication from the other counters. But there is only one channel of communication, and it only holds one bit, so there is no way for a counter to know whether a signal is coming from another counter or a regular prisoner. Therefore it is impossible for a counter to respond differently to another counter than to a prisoner, so the counter must simply increment her count, just as she would with an regular prisoner.

Therefore the only signal a counter can send to another counter means "increment your count." Her only choice is of the circumstances under which to send it. If she is to transmit to other counters the number of prisoners she has counted, she must signal once for each such prisoner. But she has no control over who receives the signal--in fact, she may receive it herself, and will have no way to know. Therefore, she might increment her own count, and thus overcount the prisoners. This of course destroys the whole scheme.

>I would assume that, as n grows, the wait period grows as
>well. Thus E(K)=1/n does not seem right.

Thanks, that was my mistake. I worked this out on a blackboard, misread my own handwriting and typed what I saw. It should be E(K)=n-1, which I misread as n^(-1) and typed as 1/n, completely obscuring the connection to the original. The calculations are of course based on the correct value, n-1.

I see that Sheridan beat me to posting the way around the problem of an indeterminate initial bulb state. That's what I get for taking so long writing without checking the page for updates.

--Stuart Anderson

If the first time you see the bulb it is on, turn it off and then never change it again. When you next see it on, declare that all prisoners have visited the room.

If the first time you see the bulb it is off, turn it on and then never change it again.

Then certainly they will be freed, but there is no controlling process. It is possible to set up strategies with no controlling process in all the variations I am aware of. However, there are some variations in which there must be a single process which obeys different rules to the others.

Thankyou

sfwc
<><

Prisoner A enters the room on day one and finds the light off, so he turns it on.
Prisoner B enters the room on day two and finds the light on, so he turns it off and notes that he first saw the light on.
Prisoner C enters the room on day three and finds the light off, so he turns it on.
By chance, Prisoner B is called again to the room on day four, finds the light on, reports that everyone has entered the room, and the prisoners are all killed.

Obviously they cannot all have visited by day 4 if there are 100 prisoners. Am I missing something?

--Stuart Anderson

Never mind; I missed seeing your first paragraph because there was no space between it and the quoted material. Sorry! Your example certainly seems to work for three prisoners. Do you have any examples of strategies that work with many prisoners and yet have no single overall controlling process?

--Stuart Anderson

One day Alice wins them all their freedom by declaring that they have all been in the room. The previous day, of course, Bob was in the switch room. Because he had been in so often, he had gathered a lot of information. As much, in fact, as Alice has the following day. So he knew that everyone had been in the room. But he pedantically stuck to the strategy as given and did not declare this fact. This caused him a good deal of frustration, which was not helped by the warden's evil cackling at the success of his ploy.

Now, with hindsight, Bob concieves of a new strategy, just like the old one except that a person in his situation may declare that everyone has in fact been in the room. Of course this strategy is certain to work, but it now has no single overall controlling process, since any of the prisoners may make the declaration which wins them their freedom. This is an example of such a cheating strategy.

However, it may be shown for some versions of the problem that if there are at least 4 prisoners there is at least one prisoner in any winning strategy who follows a set of rules different to the rules of any other prisoner.

Thankyou

sfwc
<><

I just remembered of my intention to give your response more publicity than it gets in the forum, as it certainly deserves. I thus made a page out of it, of which I hope you approve.

(http://www.cut-the-knot.org/Probability/LightBulbs.shtml)

Thank you,
Alex

Yes, thank you! I am very happy that you thought well enough of it to include it as a page.

However, I was embarrassed to find that I had made a typo in one of the formulas in my original post:

In the paragraph

Suppose Alice has just visited the room, and let K be the number of days that pass before her next visit (so she visits again K+1 days from now), let n be the number of prisoners, let c be the number of times she has found the light on so far, and let P(ON) and P(OFF) be the probabilities that she finds the light on or off on her next visit. Then E(K) = 1/n, P(K=k) = 1/n·((n-1)/n)^k, P(K = k|OFF) = 1/n·(c/n)^k, which are fairly obvious.

the very last formula should be P(K = k & OFF) = 1/n·(c/n)^k.

Also, since it it now a separate page on its own, it might be nice to clarify one step of the calculation for those who didn't read it in the context of the thread. Since you have to calculate P(OFF) before you can apply Bayes theorem, I would suggest adding the following sentence at the start of the very next paragraph:

"Summing the last formula over all k gives P(OFF) = 1/(n-c)."

Thanks again for making a page out of this.

--Stuart