wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> 100 prisoners & a lightbulb: Technical
(Message started by: SMQ on Mar 10th, 2009, 6:56am)

Title: 100 prisoners & a lightbulb: Technical
Post by SMQ on Mar 10th, 2009, 6:56am
This thread is for technical discussion of the best known solutions to the "100 prisoners and a lightbulb" riddle. †For general discussion and an overview of what is known (with links to the solutions), see this thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1236693480) or, if you're very brave, the old thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805293) which is one of the most popular on the board, but has grown so large and so technical that it's probably scaring people off.

Hippo, you have the floor. ;)

--SMQ

Title: Re: 100 prisoners & a lightbulb: Technical
Post by Hippo on Mar 10th, 2009, 8:13am
:) Have I scared people?

I have instaled C# myself and I am planning to implement "more general" strategy in it. ... I will publish it either here or more probably on n prisoners and k state switch forum.

As I am new to C# it will take much more than one day it should take to one familiar with it.

I have stopped the genetic experiments running more than a month. The gaps in knowledge are even in smallest numbers of prisoners, where ignoring first and omiting snowballs is best for 4 prisoners (the ternary top), and it was not tested with double binary top for 5 prisoners ... I suppose experimets will continue on version in C#.

I have incredibly small amount of accademic publications so may be ...

Title: Re: 100 prisoners & a lightbulb: Technical
Post by River Phoenix on Mar 24th, 2009, 7:58pm
Can anybody supply a review of the known mathematical facts? E.g. probabilistic formulation, trivial lower bounds, information theoretic results, etc.

It would be highly significant, if possible, to make progress by diagonalization, counting arguments, or density/ramsey/ergodic theory.

Title: Re: 100 prisoners & a lightbulb: Technical
Post by Hippo on Mar 25th, 2009, 6:36am
For lower bound ... at least every prisoner must enter at least once.
For n prisoners where k not entered yet average time waiting for one of them is n/k.

This gives lower bound nHn.

Upper bounds whose can be easily calculated are for algorithms without phase switching.
... One counter with one snowball.
But they are beaten by so far known algorithms except for some small values of n.

Precise analysis of algorithms with phases requires space much bigger than the Universe.

BTW: I have not implemented gen parsing, mutations and snowballs yet, but it seems that binary scheme without snowballs, ignoring first beats one counter with snowball at least for n<=7.

In the following post brac37 incorporates to snowballs the idea the snowball fail the first possible fail night can be prevented by one intentional fail. I don't thing it will help, but I should think about it. Other proposals are special cases of general already discussed concepts (and there are nonoptimalities as badger selection is delayed what can result in doublebadge problem ...)

Title: Re: 100 prisoners & a lightbulb: Technical
Post by brac37 on Apr 1st, 2009, 2:36pm
Hello all,

In the second post of non-technical, one can read how I encountered the problem. Furthermore, you can read that I announced a message here. That will be this message. But what you read right now is only a beta version, since it will take more than a single moment to complete this message. You can start reading, but if you find something that is not clear/wrong or think that the presentation can be improved, you better send me a private message than posting here, for future consistency of this topic.

Before reading this message, read
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
unless you are convinced you know enough already.


A conceptual algorithm for dynamic counters

The purpose of this algorithm is to build concept. For that reason, it is a very dumb algorithm. The receipts of bulb messages in the algorithm will be formulated in the description of the sender. The reason of this will follow later.

The general idea is that in the first 47 days (47 is an arbitrary number for easy formulation), nine counters will be assigned and some counting will be done already. The problem of assigning a primary counter amongst the counters is ignored in this conceptual presentation. The counters gets different counting targets, but the formula presented here for these targets is a very stupid one (but easy for presentation). From day 48 and on, the algorithm continues as the multi-counter algorithm in the above link.

Here follows the description of the first 47 days. k is any nonnegative integer. In dark cyan, you can find remarks about tokens and badges. Ignore them if you do not know what they are (or just read them to understand what they are).

