Author |
Topic: Prisoners again- with 2 switches (Read 17578 times) |
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
 |
Re: Prisoners again- with 2 switches
« Reply #25 on: Aug 5th, 2010, 3:38am » |
 Quote  Modify
|
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 (apa/(a+1))<1/2 resp. equally iff \sum (pa/(a+1))\ge 1/2.
[edit]Oops coppying removes indexing tags  .[/edit]
|
| « Last Edit: Aug 5th, 2010, 3:53am by Hippo » |
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Prisoners again- with 2 switches
« Reply #26 on: Aug 5th, 2010, 10:17am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Prisoners again- with 2 switches
« Reply #27 on: Aug 5th, 2010, 2:13pm » |
Quote Modify
|
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 p0<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.
|
| « Last Edit: Aug 5th, 2010, 3:11pm by Hippo » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Prisoners again- with 2 switches
« Reply #28 on: Aug 5th, 2010, 3:10pm » |
Quote Modify
|
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.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
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.
|
| « Last Edit: Aug 6th, 2010, 1:07am by Hippo » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
on Aug 5th, 2010, 2:13pm, 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.255 .015
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
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 p0>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 p0>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 p0 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.
|
| « Last Edit: Aug 9th, 2010, 8:41am by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
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 p0>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 p0 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.
|
| « Last Edit: Aug 11th, 2010, 12:38am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print