wu :: forums - Print Page


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

        riddles >> hard >> Prisoners again- with 2 switches
        
(Message started by: mad on Feb 25^th, 2008, 10:24am)

Title: Prisoners again- with 2 switches
Post by mad on Feb 25^th, 2008, 10:24am

The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'on' or the 'off' position. I am not telling you their present positions. The switches are not connected to anything.

"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell.

"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.' and be 100% sure.

"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."

What is the strategy they come up with so that they can be free?

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Feb 25^th, 2008, 11:01am

Of course if you don't optimize the number of visits, you can reduce the problem to 2 state switch without timing (the other switch does not carry information in this strategy).

Title: Re: Prisoners again- with 2 switches
Post by Icarus on Feb 25^th, 2008, 3:37pm

This is the 100 Prisoners & 2 Lightbulbs (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#100prisoners2LightBulbs) riddle. There is a thread for it here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1030162865;start=).

It doesn't look like that thread ever came to a full consensus on the solution, however.

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Feb 25^th, 2008, 4:00pm

on 02/25/08 at 15:37:06, Icarus wrote:

Not exactly as they must switch exactly one switch during each visit.

Title: Re: Prisoners again- with 2 switches
Post by Grimbal on Feb 26^th, 2008, 12:51am

There is a difference.

In "100 prisoners and a light bulb" there is a version with 1 visit a day, which allows the meaning of the switch to change from day to day, and there is a version without a time line that requires that every visit to is handled in the same way.

In this riddle, the prisoners can distinguish 2 cases. The switch can have a different meaning depending on whether both switches are in the same position or not. I am not sure how (and whether) that distinction can be put to use efficiently.

Title: Re: Prisoners again- with 2 switches
Post by jollytall on Feb 26^th, 2008, 2:16am

This seems to be the same as the original one, that had been discussed among Hungarian mathematicians' and was the basis of the 100 prisoners riddle. The original is still available on IBM's page (http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/July2002.html).

There are two main differences between the 100 prisoners and 1 light ball and this one:
There are two switches. BUT a prisoner must switch one. This means it is the same in terms of information as one switch that you might or might not change.
There is no fixed period of visits, i.e. all periodicity related solutions are out of question. As a second consequence of it, the switch can never be known as reset to "off". In the fixed period game we can say that the first visitor sets it to "off" and the game starts on the second day, knowing that the switch's original position is off. In the game without fixed periods, we can never know whether the game has started at all. This is why the best solution known waits until everybody was there twice.

The two prisoners and 2 (or n) light balls is totally different, if you can decide whether change the status of one or two or none of the switches.

Title: Re: Prisoners again- with 2 switches
Post by rmsgrey on Feb 26^th, 2008, 11:32am

As Grimbal pointed out, you can reliably distinguish between the two parities of visit-events, however it's not obvious how to take advantage of that - particularly with the unknown initial state potentially adding more spurious counts.

The best I can come up with would be to start each prisoner with 3 tokens (a single and a double) and pass single tokens on the A visits, and doubles on the B visits, with prisoners merging pairs of single tokens into doubles where possible, and the designated counter never passing a token.

I suspect this will run slower than ignoring the parity information and just running the standard 2-tokens per prisoner, single phase solution.

I also suspect that any gains from passing larger bundles of tokens on the B visits will be swamped by the cost of having more tokens per prisoner to start with - essentially, you're looking at starting each prisoner with an A-token and a B-token and having a rule whereby A-tokens can be converted into B-tokens (but not vice versa) at the cost of making both types of token harder to collect - under standard conditions, a token gets collected every time the counter visits and at least one token-bearer has visited since the counter's last visit. With the alternating A/B, a token only gets collected when the counter visits and the previous visitor was a token-bearer - obviously far worse...

Title: Re: Prisoners again- with 2 switches
Post by Icarus on Feb 26^th, 2008, 4:27pm

Because the prisoners are forced to flip a switch, the relative positions of the switches (= or not =) will switch with every visit. I think the fact that the visitors must always flip a switch pretty much destroys the utility of the second switch for sending messages.

Here is one solution:

The left switch will be considered meaningless. Visitors who do not wish to send a message will flip it. This reduces the problem to 100 prisoners and 1 light bulb with uneven visits and uncertain initial state. To solve that problem:

Pick a leader. On the leader's first visit he will flip the (right) switch, and remember the position he left it in. No one else is to ever flip the switch unless:
(1) the switch is currently on, and
(2) they have seen the switch off before, and
(3) they haven't flipped the switch before.

Any time that the leader visits and sees the switch off when he did not leave it off, he will increment his count and turn the light back on. If the switch is in the same position he left it in before, he will flip the switch, but not increment his count.

When his count reaches 99, he declares everyone has visited.

-------------------------------

Regular prisoners only get one chance to be counted. But they have to wait until they are sure that their message will be heard. That is, until they are sure that the leader has visited the room. So we have the rule that no one else can touch the switch until they have seen the switch in both positions. This can only occur after the leader's initial visit. Unfortunately, it is quite possible that someone's first visit may not come until everyone else has already been counted. If the leader did not switch the light off himself, this person would never have the opportunity to see the light in both positions, and so would never be sure that it was safe to send his message. Therefore, the leader has to switch the light on and off himself, even though when he switches it off, it means that no messages can be sent until he visits again.

Title: Re: Prisoners again- with 2 switches
Post by jollytall on Feb 27^th, 2008, 12:21am

As I also pointed out before and agreeing with Icarus there is no difference between 1 switch optional to be switched and 2 switches where one and only one must be switched. As Icarus says, you only look at switch A, while switch B is only used to switch something if you do not want to switch A. So in this context there is no difference between this variation and the 100 prisoners and 1 switch.

The uncertainty of the initial position is causing the problem. Because of the non predictable periodicity, there is no chance to re-set the switch if the initial state is not known.
This is why the standard solution (single pre-appointed leader) counts until 197, allowing every prisoner to show his presence twice. Because of the uncertainty of the initial state, one count of the first prisoner might be lost. In this case 197 is reached when all prisoners were there twice. If the first count is not lost, then 197 is reached when 98 prisoners were there 2 times and 1 only once.

This approach is safe and probably also much faster than Icarus's one, where the counting only starts when every priosoner already had seen the switch in both positions.

Edit note: A xor B reference removed.

Title: Re: Prisoners again- with 2 switches
Post by Icarus on Feb 27^th, 2008, 3:50pm

A xor B switches with every visit, so its state can't be used for passing information. This is why I went with one switch and ignored the other.

While the two-token method certainly works better than mine, I think the problem is not missing the first visitor's count, but rather falsely counting a visit that didn't actually occur. If the switch is initially in the message position, no one realizes that it wasn't set that way by an earlier visitor, so the false count is picked up by the Leader. I would say that leader needs to count to 198 to be sure he has counted everyone.

Title: Re: Prisoners again- with 2 switches
Post by towr on Feb 27^th, 2008, 11:52pm

on 02/27/08 at 15:50:08, Icarus wrote:

If the switch is initially in the message position, no one realizes that it wasn't set that way by an earlier visitor, so the false count is picked up by the Leader. I would say that leader needs to count to 198 to be sure he has counted everyone.

Well, the leader knows he hadn't been there to reset the switch; he can only be sure that something is a message after his first visit.
If he counts what he encounters on his first visit as possibly being a real message, then he'd have to count to 198; if he disregards it, he'd have to count to 197 (and the first prisoner's first message may have gone wasted).

Title: Re: Prisoners again- with 2 switches
Post by jollytall on Feb 28^th, 2008, 2:44am

Forget my comment re A xor B. Original post edited.

As towr say, the difference is in the starting position. If the leader starts counting once he reset the switch, the counting should go up to 197 (and so, 1 visit of 1 prisoner might be lost). If the leader already counts the first time he goes in (if the switch tells him to count), then he might count the initial state as a false visit, so he has to count up to 198.

Title: Re: Prisoners again- with 2 switches
Post by Grimbal on Feb 28^th, 2008, 4:47am

So, for 23 prisoners, how many does he count?

Title: Re: Prisoners again- with 2 switches
Post by jollytall on Feb 28^th, 2008, 6:24am

2*(n-2)+1, i.e. 43 with the most comonly accepted logic.

To further clarify the two logics:

If the leader starts to count once he reset the switch during his first visit, he must count till 43 (23 prisoners).
If the leader is already allowed to count 'one' when he enters (and finds the switch switched on) then he needs to count till 44. But if he finds the switch off at his first visit, that means that the switch was off at the beginning AND noone has visited it yet, he doesn't need to count 44 (although that is not a problem either), but 43 is sufficient.

With other words the two logics are the same most of the cases, but the "start counting after your first visit and count till 43" is shorter in that case when the leader visits the room first and the original status of the switch is off. This has 1/46 probability, when the 44 counting is results in a longer escape time.

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Feb 28^th, 2008, 3:45pm

It seems to me now we agree that it is 23C2 problem refered by n prisoners and a k-state switch (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1177584051) as the parity of number of visits does not carry any usefull information.

Title: Re: Prisoners again- with 2 switches
Post by Icarus on Feb 28^th, 2008, 4:03pm

on 02/27/08 at 23:52:59, towr wrote:

I see. Thanks.

I know I've read these threads before, but I failed to remember the logic.

Title: Re: Prisoners again- with 2 switches
Post by mattian on May 11^th, 2010, 2:09pm

THIS IS MY SOLUTION
Please let me know if there are any holes in this approach.

Step 1

Use switch A as the primary switch which may be toggled or left alone as necessary. Use switch B as a dummy switch that allows a prisoner to leave switch A alone. Thus switch A becomes a single optional switch, while switch B absorbs "noise" and carries no information.

Step 2

Elect a leader. The leader is responsible for managing the state of switch A (hereafter referred to as "the switch").

Step 3

Assign a count of 1 (a token) to each prisoner before commencing.

Strategy:

Any non-leader who enters the room will abide by the following rules:

1. If only one state (either 1 or 0) has EVER been seen on the switch, do nothing, retain token and skip the remaining steps.
2. If both states (both 1 and 0) have been seen on the switch then NOTE that the leader has visited at least once and continue with step 3.
3. If the current state is 0 and current prisoner has a token, then set switch to 1 and relinquish token.
4. If the current state is 1 then do nothing, but remember for next time that leader the has visited at least once.
5. If the current state is 0 and the current prisoner has no tokens, do nothing.

The leader when he enters will do the following:

a. If the initial value of the switch was 0, then set it to 1. This will not allow any prisoners to submit their tokens because the switch will remain at 1 until A returns. But this is fine because it allows some prisoners to witness a state change (see Step 2.) thus informing them that the leader has visited at least once and allowing them to submit their tokens at their next opportunity.

b. If the initial value of the switch was 1, then set it to 0. This allows some prisoners to see a state change thus informing them that the leader has visited at least once and allowing them to submit their tokens at the next opportunity.

c. At any point the leader may opt to leave the switch at 1 instead of resetting it to 0, if he is missing prisoners who may potentially have missed a state change. It is safe to do so because in the 1 position, no one can misleadingly submit a token. The prisoner can use his discretion to determine how long to leave the switch in a chosen state, but he will collect counts only when he witnesses a change from 0 to 1 (ie. when he leaves the switch at 0 and returns to find it at 1). But he cannot forget that every prisoner has to get the signal that he has started counting - and that signal comes in the form of a state change that they have witnessed.

d. When the leader's count reaches 23, declare that all prisoners have visited.

Note: If the leader sets the switch to 0 and a subsequent prisoner sets it to one by "submitting" his token, a third prisoner might see the state change before the leader sees it. This is not a problem because ANY state change is indicative of the fact that the leader has visited and counting has started. But that third prisoner won't submit a token at that visit because the switch will be at 1, so he will retain his token until a later visit.

----------------------------------
UPDATE:

I just reread the thread. Turns out icarus already posted this solution. My apologies.

Title: Re: Prisoners again- with 2 switches
Post by rmsgrey on May 12^th, 2010, 2:36pm

My intuition (as in it's been 5-6 years since I worked seriously on this family of problems, and I'm not about to try working out solid figures) is that it's best for the leader to flip the signal switch on every visit, but that 23 prisoners is more than enough for "count twice and possibly miss one" to be more efficient than waiting for every prisoner to have seen the signal switch change state and then been able to pass a signal...

Title: Re: Prisoners again- with 2 switches
Post by towr on May 13^th, 2010, 4:20am

The "count twice and possibly miss one" approach takes 1128.05 visits, from what my program tells me. Icarus' and Mattian's approach takes 718.43 visits. (Well, assuming Mattian makes the same choice in case c) as Icarus.)

Title: Re: Prisoners again- with 2 switches
Post by rmsgrey on May 13^th, 2010, 8:44am

Shows what intutition is worth! :D

Title: Re: Prisoners again- with 2 switches
Post by towr on May 13^th, 2010, 9:49am

There is room for optimization as well. When the leader returns to the room and find the light is on, if he only flips the switch with 50% chance, the process only takes 676.22 visits on average; at 10%, it's 649.86. Making that probability depend in some way on how often he visited before should improve things further.
Most people will have seem the light off in the first 200 visits, so there's little point to switching the light off for the leader after that point. (But of course he only knows how often he has visited himself, plus how many he has counted. But after 10 visits he can estimate there have likely been over 200 visits.)

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Aug 3^rd, 2010, 6:33am

So for the leader strategy in 2nC case (single counting).
What about to count number of known switches and visits from the last counted prisoner. When the number of visits exceeds number of switches he sends activation signal (dummy switch).

... I would think about this kind of optimisation :)