Day 1. The prisoner that is invited to the room does not need to be counted. So 99 prisoners must be counted. The bulb is set in an arbitrary position.
99 prisoners add one token each to their inventories.

Day 2+5k. The prisoner that is invited sends to his successor if he is invited the first time.
If the prisoner has a token, then he gives it to his successor.

Day 3+5k. The prisoner that is invited sends to his successor if at least one of the prisoners of the days 2+5k (predecessor) and 3+5k (himself) has been invited for the first time. His successor interprets a positive answer as exactly one instead of at least one. For that reason, the invited prisoner will forget that he has been invited to compensate, in case two prisoners of the days 2+5k and 3+5k has been invited for the first time.
If the prisoner has a token (one or two tokes), then he gives one token to his successor.

Day 4+5k. The prisoner that is invited sends to his successor if on both day 3+5k (predecessor) and day 4+5k (himself), a prisoner was invited for the first time. His successor interprets a negative answer as no one instead of at most one. For that reason, the invited prisoner will forget that he has been invited to compensate, in case exactly on one of the days 2+5k and 3+5k, a prisoner was invited for the first time.
If the prisoner has two tokens, then he gives both of them to his successor.

Day 5+5k. The prisoner of this day becomes a counter, except in case he was already a counter before he was invited. In that case, he orders his successor to become a counter by way of the bulb. If he becomes a counter, then his object will be to count 15-k of the 99 prisoners.
The prisoner adds one badge and k tokens to his inventory. If the prisoner had already a badge, then he passes the (just created) badge and k tokens to his successor.

Day 6+5k. The prisoner of this day becomes a counter if he has been ordered by his predecessor, except in case he was already a counter before he was ordered. In that case, he orders his successor to become a counter by way of the bulb. †If he becomes a counter, then his object will be to count 15-k of the 99 prisoners.
If the prisoner received an order to become counter, but had already a badge, then he passes the (just received) badge and k tokens to his successor.

Day 7+5k. The prisoner of this day becomes a secondary counter if he has been ordered by his predecessor. If he becomes a counter, then his object will be to count 15-k of the 99 prisoners. Since 7+5k = 2+5(k+1), we are round now.


Improvements of the conceptual algorithm

God did not create the universe in six days. No, I am told that that is another translation error in the bible. God created the universe in six periods instead. This is also more in accordance with scientific research, but that is another discussion.

Here, we have a week of 5 days without a Sunday. But some days may be removed, merged, or blown up to a sequence of several days. From now on, we call the days of the above algorithm periods.

For instance, period 5, 6 and 7 will be one and the same day, because the period 5 prisoner will always become a new counter. If periods 5+5k, 6+5k and 7+5k are not merged to one day, then periods 5+5k and 7+5k remain one day, but period 6+5k becomes a sequence of zero or more days.

If period 9+5k in the concept becomes more than one day, then there will be a transfer of either zero or d+1 tokens to the successor on day d of this period. If the prisoner of day d has at least d+1 tokens after receiving the tokens of his predecessor, then he can get rid of d+1 tokens.

Day 8+5k and day 9+5k in the concept will become sequences of zero or more days, but it seems wise if at most one of both days will become a sequence of positive length.

I take a break now.

Passing additional tokes or anti-tokens along with badges.

Cheating by prisoners with badges.

Title: Re: 100 prisoners & a lightbulb: Technical
Post by Hippo on Apr 24th, 2009, 1:05am
The C# implementation is not finished yet :(, but the long simulation of genetic algorithm for 12 counters (with snowballs with first fail hooks and careful restarting, /\/// ordering of binary phases and observers stop) and I get average 3369.69 of all 7810569 simulations. The most spread gen had average under 3347.

Title: Re: 100 prisoners & a lightbulb: Technical
Post by william wu on Apr 30th, 2009, 2:28pm

on 04/01/09 at 14:36:36, brac37 wrote:
Hello all,

Before reading this message, read
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
unless you are convinced you know enough already.


Hi,

