Here's my solution to the problem. I used MS Excel. You must click "Enable Macros" for it to work.

https://tinyurl.com/2smwyy

Feel Free to Share with others or give me your input.

Thanks,
Dan

I am not sure this formula is correct. If we are looking at the probability on one day for a prisoner who has never turned on the light before to enter the room and find the light off, then it makes obvious sense to talk about fractions like c/n or 1-(c-1)/n. However, the c-1’th time the leader finds the light on can occur on between about 2c and d-2’th days. The multiplications of simple fractions 1-(c-1)/n and c/n are not, at least, obvious to me, even if it is correct.

Can you or Stuart Anderson explain? Thanks.

The error is that, in the first part of my solution, I was counting days BETWEEN Alice's visits, hence Alice herself was not included as a potential visitor on those days. However, in the second part, where I estimated the probability of all prisoners having visited as a function of time, I needed to include the possibility of Alice's visits.

Note that the formula calculates the probability for day d based on the immediately previous day, d-1. There are precisely two ways of arriving at count c on day d, based on the situation at day d-1: either the count was c-1 on day d-1, and on day d the light was turned on, or else the count was already c, and on day d the light was not turned on.

In the first case, c-1 of the n prisoners had already turned the light on, and Alice (whom I had forgotten to include) never turns it on. Thus there is a (c-1+1)/n = c/n chance that it will not be turned on at day d, hence a 1 - c/n chance that it will be turned on. In the second case, c of the n prisoners have already turned it on, and including Alice makes c+1 prisoners who will not turn on the light; hence there is a (c+1)/n chance that it will not be turned on in this case.

Since these cases exhaust the possibilities for day d-1, the probability P(c,d) = P(c-1,d-1)·(1-c/n) + P(c,d-1)·(c+1)/n. As you can see, this is the same as the formula I gave, with the value of c increased by 1 to account for Alice.

I see one further error later on the same line as well. I mentioned that P(0,0) = P(1,1) = 1 and P(1,0) = 0. The first and last of these are true, and are sufficient to start the recursion. But P(1,1)=1 is false, since it is possible that Alice visits the room on the first day. In fact, you can compute P(1,1) = P(0,0)·(1 - 1/n) + P(1,0)·(2/n) = 1-1/n, again because of the possibility of Alice visiting. This does not affect the calculation I did that results in a time of 5 years + 1 week for 0.999999 chance of success, since the recursion I used started at day 0, so I never actually made use of P(1,1). It is fortunate when the part which is wrong is also redundant!

However, the error in the formula DOES affect the numerical calculation. I'll re-run it and see how much differenc it makes. My guess is not much, but we'll see.

Hope that makes the situation clearer!

--Stuart Anderson

I agree with you analysis of the problem until this point:

>In the first case, c-1 of the n prisoners had already turned
>the light on, and Alice (whom I had forgotten to include)
>never turns it on. Thus there is a (c-1+1)/n = c/n chance
>that it will not be turned on at day d, hence a 1 - c/n
>chance that it will be turned on.

This is exactly the point I had question about in the last post. This is either incorrect or it takes more convincing than the above statement. The first day the count reaches c-1 may be way before d-1. During the interim between the first day the count reaches c-1, which we call day f and day d, where I want to stress that the number of intervening days may well be larger than 1. If we denote one of those c-1 prisoners who have turned on the light before day f as b, and Alice as a, the rest of the prisoners as c, some of the possible events between f (excluding f) and d could be

bbbacccba
accbcbca
…

Are you indicating with all those possibilities and varying f, the event (c,d) coming from (c-1,d-1) is only a simple multiplication of 1-c/n, same as waiting one day in between f and d, or f-d=2? It'seems too good to be true. If it is, it is, as I said in my previous post, not obvious. It requires a proof. I can not see it immediately.

My same skepticism applies to the second case:

> In the second case, c of
>the n prisoners have already turned it on, and including
>Alice makes c+1 prisoners who will not turn on the light;
>hence there is a (c+1)/n chance that it will not be turned
>on in this case.

I think you're overcomplicating things. The idea I had was to set up a simple recursion, as follows: suppose you ALREADY know the probabilities at day d for all count possibilities c = 0, 1, ... d. From this, you can calculate the probabilities for all count possibilities c=0, 1, ... d+1 for day d+1. In other words, if you know how things stand today, you can calculate the probabilities for tomorrow; you don't need to know how you arrived at today's situation. In fact, since today's probabilities are calculated from yesterday's, and so on, all possible ways of arriving at today's count are already taken into consideration.

This doesn't seem to me to require a formal proof, but here goes:
Let A be the case that on day d the count is c,
let B be the case that on day d-1 the count is c,
let C be the case that on day d-1 the count is c-1.
Since in general probability obeys the law P(X) = P(X|Y)·P(Y) + P(X|~Y)·P(~Y), you can write
P(A) = P(A|B)·P(B) + P(A|C)·P(C) + P(A|~(B or C))·P(~(B or C)).
Now the third of these terms must be zero, since between day d-1 and day d, the count must increase by either 0 or 1. Therefore, in the case ~(B or C), the count on day d-1 was neither c nor c-1, so it is impossible to reach count c on day d. Hence P(A|~(B or C)) = 0.
The remaining two terms are precisely the cases I identified, since P(A|B) is the probability that the prisoner who entered on day d did not turn on the light, while P(A|C) is the probability that he/she did. QED

Note that this recursion requires you to know ALL the probabilities of the various counts on the current day and from them you get ALL the probabilities of the various counts on the next day. It doesn't work if you only know some of them. Fortunately, on day 0, no one has entered the room, so P(c=0) = 1 and P(c<>0) = 0, so you have enough information to get started.

The whole calculation looks rather like Pascal's Triangle:

                        1
        1/n                         (n-1)/n
1/n·1/n     (n-1)/n·1/n + 2/n·(n-1)/n     (n-2)/n·(n-1)/n

Does that clear it up?

--Stuart Anderson

I am sorry, but I do not think it is any clearer.

I understand the conditional probability formulation. However, my question has always been and you have not shown why P(A|B) and P(A|C) are simple as (n-c)/n and (c+1)/n. As a matter of fact, I highly doubt they are.

What I am saying is P(A|B) (P(A|C)) is not independent of B(C) in your present formulation, specifically as B is the count, or the number of times the light is (on then) off.

I think I've identified the trouble. We have a miscommunication here, and upon rereading my original solution, I think it is my fault. There are two slightly different problems which the actuary in my story solves. First, how long until we should expect that Alice KNOWS that all prisoners have visited the room, and second how long until we should expect that IN ACTUAL FACT all prisoners have visited the room. This distinction comes about because in the first case, Alice has to declare that all have visited, so she has to know, while in the second case, the prisoners declare they have visited after 5 years because they deem it'safe to do so. Note that Alice's knowledge does not figure into the second problem at all.

Therefore, I should have been careful in my solution to mention this difference explicitly. What this means is that the definition of c is slightly different. In the first problem, it is the number of times Alice has found the light on, while in the second problem, it is simply the number of prisoners who have visited the room. So in the first one, the count increments when Alice FINDS the light on, but in the second case it increments when a new prisoner VISITS the room. I never made this explicit, because it never occured to me to consider waiting around for Alice to notice, when what I was after was the earliest date when everyone had ACTUALLY visited the room. Sorry for the lack of clarity there.

This also means that I should retract the correction I made to my formula. The correction was the result of reading your post, which, combined with the lapse of 3 years since I looked at this problem, caused me to forget that I wasn't assigning a special role to Alice in the second problem. So the original formula is correct.

