wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> 5 Prisoners And A Light Bulb
        
(Message started by: Padfoot on Jan 29^th, 2007, 5:34pm)

Title: 5 Prisoners And A Light Bulb
Post by Padfoot on Jan 29^th, 2007, 5:34pm

See 100 Prisoners and a Light Bulb

What would be the optimal plan for if there were just 5 prisoners?

Is there more than one optimal solution?

:-/ :) ??? :-/ :)

(They need your help)

Title: Re: 5 Prisoners And A Light Bulb
Post by towr on Jan 30^th, 2007, 12:50am

I would guess the simple leader solution would be the best bet. More advances strategies probably need more time to pay off.

Title: Re: 5 Prisoners And A Light Bulb
Post by Grimbal on Jan 30^th, 2007, 3:02am

But the details of how you choose the leader becomes very important.
If for instance the leader is whoever is picked on day 2, he can start with a count of 2 (himself and the first prisoner) with 80% probability or 1 with 20% probability.
If we choose the leader as prisoner of day 3, with a small snowball round, he starts with a count of 3 with 48%, 2 with 32% and 1 with 20%. This is good considering that he otherwise gets an average of less than 1 count in 5 days.

Title: Re: 5 Prisoners And A Light Bulb
Post by towr on Jan 30^th, 2007, 3:47am

I don't think those percentages are all quite correct (I get 48,48,4), but I get the idea.

Title: Re: 5 Prisoners And A Light Bulb
Post by Grimbal on Jan 30^th, 2007, 4:22am

Right. The way I thought of a snowball, a prisoner on day N can pass only 0 or N token by leaving the light off or on. In that case, if the same prisoner is picked on day 1 and 2 he could not pass 2 tokens. He would pass zero. But since the prisoner on day 2 is guaranteed to have at least one token, the meaning of the light off resp. on after day 2 can mean 1 resp. 2 token, instead of 0 and 2. I think on day 3 the same applies.

Title: Re: 5 Prisoners And A Light Bulb
Post by SMQ on Jan 30^th, 2007, 8:52am

Along another line, here are what I believe to be optimal strategies for 1 through 4 prisoners (I assign letters to the prisoners based on the order in which they first enter the common room):

1 prisoner and no lightbulb: (optimal)
- Prisoner A enters on day 1, declares success

2 prisoners and no lightbulb: (optimal)
- Prisoner A enters, knows he is A b/c it is day 1, does nothing
- Prisoner B enters, knows he is B b/c it is day >1, declares success

3 prisoners and a lightbulb: (optimal)
- Prisoner A enters, knows he is A b/c it is day 1, turns off the light
- Prisoner B enters, knows he is B b/c it is day >1 and the light is off, turns on the light
- Prisoner C enters, knows he is C b/c it is day >1 and the light is on, declares success

4 prisoners and a lightbulb: (probably optimal)
- Prisoner A enters, knows he is A b/c it is day 1, turns off the light
- Prisoner B enters, knows he is B or D b/c it is day >1 and the light is off, turns on the light
- If prisoner A enters between B and C, he knows either B or D has visited b/c he sees the light on.
- Prisoner C enters, knows he is C b/c it is day >1 and the light is on, turns off the light
- If prisoner A enters between C and D, and he has previously seen the light on, he now knows B and C have visited b/c he sees the light off.
- If prisoner B enters between C and D, he now knows C has visited b/c he sees the light off.
- Prisoner D enters, knows he is B or D b/c it is day >1 and the light is off, turns on the light
- Prisoner A, B or C enters, declares success iff he knows prisoner C has entered.

This gives an average runtime of about three days past when all four prisoners have entered. (C can always declare success on his first visit after D; B has a 50% chance of having entered between C and D and so being able to declare success; A has a 1 in 6 chance.)

I don't see an obvious way to extend this strategy to 5 prisoners, however, as no one but A will know his order for sure.

--SMQ

