Another prisoners and hats problem

From a friend at facebook: "Email I just got from Peter Winkler:

100 prisoners will be fitted with red or blue hats according to fair coinflips. Then the lights are turned on; each prisoner sees every other hat color and must write down a guess for his own. If a majority (at least 51) get their own hat color right, all the prisoners will be freed.

As usual the prisoners can't communicate once the hats are placed, but have time to strategize beforehand. Can they achieve a 90% probability of being freed? How about 95%?" 100 prisoners will be fitted with red or blue hats according to fair coinflips. Then the lights are turned on; each prisoner sees every other hat color and must write down a guess for his own. If a majority (at least 51) get their own hat color right, all the prisoners will be freed.

\*\*\*

I thought I got a way but it is not getting the chance of success over 95% so any idea from fellow at LG welcome!

90% seems easy if my calculation was correct. No idea so far for 95%.

I guess you get to 92.04% ?

What happens with your algo for the 50-50 case happening the most?

Yep, I get 92.04. I made that calculation very quickly, so had no great confidence, but if you get the same it's probably correct. :-)

In the 50-50 case all 100 would guess incorrectly with my strategy. In the 100-0 and 0-100 cases all would get it right.

I got a little improvement over the simple scheme but I have no way of measuring it for 100 people. I've made some calculations for 20 instead.

Here's the simple voting stats for comparison:

863820 escapes out of 1048576 (82.380295%)

popcount 0: 1 escapes out of 1 (100.000000%)

popcount 1: 20 escapes out of 20 (100.000000%)

popcount 2: 190 escapes out of 190 (100.000000%)

popcount 3: 1140 escapes out of 1140 (100.000000%)

popcount 4: 4845 escapes out of 4845 (100.000000%)

popcount 5: 15504 escapes out of 15504 (100.000000%)

popcount 6: 38760 escapes out of 38760 (100.000000%)

popcount 7: 77520 escapes out of 77520 (100.000000%)

popcount 8: 125970 escapes out of 125970 (100.000000%)

popcount 9: 167960 escapes out of 167960 (100.000000%)

popcount 10: 0 escapes out of 184756 (0.000000%)

Here's my algorithm:

883174 escapes out of 1048576 (84.226036%)

popcount 0: 1 escapes out of 1 (100.000000%)

popcount 1: 20 escapes out of 20 (100.000000%)

popcount 2: 187 escapes out of 190 (98.421053%)

popcount 3: 1074 escapes out of 1140 (94.210526%)

popcount 4: 4040 escapes out of 4845 (83.384933%)

popcount 5: 13901 escapes out of 15504 (89.660733%)

popcount 6: 37009 escapes out of 38760 (95.482456%)

popcount 7: 53376 escapes out of 77520 (68.854489%)

popcount 8: 71741 escapes out of 125970 (56.950861%)

popcount 9: 167860 escapes out of 167960 (99.940462%)

popcount 10: 184756 escapes out of 184756 (100.000000%)

Hint: the prisoners don't have to behave the same way.

Maybe I am not getting the terms of the problem right, but if no communication is allowed after the lights are turned on, and if I cannot see what the others write down, then I think it can be proven that the chance of getting my color right is exactly 50%, no matter what my "strategy" is. Therefore the probability of 51 or more correct guesses is 0.460205.

If the guess must be instant after turning on the  lights I agree with 92,04%. But there doesn't seem to be a time indication, so they could write down their guess let's say after 1 hour, 1 day, 5 days, ...?

With that setup, I'm convinced there are strategies that everyone knows their hat color. Or 100% certainty of being freed.

Despite the success when the number of blue and red hats are different, the simple strategy mentioned is a complete failure when there equally many blue and red hats. In this case, every single prisoner will guess the wrong color. One could perhaps imagine a mixed strategy in which a prisoner will guess the least numerous color when they differ by 1 with a certain probability (or a certain portion of the prisoners could be instructed in advance to do this). However, this will affect the cases when the number of read and blue hats differ by 2. Since these cases are almost twice as common as the ones with equally many red and blue hats, it seems difficult to obtain an overall advantage in this way (and that is before we have considered the effects on the other cases if we make further adjustments in order to compensate). The only elements I can imagine in a mixed strategy are: Pick the most numerous color, pick the least numerous color, pick red, pick blue. But I don't see how to improve on the trivial strategy, and I am curious how alihv found an improvement.