[edit]I continue on http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1177584051;start=0#16[/edit]

Title: Re: Prisoners again- with 2 switches
Post by SMQ on Aug 3^rd, 2010, 8:10am

I'm still working on the details, but the leader should, in fact, be able to estimate, based on the number of uncounted prisoners and the number of times he has visited since the last count, whether leaving the light on or off is more likely to result in a successful count. His estimate would be based on an estimate of the chances of the light remaining off because no one countable had visited the room versus their not having seen a state change.

--SMQ

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Aug 5^th, 2010, 2:22am

on 05/13/10 at 09:49:57, towr wrote:

What about to switch on only when probability drones will switch on is less than 1/2? How to compute this probability is described in the other thread.

Title: Re: Prisoners again- with 2 switches
Post by towr on Aug 5^th, 2010, 3:17am

It sounds like something that might work, but I'm not quite sure how the leader can best estimate that probability, which depends on the number of times he's visited, his current count, and his previous decisions.
The last factor especially would explode a simulation to find out (too many possible histories).

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Aug 5^th, 2010, 3:38am

From the other thread ... maintain probabilities that a prisoners are active (have seen switch on).
Maintain number of already counted drones.

So O(n) probabilities and O(1) space are sufficient for simulation. And O(n) divisions, multiplications and additions for single step of counter.