You may be interested in an updated version of my small writeup that has been hiding at the following URL:

 http://www.ocf.berkeley.edu/~wwu/articles/100prisonersLightBulb.pdf

This version has corrected typos, describes the binary tokens scheme more clearly, and includes technical content such as a proof that the binary tokens scheme has O(n (ln n)^2) runtime.

(Normally I would update the old URL, but apparently I cannot update the old URL at the moment because all SSH services are down at OCF, and it is unknown when they will be restored.)

Will

Title: Re: 100 prisoners & a lightbulb: Technical
Post by Hippo on May 2nd, 2009, 9:13am

on 04/30/09 at 14:28:17, william wu wrote:
Hi,

You may be interested in an updated version of my small writeup that has been hiding at the following URL:

†http://www.ocf.berkeley.edu/~wwu/articles/100prisonersLightBulb.pdf

This version has corrected typos, describes the binary tokens scheme more clearly, and includes technical content such as a proof that the binary tokens scheme has O(n (ln n)^2) runtime.

(Normally I would update the old URL, but apparently I cannot update the old URL at the moment because all SSH services are down at OCF, and it is unknown when they will be restored.)

Will


Hi,
I have not read the updated version thoroughly yet.
It does not seem to be difficult to bound binary phases not using observers stop.
But when the observers stop is taken into account the things became very very difficult to analyze.
This is why I have switched to simulations instead.
Behaviour for optimal so far found parameters of best so far described algorithms gives nearly http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/2 n ln2 n so it seems the complexity of the problem would be http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/theta.gif(n ln2 n) (with the multiplicative constant near http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif/2).

Typo found:
Page 4: Stage II - Prisoners who did not see an ON bulb in stage I do nothing
There is problem with binary counting when n is not power of 2, I didn't see the required modification is in the article (I would mention two level scheme with non equal badges as well).

Title: Re: 100 prisoners & a lightbulb: Technical
Post by william wu on May 28th, 2009, 3:29pm
Hippo,

Thanks for the correction; I have updated the PDF with the fix.

I haven't had time to revisit the document lately. You are more than welcome to co-write something though if you like; if you want to use the same .tex file, send me an e-mail.

Title: Re: 100 prisoners & a lightbulb: Technical
Post by Mike_V on Mar 2nd, 2010, 8:55am

on 04/30/09 at 14:28:17, william wu wrote:
Hi,

You may be interested in an updated version of my small writeup that has been hiding at the following URL:

†http://www.ocf.berkeley.edu/~wwu/articles/100prisonersLightBulb.pdf

Will


Nice paper! Just thought I'd mention some potential problems I saw, in case you wanted to fix them.

On page 6:
- Prisoners who saw an ON bulb in Stage I do nothing.

I think you mean "who saw an OFF bulb". Since those are the ones prior to the counter being chosen. The ones who saw an ON bulb (afterward) were not counted.

On page 11:
On the last day of Stage II:
- If you are a drone:
* If light is ON, turn it OFF. Then in future invocations of Stage I, turn the
light ON q times.


I don't think this works. Since you won't have enough assistant counters to accumulate the extra q switches. Instead, you should have this drone turn the light ON 1 time in Stage II (also far faster).

Page 12:
* If the light is ON, add q to count. If the count equals n, declare victory.
Forgot to mention that he needs to turn it off if the count doesn't equal n.

Also, it'd be nice to have average run times for n=100 for each of these protocols.

- Mike

Title: Re: 100 prisoners & a lightbulb: Technical
Post by Hippo on Mar 17th, 2010, 8:26am
Oh yes, I don't remember the previous version exactly, but seems you negate the meaning of the ON/OFF during snowball (in 7th protocol). Which is incompatible with the 2nd phase according to standard protocol when counter turns OFF.

Starting snowball with ON and switching to OFF by selected counter is compatible with the "who saw ON in first phase does nothing" and with the classical counting in 2nd phase as well.

----------