Title: Re: 5 Prisoners And A Light Bulb
Post by UNKNOWN on Feb 7^th, 2007, 5:17pm

That's weird... i cant seem to find 100 prisoners and a light bulb at all...
can sum1 post it up here plz?

Title: Re: 5 Prisoners And A Light Bulb
Post by Padfoot on Feb 7^th, 2007, 5:29pm

Did you look under the "hard" section?

Title: Re: 5 Prisoners And A Light Bulb
Post by JiNbOtAk on Feb 7^th, 2007, 5:30pm

It's in the riddle's main page, under the hard section.

http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisonersLightBulb

Title: Re: 5 Prisoners And A Light Bulb
Post by UNKNOWN on Feb 7^th, 2007, 5:44pm

ok, i thought it was a forum question. thanks :)

Title: Re: 5 Prisoners And A Light Bulb
Post by UNKNOWN on Feb 7^th, 2007, 5:51pm

i forgot, what is the "leader solution"? I'm guessing is that one person is the "leader" and whenever he goes into the room he turns on a light bulb???

Title: Re: 5 Prisoners And A Light Bulb
Post by Icarus on Feb 7^th, 2007, 6:36pm

You can find a thread for the 100 prisoners and a light bulb in the Hard forum.

The leader solution has one prisoner elected as leader. He is the only one who can turn the light off. Everyone else turns on the light exactly once: the first time they enter the room and find the light off. When the leader has turned off the light 99 times (or 4 times or however-many-prisoners-there-are-other-than-him times), he knows that everyone else has entered the room, and he obviously has (at least 99 times), so he declares at this point.

A nice solution, but it can be beat by a factor of 3.

Title: Re: 5 Prisoners And A Light Bulb
Post by UNKNOWN on Feb 7^th, 2007, 7:29pm

oh nice...

Title: Re: 5 Prisoners And A Light Bulb
Post by UNKNOWN on Feb 7^th, 2007, 7:29pm

If it was up to me, I'd be shot... or so my brother says... 8)

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Feb 9^th, 2007, 5:47am

It seems to me that one counter with snowroll prephase should be optimal for this case. One should just check whether the 4 days prephase is optimal or 3 days is better.

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Feb 10^th, 2007, 6:56am

OK, 3 days snowroll gives 24,776666666... average.
(whoever turns light off becomes counter ...
first day do nothing, second day turn light off if you were here first day, otherwise turn it on, third day if the light is off do nothing, otherwise if you were here already turn it off, fourth day if the light is on, turn it off and do nothing, otherwise if you were not here with light on during first three days and didn't turn light on yet, turn light on. If you became counter, turn light off whenever is on.
If you became counter on day d<=4 when you were 2nd times near the bulb, declare success with the (5-d+2)-th switch off. If you became counter on day 4 during your first visit, declare success with the 2nd =(5-4+1) swith off (including the declaration swith off).)

2 days snowroll gives 25,2166666
4 days snowroll gives 25,3926666
So the 3 days is optimal choice.

Title: Re: 5 Prisoners And A Light Bulb
Post by rmsgrey on Feb 10^th, 2007, 11:05am

It's always possible to guarantee that the person entering on day 3 has complete information, so given that a 3-day snowball is the optimum length snowball for the 5 prisoner game, doing a special 3-day leader picking must be better than any snowball.

I'm not about to produce a simulation to get numbers, but the following should perform better:

Day 1: do nothing
Day 2, repeat visit: turn light off
Day 2, new prisoner: turn light on
Day 3, repeat visit: turn light off and start with count of 1 or 2 depending on whether someone else has been in
Day 3, new prisoner: turn light off and start with count of 2 or 3 depending on whether the light was off or on.

Anyone who didn't visit during the first 3 days turns the light on at the next opportunity; the prisoner who visited on day 3 turns it off at every opportunity and keeps count.