Although the prisoners may count the hats that they can see, they are not allowed to communicate with each other. Therefore, time is not an issue.

It is true that each prisoner has a 50% chance of getting their own color right, from their own perspective. Nevertheless, guessing the color that is most numerous among the 99 hats that are visible is a strategy that works perfectly well for the purpose whenever the number of blue and red hats are different (assuming an even number of prisoners). This is possible because the events of guessing correctly using this scheme are not independent.

Somehow the three section have come in the opposite order here (I wrote them, then cut them to check that I had not missed any recent comments, then pasted).

magicnonno, the probability of a person getting his color correctly is indeed 50%. However, an optimal strategy could make it so that when the prisoners escape, exactly 51 of 100 is correct, but when they fail, then 100 of 100 are wrong.

Now let us denote the probability of successful escape by p. The chance of getting it right for a single person is 0.51p = 0.50, therefore p is about 0.98. I believe that's the upper bound on the success rate.

Tasmanian Devil,

> or a certain portion of the prisoners could be instructed in advance to do this

Yeah, perfect. Now when you've instructed everybody what to do if they see a 50-49 split, imagine that you see a 51-48 split. If you're in the minority, then each of the 51 majority guys will see a 50-49 split so they know what to do. More importantly, you know what they will do, so you know how many points they will score.

alihv, could you please explain your strategy in English?

what they do when they see 48r/51b, when they see 49r/50b, other cases...

Tasmanian Devil, I searched this way, throwing a biased coin when they see 49/50 to avoid being all wrong in case of 50/50 at the cost of being more wrong on 49/51, but it does not work well...

The simple algorithm of announcing the majority fails in the most probable case of the Gaussian that is 7.96%, for the 50/50 case... Seeing 49/50 in the 49/51 case only happens half of 7.82%.

@Carroll: what happens with: say majority if it is 51+, else 58 people r determinated 2 say blue, 42 red?

Hard to answer to such non sentences when English is not your language ...

In case of majority algorithm for the case 42r/58b, red people see 41r and a majority of 58b so they write "blue" and are wrong. Blue people see 42r and a majority of 57b and write "blue" and are right...

So out of the 100 prisoners who write "blue", 58 are right and they are freed.

> alihv, could you please explain your strategy in English?

OK. Every prisoner gets assigned a number 1-100.

If you see 50\49 split: if your number is between 1 and 51, join the minority, else join the majority.

(I call the 1-51 the Mensheviks and 52-100 the Bolsheviks :))

If you see N\99-N split (N > 50, recursive on N):

if you're minority, then each majority guy sees an N-1\100-N split. Simulate the strategy assuming you're the minority. Now you know what those guys will do if you're the minority, let's say they score P points. If they win by themselves (P > 51), join the majority. If they can't be helped (51 - P > 99 - N), join the majority. Otherwise count the number of minority guys with the number lower than yours, let this number be K. If K < 51 - P, join the minority. If K >= 51 - P, those K guys will take care of the minority case without you so join the majority.

I've figured out how to simulate it for 100 but I didn't do it yet.

correction: the minority case can't be helped if 51 – P > 100 – N

I don't understand how the rank can help, even in the 50/50 case:

Suppose out of the 50 reds, 25 are numbered 1-25 and 25 are numbered 76-100, similarly for the 50 blue, 25 are numbered 26-50 and 25 are numbered 51-75: 25r-25b-25b-25r.

They all see a 50\49 split so the 1-25r select minority red, the 26-50b select minority blue, so we have 50 prisoners selecting right color, but for the ones numbered from 51 to 100 they will all chose majority so wrong color:

they don't reach 51 good predictions and are not saved.

Carroll, 51 prisoners "join the minority" (which I interpret as "pick the least numerous color") and are correct, not 50. But I found it difficult to follow the 51/49 case. What exactly do you do when you see 51/48? There is an "otherwise" in the text, and it is not clear to me which "if" it belongs to.

Carroll,

Tasmanian Devil is right, the 51-th prisoner picks minority.