(I am not sure with optimality, but I hope it would be closer.:))

There is formula how to recompute the probabilities when counter let switch off depending on the switch position on return. There is similar formula when he let switch on, but in that case switch remains on surely.

---------------
Unknown state for the counter is (i,a,d) where i+a+d+1=n; i is number of drones never seeing switch on, a is number of drones whose have seen switch on, but which didn't switch it and d are drones which already manipulated the switch.

With switch on (i,a) wents to (i-k,a+k) with probability 1/(i+1), and with switch off it goes with proability 1/(a+1) to switch off and conditional transition probablity of (i,a) is 1, and with probability a/(a+1) switch changes to on and in that case conditional transition probabilities to (i-k,a+k-1) become 1/(i+1).

With d known to counter i=n-1-d-a so just (a) suffices to describe the unknown state.
Let pa be probability the unknown state is (n-1-d-a,a) or shortly (a). \suma pa=1.

If the counter left room with switch off the total probability switch remain off is \suma pa/(a+1) so knowing switch remain off rebalances our probabilities to p'a=(pa/(a+1))/\sumb(pb/(b+1)).

Similarly for switch changed to on rebalances original probabilities to p'a=apa/(a+1)/sumb(bpb/(b+1)).

So the resulting probabilities of (n-1-(d+1)-a,a) are p''a=\sumb\le a+1p'b/(n-d-b)=\sumb\le a+1bpb/((b+1)(n-d-b)\sumccpc/(c+1)).