As a further improvement, on day 3, the light can be left on ~~either to signal a count of 2, or~~ ((see below)) to signal a count of 3 (I'm not sure which would work better) and the prisoner entering on day 4 then becomes a "watcher" - after leaving the light off on day 4 if they had been in before, or on if they hadn't, they then don't touch the switch, but keep track of observed changes in the bulb state between visits - so if the signalled count were 3, and the watcher were the fourth prisoner, then if he saw the light off on a subsequent visit, he'd know he'd been counted, and there was one prisoner left to turn the light on - so seeing the light on again would let him claim victory.

It's possible for the watcher to miss a count entirely (if the light is switched twice or more between consecutive visits) so there's no guarantees he'd be helpful, but it costs nothing to use the light on the third day to create one since it's otherwise unused...

Some quick calculations suggest that it's best to use the bulb to signal a count of 3 on day 3 - if the prisoner on day 4 is a repeat entry, they'll get complete information from a signal of 2 or 3. A new prisoner would get a signal of 2 in 36/125 trials and a signal of 3 in 24/125 trials, but the new prisoner starting from a count of 3 (including themself) would only have a 1/12 chance of not missing a count (or a 1/24 chance of getting to claim freedom) while a new prisoner starting with a count of 4 has a 1/4 chance of not missing a count (or a 1/8 chance of being the one to claim freedom)

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Feb 12^th, 2007, 2:40pm

rmsgrey: very nice trick, reducing probability of snowroll initialisation to 1 from 1/n to 1/n^2 for n prisoners. ... such 2 day snowroll without watcher gives 24.21666 average, and 3 day snowroll with 2nd day exception gives 23,776666 average.

I should correct your calculations ... with 1/25 probability counter is initialised to 1, with 12/25 is initialised to 2, with 12/25 the snowroll is not finished yet. ... it seems to be better to propagate the latter info and no watcher is needed.

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Feb 12^th, 2007, 2:56pm

Probably my notation of snowroll length is a bit confusing ... k-day snowroll in my notation means k-th night is the last night with snowroll signalling.

The exception of course is in 3rd day. And can be applied on snowrolling in general for n-prisoners.

Title: Re: 5 Prisoners And A Light Bulb
Post by rmsgrey on Feb 13^th, 2007, 10:21am

So your earlier figures for 2, 3 and 4 day snowballs apply to the prisoner entering on the 3rd, 4th and 5th day respectively becoming counter when a different prisoner enters each day?

In that case, with the prisoner entering on the fourth day becoming the counter in 12/25 cases, (24/125 with a count of 4; 36/125 with a count of 3), and the prisoner entering on the third day becoming counter in the remaining cases (1/25 count of 1; 12/25 count of 2), there are two choices for what to do with the bulb on day 4 - either use it to signal a potential watcher (which is useful when the counter is chosen on day 4) or use it as the first signal of the ongoing counting process (which is useful when the counter is chosen on day 3)

There's still scope for watchers to save time in bad cases - non counters become watchers with a worst-case count and occasionally have the right count and manage not to miss any signals (a 9/250 (36/125 of the right count, 1/4 of not missing intervening signals and 1/2 of intercepting the final signal) chance of the prisoner who entered on the third day successfully claiming release as a watcher - other prisoners have worse odds)

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Feb 14^th, 2007, 7:36am

Yes; with 3 day snowroll in my terminology, 4th night uses "token" signaling (if the counter was choosen on 4th day, it is off, otherwise it can signal new prisoner entered).

I didn't calculate average 'time' for watcher method yet ... I am planning to calculate it, but it is harder case ;( ... I am not sure I can do it analytically. At least it can be aproximated by some kind of dynamic programming. ... I need to improve the method required for more general case ... observers method called in my terminology.

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Feb 14^th, 2007, 2:40pm

My doubts were not confirmed. For one phase algorithms we don't need to know probabilistic distribution and computing average 'time' is easy by following recurent formulas:

T⁺_g,n,p = 5/(n+1)+n/(n+1)T⁺_g,n-1,p+1 + 1/(n+1)T^-_g-1,0,p,
T^-_g,n,p = 5/(p+g)+p/(p+g)T^-_g,n+1,p-1 + g/(p+g)T⁺_g,n,0, T^-_0,n,p = 0, T⁺_1,n,1 = 0.
where superscript denotes light on/off, g is the counter goal, n+p is the number of observers able to finish the process, p are those of them who have seen light on during the last visit. For our case p+n<=1 so it is much easier.

... results will be soon ;) ... the improvement in 3 days snowroll by observers is 0.12 when counter starts with goal of 2. Some smaller improvement is also when he starts with higher goal.

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Mar 7^th, 2007, 7:19am