Tasmanian Devil,

the intention was a cascade of checks, "otherwise" meant "in case none of the above produced an answer".

Maybe this will help?

if (P > 51) { pick majority }

else if (51 – P > 100 - N) { pick majority }

else if (K < 51 – P) { pick minority }

else { pick majority }

Oops, the forum did some strange things to formatting. Anyway, I hope it's clear...

If the prisoners are allowed to see what each other has written down then they can guarantee 50 correct guesses. They pair up, the prisoner on the left writes down their partner's hat colour and the prisoner on the right copies it. The prisoners on the right all guess correctly and it's virtually certain that at least one of the other 50 guesses will be correct.

This is probably cheating though...

Or how about this. The prisoners are told beforehand to count the number of red hats they see. If it's odd, go to the left of the room. If it's right, go to the right of the room. I think this will result in 2 groups of people each with the same colour hat regardless of the split.

Both suggestions would be a form of communication.

It does say in the question that the prisoners can strategize before the hats are placed. My first solution may be pushing it but I don't see an issue with the second one.

It also says, no communication after the hats are placed. There are a number of ways they could solve the problem if they were allowed to signal each other. For example, they could form pairs and just show each other what they had by moving to one particular side of the room, wink with the right or the left eye, and so on.

Is there a way to write a formula for what we want to optimize, that is the probability that at least 1+n/2 prisoners guess their hat?

Do you think this probability is highest when the average number of prisoners guessing right goes just above 51? Any link between this probability and expectation?

If PGuess(i) is the probability with an algorithm that i prisoners guessed their hats:

P = product (i=0 to 50) (1-PGuess(i))   (not 0 guessed right and not 1 guessed right and ... not 50 guessed right)

E = sum (i=0 to 100)(i*PGuess(i))

I will give you my current best strategy which gives a 92.197% equal to 1-C(100,49)/2^100

Each prisoner announces the color of the majority if majority is bigger (strictly) than 50.

In case he see a 50\49 split, he announces the color of the minority.

He is right in case of a 50\50 split, and in case of n\100-n with n>51. He is wrong in half the cases 51\49 and 49\51 when he sees 50\49 or 49\50 which amounts to only C(100,49) instead of C(100,50) for the naive majority strategy.

> He is wrong in half the cases

In all the cases of 51\49 split the prisoners fail to escape, and that is C(100,49)+C(100,51)=2*C(100,49) cases. Or are you counting something else?

Yes you are right,my mistake

99 prisoners would be more fun

So, at the end of the day, did anyone come up with an algorithm that results in more than 92.04% probability to escape?

At this point I tend to believe it is impossible, but I would be happy to be proved wrong.

From Johan Wästelund:

A group of an even number of people can choose to either "play safe", by half of them guessing that their number of blue hats is even and the other half guessing it's odd, or "gamble", by letting all of them guess on the same parity.

Here is a strategy that achieves 31/32:

Start by letting the first two people gamble. If they win (and everyone else will see whether they do without any illegal communication), then the remaining 98 play safe, while if they lose, the next 4 will gamble. In the latter case, if those 4 win, again all remaining play safe, while if they lose, the next 8 will gamble, and so on.

With this strategy, we achieve winning probability 3/4 with 6 people, 7/8 with 14, 15/16 with 30, and 31/32 with 62. Then we can let the last 38 play safe regardless.

We can improve to 125/128 = 97.65625% by starting from the first four people playing the "not 2-2"-strategy which loses with probability 3/8, and then halving the losing probability four times by groups of the next 6, 12, 24 and 48 people.

He then said "I can actually improve that to1129480068741774213 / 1152921504606846976 = 97.96677954%"

I'm not sure how it works but I'll try to program it.

If other prisoners can see what the first 2 gambled, isn't that a form of communication?

I thought this was not an option.

I don't think the other 98 can see if the first two are correct without communication.

On second thought, they can see if the first two are right when only considering each other.