Leaving counter in on state results in counter in on state next visit, but probabilities p'a are changed to \sumb\le apb/(n-d-b).

--------------------
So swith on iff \sum (ap_a/(a+1))<1/2 resp. equally iff \sum (p_a/(a+1))\ge 1/2.

[edit]Oops coppying removes indexing tags :(.[/edit]

Title: Re: Prisoners again- with 2 switches
Post by SMQ on Aug 5^th, 2010, 10:17am

One slight adjustment: the threshold probability needs to be very slightly smaller than 1/2 or the leader will turn the switch on with one drone remaining and leave it on forever (because the probability approaches 1/2 asymptotically from below).

Selecting the threshold probability too low means that it takes a long time to cross the threshold in the rare case where there are no active drones. Selecting the probability too high means that the light is left on unnecessarily when there are active but uncounted drones. With 23 prisoners, a value of 0.4995 seems to work well, and gives an expected runtime of just over 633 days.

--SMQ

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Aug 5^th, 2010, 2:13pm

Oh yes, counting the last drone is problem with this strategy. Solution is to switch on for last drone if probability the drone is inactive < 1/2.

Due to rounding errors typically the probability is rounded to 0. So I would increase probabilty less than \epsilon to \epsilon. So sequence of off states would be eventually terminated.

But as this is exception to the rest of algorithm, I am suspicious to beleive the solution is optimal.

I got average roughly 640 visits from first 550 simulations...

But in all cases I studied log ... counter switched on at most once :) ... the probability to switch on quickly goes to 0. ... Not at all there were several simulations when counter returns day after it switch on. After letting switch twice off it was forced to switch it on. I have not find simulation with this problem repeated, but the algorithm is well prepared for it.