If on day d-1, c-1 prisoners have visited the room at least once, and if a new prisoner visits the room on day d, then on day d the count will be c. If on day d-1, c prisoners have visited the room, and if one of the old prisoners visits the room on day d, then on day d the count will be c. These are the only two ways the count can be c on day d. In the first case, it is required that one of the new prisoners (of whom there are n-(c-1)) visit the room, and since they are chosen randomly each day, the probability is (n-(c-1))/n = 1 - (c-1)/n. In the second case, it is required that one of the old prisoners (of whom there are c) visit the room, and the probability is therefore c/n. Then my formula follows. My initial conditions are also correct as stated in the original solution, since on day 0, necessarily 0 prisoners have visited, and on day 1 necessarily 1 prisoner has visited.

Alice plays no role in this calculation, because it is not necessary for anyone to know how many prisoners have visited the room, only to estimate how many actually have done so as a function of time. Does that clear it up?

It's been nice discussing this with you. You made me think more clearly about my solution.

--Stuart Anderson

The definition of c in the first part and the intended new definition in the second part of your solution are very different, not just a bit. It is very confusing to not only not declare the variable but reuse the same symbol. It would be great if you can modify the solution for the benefit of others.

As a matter of fact, a similar recursion holds for computing the probability of Alice declaring the end of captivity on day d, if c is redefined as the number of switches (not Alice' count of prisoners) made so far, with care taken for c being even and odd.

I think this would be a nice addition to your solution.

Thank you for giving more careful consideration to this problem, Stuart.

OK, now we're in complete agreement. The difference between the two definitions of c seemed minor to me, because I started with the "Alice counts" version, and then simply dropped consideration of Alice. However, I agree that the structural difference between the two definitions is rather large, inasmuch as (as you point out) the recursion must be done quite differently when Alice counts occurences.

It is also clear that it is exactly the necessity of waiting for Alice which slows things down so much. This is because consecutive visits by new prisoners are not counted unless Alice has been there to turn off the light between their visits. Therefore, the number of counts falls far behind the number of visits. Most of the missed visits will be at the beginning, because as time goes on, the remaining number of uncounted prisoners decreases, and so does the probability that several will visit in succession without a visit by Alice intervening.

It'seems to me also (as you said) that a recursion could easily be made to include Alice. In fact, it could be a simple modification of the one I stated, as follows: Let the variable be named s rather than c, to emphasize that we are counting the number of times someone moved the switch. Now s changes from even to odd if a new prisoner enters ("new" meaning one who has not yet moved the switch), which has probability s/(2n). Also, s changes from odd to even if Alice enters, which has probability 1/n. Therefore, the recursion should be:

For ODD s, P(s, d) = P(s, d-1)·(1-1/n) + P(s-1, d-1)·(s-1)/(2n)
For EVEN s, P(s, d) = P(s, d-1)·(1-s/(2n)) + P(s-1, d-1)·(1/n)

Does that look right to you?

I had already computed the expected time for Alice to declare (which was probably the most relevant number from the prisoners' point of view), and this adds a probable count as a function of time. As for the second part of my original solution, that provided a probable number of visits as a function of time, so for completeness, I should also compute the expected time until all prisoners have visited (which is not something the prisoners would care about, since it gives no indication of when it is safe to say they've visited). If I can still find the spreadsheet I set up for that 3 years ago, I'll run the numbers. Or I could just redo the sheet, it's simple enough.

The next step would be to ask Alex if he would please update the solution, once I produce the text I want to add.

--Stuart Anderson

Stuart, of course. I am just back from vacation. After a night's sleep I'll be capable of modifying a page. It is a pity it is not a wiki. If you have anything else in mind, I can send you a password to the wiki part of the site for direct entry.

For ODD s, P(s, d) = P(s, d-1)·(s+1)/(2n) + P(s-1, d-1)·(1-(s+1)/(2n))
For EVEN s, P(s, d) = P(s, d-1)·(s/2+1)/n + P(s-1, d-1)·(1/n)
----------------

Also, I do have a bone to pick at this point. I beg to differ that the definition of count is a minor issue. First, it is only what you say counts (excuse my pun), not what you intend to say, especially in mathematics. Also in practice, it is as if to say it does not matter much whether you use your personal income or the GDP of US to calculate the tax you have to pay, because these two are both incomes. For the particular problem at hand, it is a life or death issue for those prisoners.

I apologize if the last paragraph of my last post came across as a bit obnoxious. I simply wanted to emphasize that a consistent and clear definition is necessary. Thank you.

Nightrider

As it happens, we were both wrong. I neglected to invert the probability for the transition from even to odd, so this sentence should now read:
"Now s changes from even to odd if a new prisoner enters, ..., which has probability 1-s/(2n)."

The (s+1) in your formula represents a difference in interpretation of s, I think. As is usual, I am using the OLD value of s, which represents the situation as it exists, to compute the probability of the NEW value of s. It'seems that you are constructing your formula based on the new value of s. Both are valid, but I think it is more standard to do it the way I did it. Of course, the solution is to remove the ambiguity from my statement.

Since you agree about the odd-to-even transition probability, your term for that case (and its negation) should match mine. If only Alice's visit is relevant, the probability cannot depend on s in that case. Also, everywhere in your formula, the value of s needs to be replaced with s-1 whenever the switch count was s-1 on the previous day.

Therefore, the formulas should be

For ODD s, P(s, d) = P(s, d-1)·(1 - 1/n) + P(s-1, d-1)·(1-(s-1)/(2n))
For EVEN s, P(s, d) = P(s, d-1)·s/(2n) + P(s-1, d-1)·(1/n)

To see more definitely why the earlier formulas are incorrect, note that it is obvious that P(0, 0) = 1, P(1, 0) = 0, and P(1, 1) = 1. Applying my earlier formula to compute the last of these from the first two gives 0, while your formula gives 1 - 1/n, neither of which is correct. The new formula gives the correct result, and as I've checked its derivation more thoroughly, I'm confident that it is now correct.

About that bone you picked... Certainly you are correct that what you say counts, not what you intend to say, but it is equally true that it is what I say that counts, not what you think I say. In my previous post, I did not assert that the difference in definition was minor; instead, I attempted to explain why it SEEMED minor to me three years ago. I then provided an example of one particular way in which it caused a major change in the calculation. How is admitting my error, explaining how it arose, and providing an example in support of your criticism unsatisfactory?

I would also like to add that, even if the difference is of major importance, there are different expository styles. It is very commonplace in physics (which I write about more often than mathematics) to allow a change of context to imply the necessary change of definition, trusting the reader to note and make the change. You are correct that this is not the expository standard of mathematics, but after all, this is an online discussion of a puzzle. Given the opportunity for feedback and correction, the bar may be safely lowered a bit. In fact, the net outcome has been good (at least for me) because without the discussion which arose from the change of definition, the idea of extending the recursion to calculate the probabilities in the case where Alice does count would not have arisen.

But all defensive posturing aside, you are fundamentally correct: clearer is always better.

--Stuart Anderson

Just a short note to say that my previous post was written this morning but submitted after I got home from work today, so I didn't see your most recent post. Sorry if my response at the end of my post was a bit "peppery." And also, when I referred to "defensive posturing" in that post, I meant my own.

--Stuart Anderson

Sorry about the delayed response.

You are right, that there was a mistake in my previous recursion. The correct version of mine should read:

For ODD s, P(s, d) = P(s, d-1)·(1-1/n) P(s-1, d-1)·(1-(s 1)/(2n))
For EVEN s, P(s, d) = P(s, d-1)·(s/2 1)/n P(s-1, d-1)·(1/n)

where P(s,d) is defined to be the probability that at the end of day d after the visit of the prisoner of the day, the light has been switched s times.

I do not quite understand your definition of P(s,d). I also do not understand what you mean by "new" and "old". If I could venture a guess, by those do you mean to let P(s,d) be the probability the light having been switched s times at the beginning of day d before the visit of the prisoner of the day? Could you please define it exactly, lest we argue over the name of a rose.

Nightrider

Your recursion formulas now appear ALMOST correct to me (aside from the fact that none of your "plus" signs is visible for some reason). I think the final factor for the ODD s case should be (1 - 1/n - s/(2n)), which would be 1 - (s+2)/(2n) rather than 1 - (s+1)/(2n).

I also have to retract part of what I said in my post #16: I forgot to include Alice in the count of prisoners who will not turn the switch on, so (s/2 + 1)/n is the correct expression, where I had only (s/2)/n. It is also not true that P(1,1) = 1, because now we are counting the number of times the switch has been moved, rather than the actual number of prisoners who have entered.

This situation has become confusing, because there are now three distinct things we are determining: the probability of Alice counting to c, the probability of the number of distinct prisoner visits reaching a certain value (for which P(1,1) = 1 would be correct), and the number of times the switch has been moved, for which P(1,1) ought to be 1-1/n, since it is initially off, and Alice will never turn it on in case she visits on day 1. Let me suggest c for Alice's count, v for distinct visitor, and s for switch motions.

As for the definition of P(s,d) I am using, its interpretation is the one inherited from my original post. To clarify: P(s,d) is the probability that the light switch has been moved s times at the END of day d.

About the terminology "new" and "old," this is an artifact of how I phrased my statements about s. Specifically, I referred to "s changing from odd to even" or "s changing from even to odd," but when talking about a variable changing, there are two values associated with it, the old and the new. The way I phrased the statements did not make it clear precisely what the symbol s referred to, whether it was the value before the change took place ("old") or after the change ("new"). To clarify this, I added a statement that the symbol "s" stood for the "old" value, i.e. the value before the change occured.

A much better way to fix this up would have been to discuss the cases in which s does NOT change. Then there are not two different values under discussion, so the whole question of which one "s" is to stand for simply does not arise. Therefore, this would be a better way of setting up the recursion:

When s is even, it will not change as long as the prisoner who enters next is either Alice or one of the s/2 prisoners who has already turned the light on. This probability is 1/n + s/(2n), and its complementary probability is 1 - 1/n - s/(2n).

When s is odd, it will not change as long as Alice does not enter. This probability is 1 - 1/n, and its complementary probability is 1/n.

Therefore, for s to be odd at the end of day d, it was either odd on day d-1 and did not change, or was even on day d-1 and did change. This gives P(s, d) = P(s, d-1)·(1 - 1/n) + P(s-1, d-1)·(1 - 1/n - s/(2n).

For s to be even at the end of day d, it was either even on day d-1 and did not change, or was odd on day d-1 and did change. This gives P(s, d) = P(s, d-1)·(1/n + s/(2n)) + P(s-1, d-1)·(1/n).

If we are in agreement, I'll write up a revised version of my solution, including better variable names, clearer definitions, and the new recursion

Thanks for an interesting and productive discussion so far.

--Stuart Anderson

You're right of course. I forgot to evaluate my probability at s-1 rather than s, even though I explicitly wrote P(s-1, d-1), and even though I had done this very thing correctly in a previous post. It'seems I've made more errors in this discussion with you than in the entire body of my other posts to CTK. Sigh. I must be out of practice!

--Stuart Anderson

I am looking forward to your corrected solution post.

With regard to your previous comment concerning physicists' exposition style. I have to concede that I never like much of it. It makes a very inefficient or worse misleading read of a paper when many authors adopt the attitude that the readers already know what what they are thinking. But if that is the case, why do you bother frigging write the paper at all if there is nothing new? What is most disturbing is some of them even treat as theorem some folklore rumor which after many a exhausting and time-wasting reference checking turns out to be just that, some guess work or conjecture if it can be called that at all.