It's interesting how close Wästelund's strategy comes to the upper bound that alihv mentioned earlier. In general, if there are n prisoners in total with n even, no strategy can give a success probability higher than n/(n+2). I was thinking of running through all possible strategies for n=4 (that is, assigning a guess for each player for each of the 2^(n-1) possible combinations that he can see) to see if it was possible to improve on 5/8. Fortunately, I didn't, because the optimal success probability must be an integer divided by 2^n (the integer being the number of successes among all 2^n combinations of red/blue hats). So we actually have an upper bound of [(n/(n+2)) * 2^n] / (2^n) where [x] means floor(x). (I am assuming that each player can have a fixed guess for each combination and does not need to introduce any randomness. This way of thinking of a strategy overrides what I wrote earlier about possible elements in a strategy, by the way.) For n = 4 and 6, this gives 5/8 and 3/4 respectively, which we have already attained in the discussion above. For n = 8, our bounds are 3/4 <= P <= 51/64, and for n = 10, we have 13/16=832/1024 <= P <= 853/1024. Can we tighten these bounds?

Can you explain Wäslund's algo?

Starting with this sentence:

"Start by letting the first two people gamble. If they win (and everyone else will see whether they do without any illegal communication), then the remaining 98 play safe"

If they gamble and are right (p=1/2) then next 98 prisoners (who play safe assuming even probability of blue on the 98 prisoners) must get at least 49 good guesses out of 98 (51%), this gives 25.5% and i don't see how in the case they are wrong this will bump up the probability to 31/32 ?

The safe strategy means that any set of 2k players can always guarantee k right and k wrong guesses if this is satisfactory. So if the first two players win, the remaining 98 players play safe and get 51 right answers. If the first two players are wrong, the remaining group raises the stakes by letting four players gamble. If the four win, they have eliminated the bad start of the first two players. Otherwise, the group raises the stakes again by letting eight players gamble. The probability of failure for the whole group is halved for every time they can raise the stakes. It's like playing odd or even numbers in roulette and doubling the bet for every time you lose until you win, except that you don't care how much you can lose, you just want to maximize the probability of ending with a profit.

Wästelund or Wäslund's strategy is probvably optimal when the total number of prisoners is of the form 2^k-2, as the probability of success in these cases is equal to the upper bound.

"probvably" should be "provably", not "probably".

Carroll,

Thanks for bringing this in, this is awesome! I understand the strategy but not your question. I'm going to explain the strategy.

A prisoner from a "gambling" team counts the blue hats of his team, if the number is odd, he bets that his hat is blue, otherwise red. So if the number of blue hats in a gambling team is even, the entire team scores, otherwise none of them score.

A "safe" team consists of two equal parts. The first part does exactly the same as if they were on the gambling team - these guys don't even need to care which kind of team they're in. The second part bets on the opposite color. A safe team always achieves exactly half the score.

Since the expectancy of the prisoners' score is exactly 50, we want to achieve escapes as tight as possible and the failures as total as possible. The algorithm is going to achieve in every case either an escape with at most 1 point too many or a total failure (score = 0).

For 4 prisoners: always vote majority. There are C(4,2)=6 total failures and the rest works with either 3 or 4 points.

Now if we have an algorithm for a particular even N, we're going to build algorithms for 2 N + 2 and 2 N + 4. The first N prisoners follow the algorithm.

If they fail: the rest N + 2 or N + 4 gamble. If they fail, the whole 2 N + 2 (+ 4) fail completely. If they win, we get N + 2 = (2 N + 2) / 2 + 1 - the exact amount of points we need - or N + 4 = (2 N + 4) / 2 + 1 + 1, so 1 point more than we need.

If the first N prisoners succeed: they bring us either N/2 + 1 points (exactly what we need) or N/2 + 2 (one point extra). The rest plays safe, bringing us N/2 + 1 (resp. N / 2 + 2) points for a total of at most N+3 (resp. N+4). We need (2N+2)/2+1 = N+2 (resp. (2N+4)/2+1=N+3) points to win, so it's at most 1 point extra.

Now we just go for N = 100 via 4 -> 10 -> 22 -> 48 -> 100.

Nice. The strategy is basically identical to the 'failsafe' roulette system of always doubling if you lost.

Awesome!

Yes sorry for miss writing his name, he is Johan Wästlund: https://wastlund.blogspot.fr/2017/06/13532385396179-number-which-is-its-own.html