Finaly the computation is finished ... it takes 3 pages after shortening ... improvement of observers in single counter method with n prisoners, snowroll of length s with 2/3 day hook is:
(12n²-20n+10)/(2ⁿn!)-(63 2^n-5)/(3ⁿn!(n-1)!)+
18/(6ⁿn!(n-1)!)+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif^s_k=3 n!(k-1)/(2^n-kn^k+1(n-k)!(n-k)!).

This is of order 10^-128 for n=100,s=28 and 0.07859828 for n=5, s=3.
I hope there is no bug in computation, the most challenging part was not yet counted observers with full info (first three days the same prisoner choosen).
In my previous post the result should be 0.024 ... I missed one division by 5 somehow. :(

So the resulting best (at least so far) algorithm for 5 prisoners gives average approx 23,69806838.

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Nov 13^th, 2008, 1:54pm

on 02/10/07 at 06:56:04, Hippo wrote:

Actually I were pesimistic here ... if the counter was choosen before the last snowroll night, the following night may be used for counter signalling. This reduces the probabilities following way:
2 nights snowroll gives 25,0166667
3 nights snowroll gives 24,2566667
4 nights snowroll gives 24,5846667
2nd night hook improves it by one day.
Observer(s) improve it by a very small amount.

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Apr 14^th, 2009, 1:04pm

So one leader with snowball is not optimal for 5 prisoners.
Ignoring first and binary scheme (with observers) with all phase lengths 16 has average around 22,9 days.

Title: Re: 5 Prisoners And A Light Bulb
Post by meister on Nov 1^st, 2010, 8:46pm

I was introduced to this puzzle via
http://wordplay.blogs.nytimes.com/2010/08/23/numberplay-shackled-communication/

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) +
sum_i=1⁴ [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.

Title: Re: 5 Prisoners And A Light Bulb
Post by meister on Nov 5^th, 2010, 7:31am

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.

Title: Re: 5 Prisoners And A Light Bulb
Post by meister on Nov 6^th, 2010, 7:33pm

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.

Title: Re: 5 Prisoners And A Light Bulb
Post by meister on Nov 6^th, 2010, 11:23pm

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..

Title: Re: 5 Prisoners And A Light Bulb
Post by meister on Nov 7^th, 2010, 10:27am

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.

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Nov 30^th, 2010, 7:53am

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+H₄)+52/125*5(3+H₃)+
216/625*5(2+H₂)+144/625*5*(1+H₁)\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/5⁵?

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+H₄)+12/25*5(3+H₃)+36/125*5(2+H₂)+72/625*5*(1+H₁)\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+H₄)+12/25*5(3+H₃)+36/125*5(2+H₂)+24/125*5*(1+H₁)\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.

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Dec 1^st, 2010, 3:02am

So generally you have introduced doubled snowball.
After first night next 2s₂ nights the snowball signalling is increased each 2nd day, next s₁ days the signalling is increased each day.

Oops no, that would not work. the hook is possible only for the first fail.

Title: Re: 5 Prisoners And A Light Bulb
Post by Hippo on Dec 2^nd, 2010, 3:25am

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 ...