To the protocol 8 ... the static assignment of assistant counters and the head counter are ineffective. Morever stage switching is much easier with dynamic counters. At the end of stage in the ON state prisoner "increments" the number of tokens in ending phase to be sent.
It's complicate to describe it as he is double drone (the and of first phase with active drone in it) and drone assistant when it have to sent one token in odd phase and one in even etc.
I would definitly not divide assistant token into q drone tokens.

More natural ... may be just for me ... describtion of the 8th protocol is following:
Each prisoner stars with (virtual) token, and goal.
Most of prisoner's goal is zero, but a "assistant counters" obtain nonzero goal and assistant token.
There is head counter (the only prisoner with nonzero assistant token goal (equal a)).

On odd phases:
in OFF state each prisoner having more tokens than goal states decrements his token count and switches light ON. Otherwise there is no change.

in ON state each prisoner having bigger goal than tokens increments his token count and switches light OFF. Otherwise there is no change.

On even phases: (similarly but with assistant tokens)
in OFF state
... having at least 2 more assistant tokens than is assistant goal decrements the number of assistant tokens and swithces light ON.
... having 1 more assistant token than assistant goal and goal equal to number of tokens ... decrements the number of assistant tokens and swithces light ON.
otherwise no change
in ON state
... having less assistant tokens than assistnt goal increments number of assistant tokens and switches state OFF
otherwise no change

Victory is declared by head counter when both his goal and assistant goal are equal to number of collected tokens and assistant tokens.

The scheme could work in case sum of goals is equal to number of tokens and the head counter assistant token goal is equal to number of assistant tokens.

There is no need to make all goals of equal size in this scheme. And actually only the differences tokens-goal, assistant tokens - assistant goal are important. I would rather use level 1, level 2 tokens in the describtion ... what could be easily generalised to more than 2 level scheme.

Title: Re: 100 prisoners & a lightbulb: Technical
Post by rsreinhart on Jan 4th, 2012, 4:55am
I have a solution that I don't believe has been put forth yet. I read through many pages from various threads and didn't see what I think could be a more optimal solution. It is a modification of the binary and several other ideas already out there. I believe it could be a significant improvement in expected # of days until freedom.

