Author |
Topic: 5 Prisoners And A Light Bulb (Read 8729 times) |
|
meister
Newbie
Gender: 
Posts: 5
|
 |
Re: 5 Prisoners And A Light Bulb
« Reply #25 on: Nov 1st, 2010, 8:46pm » |
 Quote  Modify
|
I was introduced to this puzzle via
http://wordplay.blogs.nytimes.com/2010/08/23/numberplay-shackled-communi cation/
where we have been studying primarily the 10 prisoner case. Our best strategy so far has been a single dynamically-chosen leader strategy with a well-chosen initial snowballing phase. We have been unsuccessful in finding a multi-stage algorithm that can beat the single-leader strategy.
Applying some of the results I have learned, I believe I have found a initial snowballing strategy w/ dynamic leader that analytically yields an average of 22.81922667 days, for the 5 person case. This is better than anything mentioned so far.
I will use the following framework to describe the strategy.
There are two kinds of objects passed between prisoners: tokens, and leadership badges. Initially, everybody have one token. There will only be one badge, which will be dynamically assigned, and possibly passed between prisoners. The goal is to get the leader (the one with the badge) to amass all 5 tokens. The light bulb signal between days is predefined to represent a certain group of objects; conceptually, a prisoner entering on day X receives the light signal from day X-1, adding new objects to his collection. He then sets the lightbulb to the signal he wants to send, and removes objects from his collection corresponding to the signal sent.
Day 1: leave light off; an "off" light on day 1 represents 1 token
Day 2: outgoing light of "on" represents 2 tokens; "off" represents 1 token. Send 2 tokens if you have 2 (meaning you did not visit on day 1), otherwise send 1.
Day 3: outgoing light of "on" represents 2 tokens, "off" represents 1. Send 2 tokens if you have 2 or more, otherwise send 1.
Day 4: automatically pickup the leadership badge on this day. outgoing light of "on" represents badge and 3 tokens; "off" represents no objects. Send 3 tokens + badge if you have them, otherwise you keep the badge.
Day 5: "on" = badge + 3 tokens, "off" = nothing. Send badge + 3 tokens if you have a badge and exactly 3 tokens. Do not send the badge + 3 tokens if you already have 4 tokens and the badge.
Day 6 and onward: follow standard leader counting strategy, where the leader is the person with the badge.
--------
There is a fairly straightforward way to compute the probabilities in this strategy. It is
(5 = number of days to select final leader) +
sumi=14 [pr(leader starts at count i) * (ave. days for leader to finish counting when having starting count of i)] +
(pr(leadership badge passed from day 5 to 6) = penalty for not being able to start the normal counting process on day 6 when you attempt to change leadership)
Counting the number of days to finish counting to 5 simply means adding up the expected number of days for the series of people you need to show up. For example, if my count starts at 3, then the I need the following people to show up, in this order: one of the remaining 2 people with an uncounted token (takes 5/2 days), the leader (5 days), the remaining uncounted token holder (5 days), the leader (5 days), total 17.5 days.
The probability distribution I got after following the 5 days used to select the leader is:
Pr(start at 1) = 0.008
Pr(start at 2) = 0.416
Pr(start at 3) = 0.20736
Pr(start at 4) = 0.36864
So the average number of days is
5 + 0.008 * 30.41666667 + 0.416 * 24.16666667 + 0.20736 * 17.5 + 0.36864 * 10 + 0.20736 = 22.81922667
--------
Note 1 on previous comments:
I was having trouble repeating Hippo's calculation for average time for the single leader case without "observers". But then I figured out he must have been calculating for a slightly different algorithm. He reports "3 nights snowroll [with signaling] gives 24,2566667", and that "2nd night hook improves this by one day" (presumably to 23.2566667). I'm getting 23.25666667 for the following algorithm, which must be the same, but is described using my framework:
Day 1: leave off; "off" = one token
Day 2: "off" = 1 token, "on" = 2 tokens; send 2 tokens if you have 2
Day 3: Receive leadership badge. "off" = nothing; "on" = 3 tokens + badge. Send 3 tokens + badge if you can afford it.
Day 4: "off" = nothing, "on" = 1 token. Send 1 token if you do not have the badge and you have 1 token [early counter signaling].
---------
Note 2 on previous comments:
The "Watcher" strategy introduced by rmsgrey seems strictly worse than passing leadership onward to the potential "Watcher". Consider the case where on day 4 you "signal" to the watcher that you have a count of 4. On day 5, you will have a leader with count 4, and if the leader was not chosen on day 5, then you will have a watcher who knows the count is up to 4. In the alternative strategy, you could instead pass leadership and a count of 4 from day 4 to day 5. In this scenario, if the person on day 5 was previously uncounted, then you end up with a leader with count 5. If the person on day 5 was already counted, then you still have a leader with count 4, and you can designate the person on day 4 (former leader) to be the watcher, because he also knows the leader's count is at least 4. So the alternative is better in that you still have a potential watcher, and you also have the possibility of increasing the leader's count.
Also note that the calculations for my proposed fancy-snowballing algorithm do not consider "observers". With observers, my algorithm should be slightly better. I didn't calculate exact probabilities for this case with observers, but was interested enough to estimate them. I get a value of about 22.5 days with observers. Note that 65% of the time, at the beginning of day 6, we will have at least one observer (non-leader) who will have the correct count for the leader. In fact, for the case where the leader starts with count 3, 2/3 of the time there will be exactly one non-leader inferring a count of 3, and 2/9 of the time there will be two non-leaders inferring a count of 3.
Based on my work on 10 prisoner case, for small cases (n <=10), I doubt that there are any multistage strategies better than a properly designed algorithm that does dynamic leader selection + one stage counting.
|
|
 IP Logged |