I would for safety reasons convert p₀<epsilon to epsilon after each step. And the 0,49995 treshold is good alternative to exception in termination.

Oops I have started all simulations with switch off.

Now the average is roughly 634.

Title: Re: Prisoners again- with 2 switches
Post by towr on Aug 5^th, 2010, 3:10pm

I wish I had a decent computer to do the calculations on, then I could try to see if a genetic algorithm (or similar) could optimize the solution. But a full simulation took long enough as it was.

Oh, and one question, do you switch deterministically, or probabilistically? It sounds like it's the former; is that best?.

And what is the expected variation on your results if you're using monte carlo simulations? (I've based my simulations on state transitions, so it's slower, but it leaves no room for variations in the result.)

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Aug 5^th, 2010, 3:14pm

It is deterministic. I am counting the simulations depending on each number of visits. ... So I would give graph of distributions ... now I am on 50000 simulations ... it's rather slow :). ... May be the scrolling slows it down rapidly :).

I was not trying to compute probabilities it terminates on given day, there is a lot of cases with very small probabilities ... one need at least long integers implementation. The system must know counter history so finite number of states is insufficient.
(At least grows with number of simulated days).

... 633.3

I am thinking about strategy with switching on when probability nobody is active is at least 1/2.
It would have simillar behaviour and probably easier simulation. There could be other approximations making almost same decisions.
May be they would be usable for computing exact distribution.

Title: Re: Prisoners again- with 2 switches
Post by SMQ on Aug 6^th, 2010, 6:03am

on 08/05/10 at 14:13:42, Hippo wrote:

Oh yes, counting the last drone is problem with this strategy. Solution is to switch on for last drone if probability the drone is inactive < 1/2.

That's definitely (slightly) non-optimal. It's rare that the last drone is inactive, but when it happens you want to "err on the side of caution" and turn the light on after only a handful of rounds without a count. The rounds lost in the case when the drone is actually active are more than made up for by the rounds saved when the drone is indeed inactive.