I. Day 1-120
Assume light starts off.
All Prisoners start with a value of 1.
All prisoners that have never been in room before turn light on when finding it off and reduce their value by 1 to 0.
Any prisoner finding light on, turns it off and adds a value of 1 to his value. (Exception: on Day 2, prisoner will always add an extra 28 to his count (e.g. if he enters with light on, would have a count of 30. In the event he enters on both day 1 and 2, it would be 29).

At the end of 120 days, there will be a value distribution such as: 1 x 31, 14 x 3, 22 x 2, 3 x 1.

The light on can/should be carried over from Day 120 to Day 121 to start the next cycle. E.g. If the Day 120 person has a Value of 1 and enters with light off should turn light on and leave with Value 0, or if he enters with Value 0 and light on should leave light on and leave with Value 0.

II. Days 121+
There will be a 70 day cycle allowing the counts to be accumulated.
Days 1-10 = Value 1
Days 11-20 = Value 2
Days 21-30 = Value 4
Days 31-40 = Value 8
Days 41-50 = Value 16
Days 51-60 = Value 32
Days 61-70 = Value 64

Whenever someone enters a room, he can either pass along his count or accumulate the count already in the room.

Counts are signaled by the light being on during the respective period. If someone enters on day 37 with the light on then the room has a value of 8.

Counters will always try to put up or take loose counts that give them fewer pieces of binary number. E.g. a 9 will leave a 1 but not a 2. A 7 will accumulate a 1 or 2. (Going from 7 to 9 goes from 3 binary pieces to 2 (4+2+1 --> 8+1)

{e.g. On Day 2 of the 70-cycle, someone who has not previously entered the room (has a 1 value), turns light on. Day 3-5, 3 people with value 0 enter room, they ignore the light and leave remaining at Value 0. On Day 6 someone with a 1 count enters, he takes the 1 count in the room by turning off the light and he is now a 2 count. Day 6, someone with value 1 enters and turns light back on, and leaves as a value 0. Now on Day 10 (the last day of the 1ís value), if the light remains on, whoever enters the room adds a value 1 (even if heís at 0) and turns light off to reset for the Day 11-20. However, if he would be leaving as a 2, instead he would leave light on and leave as a Value 0.}

{Day 11, someone with Value 1 enters, leaves light off and leaves as Value 1 still. Day 12, someone with Value 3 enters, turns light on and leaves as Value 1. Day 14 someone with value 1 enters, leaves without touching light or changing his value. Day 15, someone with Value 2 enters, turns light off and leaves as Value 4. On last day of the 2 values, Day 20, someone with Value 1 enters, turns light off and leaves as value 3, in order to prepare for Value 4 days.}

After Day 70, the 70 day cycle starts over again with 10 days at each binary value.

Once a prisoner has accumulated 128 Value, freedom is declared.

In this way, unlike other binary methods, there is no need to ever restart from the beginning, because each 70 day-round allows all binary values to be passed. And the person that started as a counter can pass his whole or partial count to someone who was a non-counter that enters the room 5 days later; there is no need for someone to be the next person in the room to transfer count.

The 100 prisoners as well as the light bulb all can store values where the bulbís value is based on the day of the cycle it is lit.

The 70 day period is not-optimal, just seemed like a good starting point for analysis.

My guess is this could be significantly less than the current 3500 day models although I donít know how to model this method.

I'm thinking 20-30 times through the 70 day cycle + the initial 120 days would be 1500-2100 day range.

Also as I stated before the 70 day period could be optimized with fewer days for some values and more for others or could change each time through weighing more heavily toward the higher binaries each time through.

Comments and analysis welcome.

Title: Re: 100 prisoners & a lightbulb: Technical
Post by SMQ on Jan 4th, 2012, 5:27am
Now that's how you do a first post -- welcome to the forum! :D

On the surface it's certainly an intriguing variation; let me break out my simulator and get back to you. ;)

--SMQ

Title: Re: 100 prisoners & a lightbulb: Technical
Post by rmsgrey on Jan 4th, 2012, 8:23am
My immediate, intuitive (ie probably wrong) reaction is that you'll lose a lot in the phase changes - time to victory can be counted in number of tokens merged - that is, sent and collected by someone with a matching bit. Every time someone intercepts a token because a phase ends rather than because they want it, you waste the initial transmission of that token.

A little more thought says that making the final count requires the last two prisoners with any values to both enter the room during the same 10 day period (in the right order unless they both have 64).

There's a 1/50 chance of either of them entering on any given day, and a 1/100 chance of the other entering on any other given day, with 45 possible choices of pairs of days, that's a 9/1000 chance of success in any given cycle once two prisoners each have a count of 64. If the final token is smaller, then it's a 9/2000 chance in cycles where one prisoner is only missing one binary token (actually, the chances are a little worse than that since you're over-counting those times when at least one of the two "live" prisoners visits more than once in the ten days, but the error is not large)

If you take the 9/1000 figure, that's roughly 111 cycles - 7770 days - just for the final transaction.

Title: Re: 100 prisoners & a lightbulb: Technical
Post by rsreinhart on Jan 5th, 2012, 4:47pm
rmsgrey, I don't think that calculation is correct. If each day each prisoner has a 1/100 chance and there's 10 days per cycle, it would be a 1/10 chance for each of the two or 20% chance that one of the 2 'value=64' would be chosen during the 10 day period. The chance of the second one being chosen would be 1/99 x (depending on day of the first being chosen but assume 5 is the average day leaving 5 days for the second to be chosen) 5. Thus in any 70 day cycle it would be .20 x 5 / 99 or 1% chance. Avg would then be 3500 days for >50%.

This appears pretty high so it's nearly 10 years for the final phase. I do believe the initial accruing of binary blocks would be rather quick using this method. Assuming my calculations are correct, the last phase would take too long...obviously the 70 day cycle times can be adjusted.

I could easily eliminate this problem by removing the 64 bit days from the 70 day cycle and making them 60 day cycles. Then I can set every 20th cycle would only be 64 bit days for 120 days in a row. There's an extremely high chance that the two Value 64 bits would combine during those 120 days.

One time through the cycles would then be 120+60x19+120 =1380 days.

My initial idea included the idea that the cycle composition could change over time.

Suppose we did the following:

Cycle 1:
15 days for Value 1
14 days for Value 2
13 days for Value 4
12 days for Value 8

The cycles would adjust each time finally reaching the final distribution of days skewed toward high value blocks:

Cycle 20:
5 days for Value 1
6 days for Value 2
8 days for Value 4
10 days for Value 8
15 days for Value 16
15 days for Value 32
20 days for Value 64

You may be able to eliminate the lower value days and just repeat the entire cycle in case of failure.

What program are you guys using to model these type of problems? I would love to be able to tweak the assumptions myself.

Title: Re: 100 prisoners & a lightbulb: Technical
Post by towr on Jan 5th, 2012, 11:04pm

on 01/05/12 at 16:47:17, rsreinhart wrote:
What program are you guys using to model these type of problems? I would love to be able to tweak the assumptions myself.
Different programs we wrote ourselves. e.g. You could use monte carlo simulation, or what I like to do is keep track of all possible states and their probabilities (but that's only doable if the number of states is sufficiently limited).

Title: Re: 100 prisoners & a lightbulb: Technical
Post by rmsgrey on Jan 6th, 2012, 8:58am

on 01/05/12 at 16:47:17, rsreinhart wrote:
rmsgrey, I don't think that calculation is correct. If each day each prisoner has a 1/100 chance and there's 10 days per cycle, it would be a 1/10 chance for each of the two or 20% chance that one of the 2 'value=64' would be chosen during the 10 day period. The chance of the second one being chosen would be 1/99 x (depending on day of the first being chosen but assume 5 is the average day leaving 5 days for the second to be chosen) 5. Thus in any 70 day cycle it would be .20 x 5 / 99 or 1% chance. Avg would then be 3500 days for >50%.


Your 1% approximate value is very close to my 9/1000 value - where we differ significantly is in how to convert the probability per iteration into an expected number of iterations for first success.

If you let the expected number of iterations for first success be E, and the probability of success in each iteration be 1/100 (independently), then the expected number of further iterations required after the first one fails is again E, making the total expected number of iterations if the first fails 1+E, while the expected number required if the first iteration succeeds is 1. Substituting into:

E = P(success) * E(success) + P(fail) * E(fail)

gives:

E= 1/100 * 1 + 99/100 * (1+E)
 = 1 + 99E/100
100E = 100 + 99E
100E - 99E = 100

E = 100

not E=50 as you approximated...

Title: Re: 100 prisoners & a lightbulb: Technical
Post by Hippo on Feb 29th, 2012, 7:52am

on 01/04/12 at 04:55:26, rsreinhart wrote:
I have a solution that I don't believe has been put forth yet. I read through many pages from various threads and didn't see what I think could be a more optimal solution. It is a modification of the binary and several other ideas already out there. I believe it could be a significant improvement in expected # of days until freedom.


Sorry, I don't think there is a bright new idea. You have applied binary counting scheme.
Unfortunately your "guessed" parameters are far from optimal ones. ... Your "snowball" phase is normal binary counting. The phase lengths are too short.
These 28 tokens given at 2nd day are not optimal. Better solution is giving the extra bits in first phase switching to given binary level (to 4, to 8 and to 16) ... this saves one visit of counter on given level. My guess is around 4000-4200 days for average release time. [edit] ... this was too optimistic with phases of length 10 (Last phase requires 150 days in average)
[/edit]

I am sure the snowball prephases speeded the binary counting a lot and the observers stop method was crucial for making binary counting better than two level counting schemas.

What was surprising that binary counting with 3 counters in the top level were better than 2 binary counters on top (observers stop).

Nonetheles you made a huge step to understanding the problem ... Try to run simulation yourself (several tousand times) to gain better understanding of required phase lengths.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board