|
|
|
meister
Newbie
Gender:
Posts: 5
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #26 on: Nov 5th, 2010, 7:31am » |
Quote Modify
|
Subject: fancier "observer" strategy.
In my previous post, I mentioned calculating 22.5 days for my strategy, with observers. This was using what I will call the "standard observer strategy":
All non-leaders (observers) keep track of what they think the leader must have (note that everyone knows the leader has count at least one, and depending on lights seen during the snowballing phase, some people could have the exact correct count for the leader). Observers can keep counting when they see others broadcast their single token to the leader successfully. If an observer infers the leader has a count of 4, and the observer sees a signal (from some other person) representing a count of 1 to the leader, then the observer can stop the game.
To calculate the benefit of the standard observer strategy, I looked at figuring out how many observers also had a count of 4 at the time the leader had a count of 4. Suppose there's just one other person. Then after the last person signals their count, the game could end when the leader sees the count, or when the observer sees the count. On average, this should yield a savings of 2.5 days. Instead of waiting 5 days for the leader to receive the signal, it only takes 2.5 days for either the leader or the observer to see the signal.
There is a fancier observer strategy possible, one that relies on people with their own unbroadcast token left that have been counting.
1) If I have just determined that the leader has count 4, and I still have a token, I can stop the game.
2) If I have an unbroadcast token, and I know the leader has count 3, and I see someone else's token of 1 being broadcast on the wire to the leader, then I can stop the game.
In the way I describe strategies, each prisoner that visits the room "receives" the signal, adding to their token total, before possibly "sending the signal" again on the same day, decreasing their token total.
The way a prisoner can decide to end early is to see if (my token total after receiving any incoming signal, but before sending one out) + inferred count of leader == 5.
Note that it is possible for an observer to temporarily have a count of 2; he just needs to have an unbroadcasted token, and he needs to see that someone else has broadcast a light representing a count of 1.
The fancier observer strategy should improve upon the average, I'm just not sure how much yet.
If we end in a scenario where the leader's count is still 3, we are saving at least 10 days on average.. Although I don't know if this happens often enough to make a significant difference.
|
|
IP Logged |
|
|
|
meister
Newbie
Gender:
Posts: 5
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #27 on: Nov 6th, 2010, 7:33pm » |
Quote Modify
|
After thinking about it some more, I think the "fancier observer" strategy from my previous post does not improve things, because the cases I mentioned never happen in my algorithm. This is because anyone who knows the leader has count 3 will never also have an untransmitted token.
However, I was able to come up with a different algorithm where we could use this sort of observer knowledge. It is sort of a combination between optimized snowballing, and the 2-stage binary token strategy. Here it is:
Following the binary token strategy, our goal this time is to infer a total token count of 4. Everyone starts with a token, but the first person who enters the room leaves the light off, and throws away their token, leaving only 4 to be counted.
On all days, a light of "off" means no information transmited, no tokens or badges transmitted.
On days 2&3: "on" means 1 token; pass 1 token if you have it.
On day 4: pick up leadership badge. "on" means 1 token + badge. Pass 1 token & badge if your count is exactly 1; otherwise keep the badge.
On day 5: "on" means 1 token + badge; pass "on" signal if you have one badge and exactly one token.
On days 6 and onward, we alternate between an "information passing" phase, and a "single token passing" stage. We will need to optimize the phase lengths to get a concrete strategy, right now, I'm guessing something like 3 days for information passing, and 16 days for single token passing.
For the information passing phase: If you know the leader (person with the badge) achieved count 2, then turn on the light. If you see the light on during this phase, you leave it on, and you have learned that the leader has count at least 2. (if the leader has count 2, and you do as well, and you are not the leader, then you stop the game-- this is important for the subsequent times this phase comes along).
For the single token passing phase: "on" represents a single token. After receiving any incoming signal from this phase, if you have count 2, and you are not the leader, and you know the leader has count 2, then stop the simulation. Obviously a leader with count 4 will also stop the game. Otherwise, if you have seen an "on" followed by "off" in this current stage, and you know the leader has count 2, then stop the game. Otherwise, if you have an odd number of tokens, then pass one token.
Note that in this algorithm, a leader with count 3 does not necessarily "keep" the count of 3, he can transmit it, going down to count 2. The idea is that we will pair the last two single tokens into a single count 2 token, and eventually an "observer" will realize that we have 2 people with 2 tokens, and stop the game. This is similar to the binary token strategy with observers.. the biggest difference is the optimized snowball at the beginning, and in the phase where knowledge of 2-tokens is being passed around. In our "information passing stage", the on signal can only represent the 2-tokens accumulated by the leader; in the binary-token strategy, the "on" signal can represent either one of the 2 2-tokens that were generated. Furthermore, in this information passing scheme, since no real tokens are being passed around, anyone, even an observer, can start the signal that "the leader has 2 tokens".
The initial snowballing phase was designed so that on the start of day 6, the leader has more than 90% chance of having a count ==2. It is possible that this is not the best initial snowballing probability distribution for this case, but it's my best guess as to what might work well.
Note that this was also designed so that many people know at the start that the leader has count 2. If the leader happens to achieve count 2 on day 4 and keep it, then the off signals from days 4 to 5 and 5 to 6 can inform 2 (possibly different) people that the leader has count 2; if the persons entering on day 5 and day 6 saw or transmitted an "on" light in days 2 and 3, then they will infer a leadership count of 2. So it is possible that day 6 will start with the lightbulb on, further propogating knowledge of leadership count to everyone else.
|
| « Last Edit: Nov 6th, 2010, 7:50pm by meister » |
IP Logged |
|
|
|
meister
Newbie
Gender:
Posts: 5
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #28 on: Nov 6th, 2010, 11:23pm » |
Quote Modify
|
Actually, it might be a reasonable algorithm to have the leader (badge-holder) chosen on day 3, and have the information signaling phase start on day 3. This way, we have a 48% that the leader starts at count 2 and immediately tries to propogate his count. Assuming an info-signalling phase length of 3, he will propogate knowledge of his count on average to 1.76 other non-leaders in this case.
Also, instead of repeating the info-signaling phase in the future, you could revert to the standard 2-token passing strategy of the binary token scheme, and see if that helps..
|
|
IP Logged |
|
|
|
meister
Newbie
Gender:
Posts: 5
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #29 on: Nov 7th, 2010, 10:27am » |
Quote Modify
|
I'm getting a simulated result of 21.7 days average for the following 2-stage binary-token algorithm, for the 5 person case:
On day 1: throw away your token, leave light off.
On day 2: Start the first stage of a binary-token algorithm, but have the stage last one day, light = single token
On days 3 & 4: This is a short 2nd stage of a binary-token algorithm, (length 2 stage), light = 2 tokens
On days 5 and onward, continue repeating the alternating stages of the binary token algorithm, using 16 days for each stage.
Be sure to use observers to exit early.
This is almost conceptually equivalent to my previously suggested strategy, where day 2 is a snowball with count 1 stage, and days 3&4 are an "info passing" stage. The "advantage" of having a short 2-day 2nd stage is that on day 3, you have a 48% chance of having 2 tokens, and can pas that along. You don't expect the 2nd stage to complete, but passing along the information makes it fairly probable that you will stop in the next phase.
My simulation results are over 100,000 runs.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #30 on: Nov 30th, 2010, 7:53am » |
Quote Modify
|
Wow, I was not here for a while and we can see new record ... good job.
So you have finally ended with throw away one token and binary observers as the top.
In both cases (single leader and this) you have improved snowballing ... good job.
Seems this short snowballing for binary/ternary scheme could be used generally.
So let me sumarize the signalling: (#tokens,#badges)
| night | on | off | prob-on | g4 pr | g3 pr | g2 pr | g1 pr | | 0 | (-5,1) | (-5,1) | * | | 1 | (-4,1) | (-4,1) | * | | 2 | (-3,1) | (-4,1) | 4/5 | | 3 | (-3,1) | (-4,1) | 24/25 | | 4 | (-2,1) | (0,0) | 72/125 | 1/125 | 52/125
| | 5 | (-2,1) | (0,0) | 72/125 | | \ge 6 | (1,0) | (0,0) | | | | 216/625 | 144/625
|
This gives 5+72/125+1/125*5(4+H4)+52/125*5(3+H3)+
216/625*5(2+H2)+144/625*5*(1+H1)\approx 24.22467, but removing 5th night gives 23.22467. I differ in goal 1,2 probabilities from your results. In all cases it is improvement.
Goal is to collect (0,1). Or know about the counter deficit and about the same number of tokens ...
Actually with the defficit notation there is no difference in collecting 5 and throwing one token out and collecting 4. So what can we achieve by 5th night? Just better knowledge ... noncounter observer of goal \le 2 with prob 144/55?
The 2nd night hook signalling with 4 nights snowball was:
| night | on | off | prob-on | g4 pr | g3 pr | g2 pr | g1 pr | g0 pr | | 0 | (-5,1) | (-5,1) | * | | 1 | (-4,1) | (-4,1) | * | | 2 | (-3,1) | (-4,1) | 4/5 | | 3 | (-2,1) | (0,0) | 12/25 | 1/25 | 12 /25 | | 4 | (-1,1) | (0,0) | 24/125 | | | 36/125
| | \ge 5 | (1,0) | (0,0) | | | | | 72/625 | 48/625 |
Giving 4+24/125+1/25*5(4+H4)+12/25*5(3+H3)+36/125*5(2+H2)+72/625*5*(1+H1 )\approx 23.456. (What differs from my previous calculations  )
and with 3 nights:
| night | on | off | prob-on | g4 pr | g3 pr | g2 pr
| g1 pr | | 0 | (-5,1) | (-5,1) | * | | 1 | (-4,1) | (-4,1) | * | | 2 | (-3,1) | (-4,1) | 4/5 | | 3 | (-2,1) | (0,0) | 12/25 | 1/25 | 12 /25 | | \ge 4 | (1,0) | (0,0) | | | | 36/125 | 24/125 |
Giving 3+12/25+1/25*5(4+H4)+12/25*5(3+H3)+36/125*5(2+H2)+24/125*5*(1+H1 )\approx 23.25667.
Now I got 24.17667 for 2 nights snowball ... what differs from my previous calculations as well  .
Originall signalling for 3 nights without the hook was:
| night | on | off | | 0 | (-5,1) | (-5,1) | * | | 1 | (-4,1) | (-4,1) | * | | 2 | (-3,1) | (0,0) | 4/5 | | 3 | (-2,1) | (0,0) | 12/25 | | \ge 5 | (1,0) | (0,0) |
For binary counting the throwing one token out is big improvement as it reduces the number of levels.
Hook/trick with high probability of having 2 tokens so you can send them. I must think about consequences of that ... sending 2 tokens does not help much as there is no matching double-token so it actually just informs others, but it creates binary counter with 3 tokens with high probability. ... Now I am not sure how much it will help with more binary counters.
Originally binary scheme:
| night | on | off | | 0 | (-1) | (-1) | | 1 | (0) | (0) | | 2-16 | (1) | (0) | | 17-32 | (2) | (0) | | 33-48 | (1) | (0) |
New binary scheme:
| night | on | off | | 0 | (-1) | (-1) | | 1 | (0) | (0) | | 2 | (1) | (0) | | 3-4 | (2) | (0) | | 5-20 | (1) | (0) | | 21-36 | (2) | (0) | | 37-52 | (1) | (0) |
I cannot see reasoning for the 4th night. Either the light was on or the prisoner could not have 2 tokens.
So I would reduce the double token phase to just one night.
It seems to me the third night signalling (1) (0) will improve thinngs (sending token if possible so not collecting double token) .. followed by 4,5 night (2) (0) signalling. The 5th night is there as the information spread phase ... actually never collecting tokens, but it creates with probability 4*72/625 an observer not holding double token knowing there exists one (it creates double token with probability 72/125, but with 72/625 only the double token holder knows it).
This will probably not help in higher level binary scheme, but in two levels it could be worth 3 days.
|
| « Last Edit: Dec 2nd, 2010, 3:12am by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #31 on: Dec 1st, 2010, 3:02am » |
Quote Modify
|
So generally you have introduced doubled snowball.
After first night next 2s2 nights the snowball signalling is increased each 2nd day, next s1 days the signalling is increased each day.
Oops no, that would not work. the hook is possible only for the first fail.
|
| « Last Edit: Dec 1st, 2010, 3:08am by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #32 on: Dec 2nd, 2010, 3:25am » |
Quote Modify
|
So as the first possible fail night hook is for free it can be used even for multiple counters.
This second possible fail night hook costs 1 day and roughly decreases the probability there would be at most 2 tokens counted by 1/n what improves the single counter as it shortens further phases by roughly n and the rounding favorizes us  .
For k counters it shortens further phases by roughly n/k and therefore it is too expensive.
So for single counter algorithm we have 2nd night hook (for free) and 3rd night hook with cost 1 both improving average number of visits.
P.S.: I still have to think about consequences for binary scheme. I suppose it could make small improvements for 5 and 7 prisoners, but I don't expect so for higher level counting schemas. ... I have to include it in gens of my genetic algorithms (to start on 2nd level for few \ge 0 days) and see what happens.
I have to look at the source codes ...
|
| « Last Edit: Dec 2nd, 2010, 3:27am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print