I also tried to improve on the algorithm by recursively finding F(N, k), the highest possible probability for N prisoners to get k correct answers, but so far I "only" got to 97.915856769...% for F(100, 51). :-)

The program actually found improvements in both the smaller cases I asked for earlier: F(8, 5) >= 49/64 and F(10, 6) >= 209/256 = 836/1024.

Now I got 97.96677954...% as well. No change in the smaller cases.

What is the size of the first group of prisoners you start from in your algorithm?

If it is in python you can use the Fractions package to get an exact figure, or send me the algo I can code it in python...

My algorithm considers a number of different approaches, including groups of 1-4 players (1 player could announce beforehand that he will pick red, and the others can see if he is right). It chooses the best one, but I don't know which of the approaches are contributing and which don't.

In your recursive formula, when a subset s of N gambles (or try to get max probability of having k good guesses) and fails , how many good guesses do you take into account for the next step of (N-s)?

Or if you care to give your recursion?

for N = 1 to 100

for k = 0 to 100

if 2*k <= N then F[N][k] = 1 {play safe}

elseif k > N then F[N][k] = 0 {impossible to get more right answers than prisoners}

elseif k = N then F[N][k] = 0.5 {gambling to get all correct}

else

F[N][k] = (F[N-1][k-1] + F[N-1][k]) / 2 {one player could "gamble", and the other N-1 could optimize accordingly}

x = (F[N-2][k-2] + F[N-2][k]) / 2 {two players could gamble, and the other N-2 could optimize accordingly}

if x > F[N][k] then F[N][k] = x {update if impovement}

if F[N-2][k-1] > F[N][k] then F[N][k] = F[N-2][k-1] {update if letting two prisoners play safe is an improvement}

if N > 3 then

{try letting three players play according to different strategies}

x = (F[N-3][k-3] + F[N-3][k]) / 2 {let all three gamble}

if x > F[N][k] then F[N][k] = x {update if improvement}

x = (F[N-3][k-2] + F[N-3][k-1]) / 2 {let two of them play safe; the third picks a pre-selected color}

if x > F[N][k] then F[N][k] = x {update if improvement}

x = (F[N-3][k-3] + 3 * F[N-3][k-1]) / 4 {the three players maximize the chance of getting 2 right}

if x > F[N][k] then F[N][k] = x {update if improvement}

x = (3 * F[N-3][k - 2] + F[N-3][k]) / 4 {opposite of last strategy}

if x > F[N][k] then F[N][k] = x {update if improvement}

endif

if (N > 4) and (k > 3) then

{let four players guess the most numerous color among them, or the opposite strategy}

x = (F[N-4][k-4] + 4 * F[N-4][k-3] + 3 * F[N-4][k]) / 8

if x > F[N][k] then F[N][k] = x

x = (3 * F[N-4][k-4] + 4 * F[N-4][k-1] + F[N-4][k]) / 8

if x > F[N][k] then F[N][k] = x

endif

{Then same (most/least numerous color) for 6 and 8 players - details left out}

for i = 1 to k

x = (F[N-i][k-i] + F[N-i][k]) / 2 {let any number of prisoners gamble, then play accordingly}

if x > F[N][k] then F[N][k] = x

next i

for j = 2 to N

if j|N and j|k then

x = F[N/j][k/j] {partition the prisoners into blocks of j people who always "gamble" together}

if x > F[N][k] then F[N][k] = x

next j

for i 0 = ceiling(k/2) to floor((N-1)/2)

x = (1+F[N-2*i][k-i]) / 2 {play safe with i players if that is enough, otherwise gamble}

if x > F[N][k] then F[N][k] = x

next i

endif

next k

next N

If there are errors, then it is possible that they appeared when I typed here, and that they are not in the actual code.

It is possible that there exist strategies for only 4 players that could lead to further improvements. If I have calculated correctly, then if we could attain distributions of 0-10-0-2-4, 0-10-1-0-5, 4-2-0-10-0 and 5-0-1-10-0 for 0, 1, 2, 3 and 4 correct answers, then all other distributions would lie in the convex hull of the ones we have found, and they would give improvements for F[10][6] and F[100][51]. Alas, I did not find any examples of these after running a few thousand simulations.