With 23 prisoners, using my adjusted threshold of 0.4995, the light is turned on after around 7.5 leader visits with no count (fewer if there have been a lot of rounds with no count earlier in the run), and toggled every round thereafter until the final drone is counted. The threshold of 0.4995 is equivalent to turning on the light when the probability the last drone is inactive has dropped to only 0.999; waiting until it drops below 0.5 adds an average of five leader rounds (or about 100 days) to the cases where the last drone is actually inactive.

Put another way, turning the light on "early" with the last drone has only a small effect on the chance of an active drone to be counted, but has a large effect on the chance of an inactive drone to become active.

Below are the results of 10 million simulated runs, with an average runtime of 633.255http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif.015

--SMQ

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Aug 6^th, 2010, 8:34am

I suppose you were on te path to implement the same algorithm ... I just presented the details earlier ...

I am not sure with the reasoning for the last inactive drone. I guess probability this situation happen is of order 1/23!. So solving the situation faster is not as important. ... I am going to made some more tests in early future.

... Switching on for p₀>1/2 whole the algoritm gives avearge around 633 as well. I am not sure simulation could find which one is better.

I am logging all cases when there is difference in decisions and mostly the p₀>1/2 makes better decisions (I didn't find the case it chosen to switch off when the last drone were not initialised ... 622 visits this simulation).

Once in the openning ofter first drone was counted there was switch off period which would not be by the original algorithm and there was no active drone.

So I am highly interested on knowing distribution of 10000000 simulations of this one as well :). (with the \epsilon hook ... to prevent rounding p₀ to 0).

This one sometimes loses on cases with pMmMmPpMpMmMmMm(M) history (lowercase input, uppercase output).
Or with mPpMpMmMpMmMmMmM history,
but several times it gains on such history...
It almost always gains on cases with pMpMpMpMpMpMpMpMpMpMpMpMpMpMpMmMpMpMpMpMmMpMpMpMmMmMmMmMmMmMmMm(M) history.

... looks like this has average 633+/-0.2

Hmm, the distribution graphs does not show visible diferences (Except with very small probabilities the long runs are much often in the older strategy).

... Better experiment would be:
Run simulations, but divide simulations to 3 cases ... the decisions are equal, the dicisions first difference is with less than 11 drones counted, the rest. Counting distribution in each case separately, and in the case of difference run parallel simulation.

This may help to find which strategy is better.
(The decision at ending could chose proper strategy for ending and switching to it at ending and running simulation again could choose proper strategy for openning) ...

Form 467979 simulations 107 differ in openning and 2167 differ at ending.
When ending differ the original algorithm average is above 767 days while the new algorithm average is under 723 days.

Openning without changed ending ... original algorithm average is under 703,5 while the new algorithm above 704. So may be finally combined algorithm would be the best one. Of course 107 cases with difference under 1 is not enough to say something, but 2167 with difference above 45 days is convincing.

So far (for the openning) it looks the strategies differ in 0.02% of cases, and the difference is around 4 visits. Which makes difference around 0.0008 visits in the context of all the runs.

The slightly better looks the strategy switching on in openning whenever chance someone else swithces on is less then 1/2. And switching on in ending whenever chance nobody is active is at least 1/2.

Title: Re: Prisoners again- with 2 switches
Post by Hippo on Aug 11^th, 2010, 12:18am

A lot of next simulations computed distribution of number of visits when the strategies differ, but nothing was visible from it. So I have changed the test to compute the difference of number of visits
and after roughly 7500000 simulations 1687 computations where the decisions differ gives following distribution on visits difference:
(Plus means p₀>1/2 openning strategy is worse.) 45% cases with no difference was removed from the distribution to emphasize the rest.

It seems to me it's clear the comined strategy wins.
So what remains is to decide what is the best time for switch.

I have find one case the difference appears when 8 prisoners were counted and one case when 7 prisoners were. In both the cases there were active prisoners and p₀ decision was better.

So may be I should group the statistics to bundles by the number of already counted prisoners.

But I am not sure 10^8 experiments would be enough to say something (and I expect the difference in the algorithms total behaviour would be less than 10^{-6} visits in average).

But when I am thinking about this difference statistics ... number of counter visits difference would be probably more interesting.