Re: [math-fun] two problems from a Facebook thread (SPOILER)
(I remember the days of putting in ^L ^L ^L at the top of an email before posting a spoiler. Is there something comparable that works for modern email readers?) The prisoners can achieve a probability of success exceeding 90% if each person sees which color predominates among the 99 hats that he sees and then guesses that his hat is that same color. This only fails when there's a 50-50 split, which happens about 8% of the time. I believe that this is best possible, but I don't have even the beginnings of a proof. Jim Propp On Sun, Jun 18, 2017 at 1:42 PM, Thane Plambeck <tplambeck@gmail.com> wrote:
(1) (via Peter Winkler) Here's a (seemingly) new hat puzzle for you:
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%?
(2) (Johan Wästlund) I'll just throw in here a question of (what turns out to be) similar flavor: Suppose you play a type of one-person tic-tac-toe where in every "move" you select a set of unoccupied squares, and then flip a coin to decide whether you get all those squares, or your "opponent" gets them. What winning probability can you achieve?
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/ _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I believe that this is best possible, but I don't have even the beginnings of a proof.
Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance of success on a 50-50 split, and only decreases the failure on a 49-51 overall split from 100% to ~100%, so I think the overall success is around 96% as the problem suggests. It's interesting that the solution smacks of a (reverse) gambler's fallacy. Even more, if the problem slightly favored one color, you often put the prisoners in the paradoxical position of having to play an individually losing/irrational strategy that somehow works en masse.
Oops, strike that first paragraph! I'm inclined to agree with Propp. On Mon, Jun 19, 2017 at 4:12 AM, James Davis <lorentztrans@gmail.com> wrote:
I believe that this is best possible, but I don't have even the beginnings of a proof.
Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance of success on a 50-50 split, and only decreases the failure on a 49-51 overall split from 100% to ~100%, so I think the overall success is around 96% as the problem suggests.
It's interesting that the solution smacks of a (reverse) gambler's fallacy. Even more, if the problem slightly favored one color, you often put the prisoners in the paradoxical position of having to play an individually losing/irrational strategy that somehow works en masse.
Why strike it? It convinced me! What's the fallacy? Jim On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com> wrote:
Oops, strike that first paragraph! I'm inclined to agree with Propp.
On Mon, Jun 19, 2017 at 4:12 AM, James Davis <lorentztrans@gmail.com <javascript:;>> wrote:
I believe that this is best possible, but I don't have even the beginnings of a proof.
Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance of success on a 50-50 split, and only decreases the failure on a 49-51 overall split from 100% to ~100%, so I think the overall success is around 96% as the problem suggests.
It's interesting that the solution smacks of a (reverse) gambler's fallacy. Even more, if the problem slightly favored one color, you often put the prisoners in the paradoxical position of having to play an individually losing/irrational strategy that somehow works en masse.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Me too. I was thinking that 51 answers that agree with the majority is enough, but we need 51 answers that are accurate to their own hat. In a 51-49 split, the 51 folks who see 49-50 are those who would get the right answer under your strategy, but not necessarily the modified. The 49 folks who see the 51-49 split as 51-48 are *still* getting the wrong answer under the simple or modified strategy (Hence Dan's idea about switching). Since 51-49 or 49-51 is about twice as likely as 50-50, it seems tricky to make a rule that gives 50-50 a chance of success without dropping the success of 49-51 below 50%. On Mon, Jun 19, 2017 at 10:56 AM, James Propp <jamespropp@gmail.com> wrote:
Why strike it? It convinced me! What's the fallacy?
Jim
On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com> wrote:
Oops, strike that first paragraph! I'm inclined to agree with Propp.
On Mon, Jun 19, 2017 at 4:12 AM, James Davis <lorentztrans@gmail.com <javascript:;>> wrote:
I believe that this is best possible, but I don't have even the beginnings of a proof.
Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance of success on a 50-50 split, and only decreases the failure on a 49-51 overall split from 100% to ~100%, so I think the overall success is around 96% as the problem suggests.
It's interesting that the solution smacks of a (reverse) gambler's fallacy. Even more, if the problem slightly favored one color, you often put the prisoners in the paradoxical position of having to play an individually losing/irrational strategy that somehow works en masse.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think Jim's solution is the optimal symmetrical solution, where each prisoner uses the same algorithm, but there might be better asymmetric strategies. A configuration C is a map C : {prisoners} -> {R, B} A guessing strategy is a map S:{configurations} x {prisoners} -> {R, B}, with the constraint that if C1(Q) = C2(Q), for all Q != P, then S(C1, P) = S(C2, P) (this expresses the fact that you can't see your own hat) Given a strategy S we have a "guessed-right" subset G of {configurations} x {prisoners}, where (C,P) is in G whenever S(C,P) = C(P) The size of G, for any strategy, is exactly half of |configurations| * |prisoners|, since when C1 and C2 only differ by prisoner P's hat, the constraint on strategies means that exactly one of (C1, P) and {C2, P) is in G. So we can divide the domain of S into pairs, each containing exactly one element of G. Since we can't change the total number of correct guesses (summed over all configurations and all prisoners), the way to maximize the number of configurations with 51 or greater correct guesses would be to have winning configurations with as close as possible to 51 correct guesses, and losing configurations with as close to 100 incorrect guesses as possible. Jim's solution does perfextly on the latter criterion; when the prisoners lose, every prisoner guesses wrong, which is perfect. But it does poorly on the first criterion; when there are 95 blue hats, for example, then 95, rather than 51, prisoners guess right, which is wasteful. If there were fewer prisoners who guessed right in these configurations, then there would be more correct guesses available for other configurations, allowing the possibility of fewer losing configurations.i If the prisoner's strategy is symmetric, then the number of correct guesses with 5 blue hats is either 0, 5, 95, or 100, which is why I think Jim's is the best symmetric solution. But an asymmetric one, where only 51 prisoners answer correctly with (at least some) 95-5 configurations, will leave more correct guesses available for other configs, possibly allowing us to decrease the number of "all-fail" configs. So I'm not convinced that Jim's solution is optimal when we include asymmetric strategies. Asymmetric strategies can be very complicated; not only do different prisoners have different algorithms, put a prisoner's guesses may depend not only on the hat count, but on exactly which prisoners have blue hats. I think I can prove that randomness doesn't help, that is, that the best nondeterministic strategy is no better than the best deterministic strategy. A nondeterministic strategy is map S:{configurations} x {prisoners} x P -> {R, B}, where P has a measure on it with total measure 1. P is the set f all possible "die rolls", or whatever other randomization technique the prisoners employ. The "Can't see your own hat" restriction in this case is just that for each p in P, the map S restricted to p satisfies the above restriction. Each element p in P has an associated set of success configurations (where 51 or more prisoners are correct). and the overall success probability of S is just the integral over P of the success probability of the strategy restricted to p. So the average value can never be greater than the maximum value, and there is some particular die roll we can choose in advance which does at least as well as the randomized strategy does overall. Andy On Mon, Jun 19, 2017 at 12:03 PM, James Davis <lorentztrans@gmail.com> wrote:
Me too. I was thinking that 51 answers that agree with the majority is enough, but we need 51 answers that are accurate to their own hat.
In a 51-49 split, the 51 folks who see 49-50 are those who would get the right answer under your strategy, but not necessarily the modified. The 49 folks who see the 51-49 split as 51-48 are *still* getting the wrong answer under the simple or modified strategy (Hence Dan's idea about switching). Since 51-49 or 49-51 is about twice as likely as 50-50, it seems tricky to make a rule that gives 50-50 a chance of success without dropping the success of 49-51 below 50%.
On Mon, Jun 19, 2017 at 10:56 AM, James Propp <jamespropp@gmail.com> wrote:
Why strike it? It convinced me! What's the fallacy?
Jim
On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com> wrote:
Oops, strike that first paragraph! I'm inclined to agree with Propp.
On Mon, Jun 19, 2017 at 4:12 AM, James Davis <lorentztrans@gmail.com <javascript:;>> wrote:
I believe that this is best possible, but I don't have even the beginnings of a proof.
Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance of success on a 50-50 split, and only decreases the failure on a 49-51 overall split from 100% to ~100%, so I think the overall success is around 96% as the problem suggests.
It's interesting that the solution smacks of a (reverse) gambler's fallacy. Even more, if the problem slightly favored one color, you often put the prisoners in the paradoxical position of having to play an individually losing/irrational strategy that somehow works en masse.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
Yeah, Andy has the right point of view here. I think that the prisoners can guess majority-correctly around 98% of the time. Think of the configuration space as the vertices and 1-dimensional edges of the 100-dimensional unit cube. A single vertex corresponds to one possible coloring of all prisoners' hats. Prisoner p gets to look at the other 99 hats, i.e. knows that the config is one of the two endpoints of one particular edge of the cube (an edge oriented parallel to the p'th basis vector). Therefore a strategy for the prisoners corresponds to assigning an *orientation* to each edge of the cube: the arrow on the edge tells the prisoner to guess the hat color they would have in the configuration the arrow points to. We want to orient all the edges so that most vertices have 51 arrows pointing at them, and the rest have ~100 arrows pointing away. If we didn't need to think about the connectivity of the cube, then of course this would be easy: for each group of fifty-one points, have one with 100 out-edges, and the other fifty with 51 in-edges and 49 out-edges. That would have the prisoners win 50/51 of the time. With an actual 100-dim cube, we surely can't quite attain that upper bound; for example the number of vertices is 2^100, which is widely known to not be a multiple of 51. But I have some hand-wavy intuition that says we should be able to get pretty close to it. Here's my plan. Pick a random 1/51 of the points to be the "losers" where we guess nearly all wrong. Now for each other point ("winner"), draw two paths connecting it to nearby losers. If it has two neighbors who are losers then this is really easy (and Bernoulli says that should be the case around 59% of the time). If you can't do this using just its immediate neighbors, then try to draw a path of length greater than 1 to a further-away loser, but don't use any already-used edges. Maybe this will be too hard with exactly ceiling(1/51) of the points being losers; those losers would need to end up with all 100 of their edges used by these paths. But if we increase the density of losers a bit, say from 1/51 = 1.96% to 2.5%, then on average each loser would only have around 80 of its 100 edges used by all the disjoint paths. It seems to me (hand-wavy!) that this is low-enough density that fitting all the paths in should be easy. Once we have this collection of edge-disjoint paths, we can easily build a strategy from it. For each edge on the path from a loser to a winner, orient all the edges to point from the loser end towards the winner end. Each winner now has two in-edges because of the two paths we drew connecting it to losers, plus some matched set of in/out pairs of edges because of other paths which passed through it, leaving an even number of not-yet-oriented edges. We can orient all of the remaining edges via Eulerian paths through the graph: the only places where these remaining paths would start/end are at the maybe-odd-degree losers, and so on all the winners, they preserve the property of having two more in-edges than out-edges. if we did go with 2.5% losers, then those vertices would each end up with around 10 people guessing correctly and 90 guessing wrong, while all the winners were 51-49 correct. The closer we can drive the loser density to 1/51, the closer the losers will get to all 100 people guessing incorrectly. How close you can come to optimal seems like a weird coding-theory-ish sort of question, but the fact that you can use arbitrarily long paths to connect winners to losers (as long as they all remain edge-disjoint) makes the codes point of view taste funny. --Michael On Mon, Jun 19, 2017 at 1:07 PM, Andy Latto <andy.latto@pobox.com> wrote:
I think Jim's solution is the optimal symmetrical solution, where each prisoner uses the same algorithm, but there might be better asymmetric strategies.
A configuration C is a map C : {prisoners} -> {R, B} A guessing strategy is a map S:{configurations} x {prisoners} -> {R, B}, with the constraint that if
C1(Q) = C2(Q), for all Q != P, then
S(C1, P) = S(C2, P) (this expresses the fact that you can't see your own hat)
Given a strategy S we have a "guessed-right" subset G of {configurations} x {prisoners}, where (C,P) is in G whenever S(C,P) = C(P)
The size of G, for any strategy, is exactly half of |configurations| * |prisoners|, since when C1 and C2 only differ by prisoner P's hat, the constraint on strategies means that exactly one of (C1, P) and {C2, P) is in G. So we can divide the domain of S into pairs, each containing exactly one element of G.
Since we can't change the total number of correct guesses (summed over all configurations and all prisoners), the way to maximize the number of configurations with 51 or greater correct guesses would be to have winning configurations with as close as possible to 51 correct guesses, and losing configurations with as close to 100 incorrect guesses as possible.
Jim's solution does perfextly on the latter criterion; when the prisoners lose, every prisoner guesses wrong, which is perfect. But it does poorly on the first criterion; when there are 95 blue hats, for example, then 95, rather than 51, prisoners guess right, which is wasteful. If there were fewer prisoners who guessed right in these configurations, then there would be more correct guesses available for other configurations, allowing the possibility of fewer losing configurations.i
If the prisoner's strategy is symmetric, then the number of correct guesses with 5 blue hats is either 0, 5, 95, or 100, which is why I think Jim's is the best symmetric solution. But an asymmetric one, where only 51 prisoners answer correctly with (at least some) 95-5 configurations, will leave more correct guesses available for other configs, possibly allowing us to decrease the number of "all-fail" configs. So I'm not convinced that Jim's solution is optimal when we include asymmetric strategies. Asymmetric strategies can be very complicated; not only do different prisoners have different algorithms, put a prisoner's guesses may depend not only on the hat count, but on exactly which prisoners have blue hats.
I think I can prove that randomness doesn't help, that is, that the best nondeterministic strategy is no better than the best deterministic strategy. A nondeterministic strategy is map
S:{configurations} x {prisoners} x P -> {R, B}, where P has a measure on it with total measure 1. P is the set f all possible "die rolls", or whatever other randomization technique the prisoners employ. The "Can't see your own hat" restriction in this case is just that for each p in P, the map S restricted to p satisfies the above restriction.
Each element p in P has an associated set of success configurations (where 51 or more prisoners are correct). and the overall success probability of S is just the integral over P of the success probability of the strategy restricted to p. So the average value can never be greater than the maximum value, and there is some particular die roll we can choose in advance which does at least as well as the randomized strategy does overall.
Andy
On Mon, Jun 19, 2017 at 12:03 PM, James Davis <lorentztrans@gmail.com> wrote:
Me too. I was thinking that 51 answers that agree with the majority is enough, but we need 51 answers that are accurate to their own hat.
In a 51-49 split, the 51 folks who see 49-50 are those who would get the right answer under your strategy, but not necessarily the modified. The 49 folks who see the 51-49 split as 51-48 are *still* getting the wrong answer under the simple or modified strategy (Hence Dan's idea about switching). Since 51-49 or 49-51 is about twice as likely as 50-50, it seems tricky to make a rule that gives 50-50 a chance of success without dropping the success of 49-51 below 50%.
On Mon, Jun 19, 2017 at 10:56 AM, James Propp <jamespropp@gmail.com> wrote:
Why strike it? It convinced me! What's the fallacy?
Jim
On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com> wrote:
Oops, strike that first paragraph! I'm inclined to agree with Propp.
On Mon, Jun 19, 2017 at 4:12 AM, James Davis <lorentztrans@gmail.com <javascript:;>> wrote:
I believe that this is best possible, but I don't have even the beginnings of a proof.
Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance of success on a 50-50 split, and only decreases the failure on a 49-51 overall split from 100% to ~100%, so I think the overall success is around 96% as the problem suggests.
It's interesting that the solution smacks of a (reverse) gambler's fallacy. Even more, if the problem slightly favored one color, you often put the prisoners in the paradoxical position of having to play an individually losing/irrational strategy that somehow works en masse.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
You can definitely improve things by a different strategy. For very small examples -- 6, 8, 10 and 12 prisoners you can write an integer program to give you the best strategy. What I mean is the following -- prisoner i, has a function f_i of the assignment of hat colors that he can see -- i.e. a function {0,1}^{n-1} ---> {0,1} which tells him what color to guess. You have 2^{n-1}*n 0/1 integer variables for that function. You then have 2^n 0/1 variables which are 1, if the majority of the guesses are correct. The objective, to maximize, is the sum of all of those variables. A uniform strategy would make all of the functions the same. I found, that for n=6, 8, 10, 12 that the best uniform function was guessing along with the majority, and an arbitrary guess if there's a 50-50 split. However, in the non-uniform case you can do a lot better. For n=6, you can get 48 out 64 assignments correct, as opposed to 44 For n=8, you can get 204 out of 256 assignments correct, as opposed to 186 For n=10, you can get 853 out of 1024 assignments correct, as opposed to 772 For n=12, you can get 3497 out of 4096 assignments correct, as opposed to 3172 (I don't know if 3497 is the best -- the program hasn't finished). The computation for n=12 is taking quite a while, so I probably won't be going much further. Victor On Mon, Jun 19, 2017 at 8:04 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Yeah, Andy has the right point of view here. I think that the prisoners can guess majority-correctly around 98% of the time.
Think of the configuration space as the vertices and 1-dimensional edges of the 100-dimensional unit cube. A single vertex corresponds to one possible coloring of all prisoners' hats. Prisoner p gets to look at the other 99 hats, i.e. knows that the config is one of the two endpoints of one particular edge of the cube (an edge oriented parallel to the p'th basis vector).
Therefore a strategy for the prisoners corresponds to assigning an *orientation* to each edge of the cube: the arrow on the edge tells the prisoner to guess the hat color they would have in the configuration the arrow points to. We want to orient all the edges so that most vertices have 51 arrows pointing at them, and the rest have ~100 arrows pointing away.
If we didn't need to think about the connectivity of the cube, then of course this would be easy: for each group of fifty-one points, have one with 100 out-edges, and the other fifty with 51 in-edges and 49 out-edges. That would have the prisoners win 50/51 of the time.
With an actual 100-dim cube, we surely can't quite attain that upper bound; for example the number of vertices is 2^100, which is widely known to not be a multiple of 51. But I have some hand-wavy intuition that says we should be able to get pretty close to it.
Here's my plan. Pick a random 1/51 of the points to be the "losers" where we guess nearly all wrong. Now for each other point ("winner"), draw two paths connecting it to nearby losers. If it has two neighbors who are losers then this is really easy (and Bernoulli says that should be the case around 59% of the time). If you can't do this using just its immediate neighbors, then try to draw a path of length greater than 1 to a further-away loser, but don't use any already-used edges. Maybe this will be too hard with exactly ceiling(1/51) of the points being losers; those losers would need to end up with all 100 of their edges used by these paths. But if we increase the density of losers a bit, say from 1/51 = 1.96% to 2.5%, then on average each loser would only have around 80 of its 100 edges used by all the disjoint paths. It seems to me (hand-wavy!) that this is low-enough density that fitting all the paths in should be easy.
Once we have this collection of edge-disjoint paths, we can easily build a strategy from it. For each edge on the path from a loser to a winner, orient all the edges to point from the loser end towards the winner end. Each winner now has two in-edges because of the two paths we drew connecting it to losers, plus some matched set of in/out pairs of edges because of other paths which passed through it, leaving an even number of not-yet-oriented edges. We can orient all of the remaining edges via Eulerian paths through the graph: the only places where these remaining paths would start/end are at the maybe-odd-degree losers, and so on all the winners, they preserve the property of having two more in-edges than out-edges.
if we did go with 2.5% losers, then those vertices would each end up with around 10 people guessing correctly and 90 guessing wrong, while all the winners were 51-49 correct. The closer we can drive the loser density to 1/51, the closer the losers will get to all 100 people guessing incorrectly.
How close you can come to optimal seems like a weird coding-theory-ish sort of question, but the fact that you can use arbitrarily long paths to connect winners to losers (as long as they all remain edge-disjoint) makes the codes point of view taste funny.
--Michael
On Mon, Jun 19, 2017 at 1:07 PM, Andy Latto <andy.latto@pobox.com> wrote:
I think Jim's solution is the optimal symmetrical solution, where each prisoner uses the same algorithm, but there might be better asymmetric strategies.
A configuration C is a map C : {prisoners} -> {R, B} A guessing strategy is a map S:{configurations} x {prisoners} -> {R, B}, with the constraint that if
C1(Q) = C2(Q), for all Q != P, then
S(C1, P) = S(C2, P) (this expresses the fact that you can't see your own hat)
Given a strategy S we have a "guessed-right" subset G of {configurations} x {prisoners}, where (C,P) is in G whenever S(C,P) = C(P)
The size of G, for any strategy, is exactly half of |configurations| * |prisoners|, since when C1 and C2 only differ by prisoner P's hat, the constraint on strategies means that exactly one of (C1, P) and {C2, P) is in G. So we can divide the domain of S into pairs, each containing exactly one element of G.
Since we can't change the total number of correct guesses (summed over all configurations and all prisoners), the way to maximize the number of configurations with 51 or greater correct guesses would be to have winning configurations with as close as possible to 51 correct guesses, and losing configurations with as close to 100 incorrect guesses as possible.
Jim's solution does perfextly on the latter criterion; when the prisoners lose, every prisoner guesses wrong, which is perfect. But it does poorly on the first criterion; when there are 95 blue hats, for example, then 95, rather than 51, prisoners guess right, which is wasteful. If there were fewer prisoners who guessed right in these configurations, then there would be more correct guesses available for other configurations, allowing the possibility of fewer losing configurations.i
If the prisoner's strategy is symmetric, then the number of correct guesses with 5 blue hats is either 0, 5, 95, or 100, which is why I think Jim's is the best symmetric solution. But an asymmetric one, where only 51 prisoners answer correctly with (at least some) 95-5 configurations, will leave more correct guesses available for other configs, possibly allowing us to decrease the number of "all-fail" configs. So I'm not convinced that Jim's solution is optimal when we include asymmetric strategies. Asymmetric strategies can be very complicated; not only do different prisoners have different algorithms, put a prisoner's guesses may depend not only on the hat count, but on exactly which prisoners have blue hats.
I think I can prove that randomness doesn't help, that is, that the best nondeterministic strategy is no better than the best deterministic strategy. A nondeterministic strategy is map
S:{configurations} x {prisoners} x P -> {R, B}, where P has a measure on it with total measure 1. P is the set f all possible "die rolls", or whatever other randomization technique the prisoners employ. The "Can't see your own hat" restriction in this case is just that for each p in P, the map S restricted to p satisfies the above restriction.
Each element p in P has an associated set of success configurations (where 51 or more prisoners are correct). and the overall success probability of S is just the integral over P of the success probability of the strategy restricted to p. So the average value can never be greater than the maximum value, and there is some particular die roll we can choose in advance which does at least as well as the randomized strategy does overall.
Andy
On Mon, Jun 19, 2017 at 12:03 PM, James Davis <lorentztrans@gmail.com> wrote:
Me too. I was thinking that 51 answers that agree with the majority is enough, but we need 51 answers that are accurate to their own hat.
In a 51-49 split, the 51 folks who see 49-50 are those who would get the right answer under your strategy, but not necessarily the modified. The 49 folks who see the 51-49 split as 51-48 are *still* getting the wrong answer under the simple or modified strategy (Hence Dan's idea about switching). Since 51-49 or 49-51 is about twice as likely as 50-50, it seems tricky to make a rule that gives 50-50 a chance of success without dropping the success of 49-51 below 50%.
On Mon, Jun 19, 2017 at 10:56 AM, James Propp <jamespropp@gmail.com> wrote:
Why strike it? It convinced me! What's the fallacy?
Jim
On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com> wrote:
Oops, strike that first paragraph! I'm inclined to agree with Propp.
On Mon, Jun 19, 2017 at 4:12 AM, James Davis <lorentztrans@gmail.com <javascript:;>> wrote:
> I believe that this is best possible, but I don't have even the beginnings > of a proof.
Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance of success on a 50-50 split, and only decreases the failure on a 49-51 overall split from 100% to ~100%, so I think the overall success is around 96% as the problem suggests.
It's interesting that the solution smacks of a (reverse) gambler's fallacy. Even more, if the problem slightly favored one color, you often put the prisoners in the paradoxical position of having to play an individually losing/irrational strategy that somehow works en masse.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think I'm missing something. 853/1024 and 3497/4096 are both less than .9, so how is this an improvement? Jim Propp On Wednesday, June 21, 2017, Victor Miller <victorsmiller@gmail.com> wrote:
You can definitely improve things by a different strategy. For very small examples -- 6, 8, 10 and 12 prisoners you can write an integer program to give you the best strategy. What I mean is the following -- prisoner i, has a function f_i of the assignment of hat colors that he can see -- i.e. a function {0,1}^{n-1} ---> {0,1} which tells him what color to guess. You have 2^{n-1}*n 0/1 integer variables for that function. You then have 2^n 0/1 variables which are 1, if the majority of the guesses are correct. The objective, to maximize, is the sum of all of those variables. A uniform strategy would make all of the functions the same. I found, that for n=6, 8, 10, 12 that the best uniform function was guessing along with the majority, and an arbitrary guess if there's a 50-50 split. However, in the non-uniform case you can do a lot better.
For n=6, you can get 48 out 64 assignments correct, as opposed to 44 For n=8, you can get 204 out of 256 assignments correct, as opposed to 186 For n=10, you can get 853 out of 1024 assignments correct, as opposed to 772 For n=12, you can get 3497 out of 4096 assignments correct, as opposed to 3172 (I don't know if 3497 is the best -- the program hasn't finished).
The computation for n=12 is taking quite a while, so I probably won't be going much further.
Victor
On Mon, Jun 19, 2017 at 8:04 PM, Michael Kleber <michael.kleber@gmail.com <javascript:;>> wrote:
Yeah, Andy has the right point of view here. I think that the prisoners can guess majority-correctly around 98% of the time.
Think of the configuration space as the vertices and 1-dimensional edges of the 100-dimensional unit cube. A single vertex corresponds to one possible coloring of all prisoners' hats. Prisoner p gets to look at the other 99 hats, i.e. knows that the config is one of the two endpoints of one particular edge of the cube (an edge oriented parallel to the p'th basis vector).
Therefore a strategy for the prisoners corresponds to assigning an *orientation* to each edge of the cube: the arrow on the edge tells the prisoner to guess the hat color they would have in the configuration the arrow points to. We want to orient all the edges so that most vertices have 51 arrows pointing at them, and the rest have ~100 arrows pointing away.
If we didn't need to think about the connectivity of the cube, then of course this would be easy: for each group of fifty-one points, have one with 100 out-edges, and the other fifty with 51 in-edges and 49 out-edges. That would have the prisoners win 50/51 of the time.
With an actual 100-dim cube, we surely can't quite attain that upper bound; for example the number of vertices is 2^100, which is widely known to not be a multiple of 51. But I have some hand-wavy intuition that says we should be able to get pretty close to it.
Here's my plan. Pick a random 1/51 of the points to be the "losers" where we guess nearly all wrong. Now for each other point ("winner"), draw two paths connecting it to nearby losers. If it has two neighbors who are losers then this is really easy (and Bernoulli says that should be the case around 59% of the time). If you can't do this using just its immediate neighbors, then try to draw a path of length greater than 1 to a further-away loser, but don't use any already-used edges. Maybe this will be too hard with exactly ceiling(1/51) of the points being losers; those losers would need to end up with all 100 of their edges used by these paths. But if we increase the density of losers a bit, say from 1/51 = 1.96% to 2.5%, then on average each loser would only have around 80 of its 100 edges used by all the disjoint paths. It seems to me (hand-wavy!) that this is low-enough density that fitting all the paths in should be easy.
Once we have this collection of edge-disjoint paths, we can easily build a strategy from it. For each edge on the path from a loser to a winner, orient all the edges to point from the loser end towards the winner end. Each winner now has two in-edges because of the two paths we drew connecting it to losers, plus some matched set of in/out pairs of edges because of other paths which passed through it, leaving an even number of not-yet-oriented edges. We can orient all of the remaining edges via Eulerian paths through the graph: the only places where these remaining paths would start/end are at the maybe-odd-degree losers, and so on all the winners, they preserve the property of having two more in-edges than out-edges.
if we did go with 2.5% losers, then those vertices would each end up with around 10 people guessing correctly and 90 guessing wrong, while all the winners were 51-49 correct. The closer we can drive the loser density to 1/51, the closer the losers will get to all 100 people guessing incorrectly.
How close you can come to optimal seems like a weird coding-theory-ish sort of question, but the fact that you can use arbitrarily long paths to connect winners to losers (as long as they all remain edge-disjoint) makes the codes point of view taste funny.
--Michael
On Mon, Jun 19, 2017 at 1:07 PM, Andy Latto <andy.latto@pobox.com <javascript:;>> wrote:
I think Jim's solution is the optimal symmetrical solution, where each prisoner uses the same algorithm, but there might be better asymmetric strategies.
A configuration C is a map C : {prisoners} -> {R, B} A guessing strategy is a map S:{configurations} x {prisoners} -> {R, B}, with the constraint that if
C1(Q) = C2(Q), for all Q != P, then
S(C1, P) = S(C2, P) (this expresses the fact that you can't see your own hat)
Given a strategy S we have a "guessed-right" subset G of {configurations} x {prisoners}, where (C,P) is in G whenever S(C,P) = C(P)
The size of G, for any strategy, is exactly half of |configurations| * |prisoners|, since when C1 and C2 only differ by prisoner P's hat, the constraint on strategies means that exactly one of (C1, P) and {C2, P) is in G. So we can divide the domain of S into pairs, each containing exactly one element of G.
Since we can't change the total number of correct guesses (summed over all configurations and all prisoners), the way to maximize the number of configurations with 51 or greater correct guesses would be to have winning configurations with as close as possible to 51 correct guesses, and losing configurations with as close to 100 incorrect guesses as possible.
Jim's solution does perfextly on the latter criterion; when the prisoners lose, every prisoner guesses wrong, which is perfect. But it does poorly on the first criterion; when there are 95 blue hats, for example, then 95, rather than 51, prisoners guess right, which is wasteful. If there were fewer prisoners who guessed right in these configurations, then there would be more correct guesses available for other configurations, allowing the possibility of fewer losing configurations.i
If the prisoner's strategy is symmetric, then the number of correct guesses with 5 blue hats is either 0, 5, 95, or 100, which is why I think Jim's is the best symmetric solution. But an asymmetric one, where only 51 prisoners answer correctly with (at least some) 95-5 configurations, will leave more correct guesses available for other configs, possibly allowing us to decrease the number of "all-fail" configs. So I'm not convinced that Jim's solution is optimal when we include asymmetric strategies. Asymmetric strategies can be very complicated; not only do different prisoners have different algorithms, put a prisoner's guesses may depend not only on the hat count, but on exactly which prisoners have blue hats.
I think I can prove that randomness doesn't help, that is, that the best nondeterministic strategy is no better than the best deterministic strategy. A nondeterministic strategy is map
S:{configurations} x {prisoners} x P -> {R, B}, where P has a measure on it with total measure 1. P is the set f all possible "die rolls", or whatever other randomization technique the prisoners employ. The "Can't see your own hat" restriction in this case is just that for each p in P, the map S restricted to p satisfies the above restriction.
Each element p in P has an associated set of success configurations (where 51 or more prisoners are correct). and the overall success probability of S is just the integral over P of the success probability of the strategy restricted to p. So the average value can never be greater than the maximum value, and there is some particular die roll we can choose in advance which does at least as well as the randomized strategy does overall.
Andy
On Mon, Jun 19, 2017 at 12:03 PM, James Davis <lorentztrans@gmail.com <javascript:;>> wrote:
Me too. I was thinking that 51 answers that agree with the majority is enough, but we need 51 answers that are accurate to their own hat.
In a 51-49 split, the 51 folks who see 49-50 are those who would get the right answer under your strategy, but not necessarily the modified. The 49 folks who see the 51-49 split as 51-48 are *still* getting the wrong answer under the simple or modified strategy (Hence Dan's idea about switching). Since 51-49 or 49-51 is about twice as likely as 50-50, it seems tricky to make a rule that gives 50-50 a chance of success without dropping the success of 49-51 below 50%.
On Mon, Jun 19, 2017 at 10:56 AM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
Why strike it? It convinced me! What's the fallacy?
Jim
On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com <javascript:;>> wrote:
Oops, strike that first paragraph! I'm inclined to agree with Propp.
On Mon, Jun 19, 2017 at 4:12 AM, James Davis < lorentztrans@gmail.com <javascript:;> <javascript:;>> wrote: >> I believe that this is best possible, but I don't have even the beginnings >> of a proof. > > Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance > of success on a 50-50 split, and only decreases the failure on a 49-51 > overall split from 100% to ~100%, so I think the overall success is > around 96% as the problem suggests. > > It's interesting that the solution smacks of a (reverse) gambler's > fallacy. Even more, if the problem slightly favored one color, you > often put the prisoners in the paradoxical position of having to play > an individually losing/irrational strategy that somehow works en > masse.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com <javascript:;>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Jim, For such small n you can't get to .9. The strategy of guessing the color that the majority (that you can see) has, gives you 2^n - (2n) choose n. For n really large this is very good since 2n choose n is asymptotic (roughly) to 4^n/sqrt(n), which gets you to 90% when n=100, but nowhere near that when n is much smaller. Victor On Wed, Jun 21, 2017 at 5:44 PM, James Propp <jamespropp@gmail.com> wrote:
I think I'm missing something. 853/1024 and 3497/4096 are both less than .9, so how is this an improvement?
Jim Propp
On Wednesday, June 21, 2017, Victor Miller <victorsmiller@gmail.com> wrote:
You can definitely improve things by a different strategy. For very small examples -- 6, 8, 10 and 12 prisoners you can write an integer program to give you the best strategy. What I mean is the following -- prisoner i, has a function f_i of the assignment of hat colors that he can see -- i.e. a function {0,1}^{n-1} ---> {0,1} which tells him what color to guess. You have 2^{n-1}*n 0/1 integer variables for that function. You then have 2^n 0/1 variables which are 1, if the majority of the guesses are correct. The objective, to maximize, is the sum of all of those variables. A uniform strategy would make all of the functions the same. I found, that for n=6, 8, 10, 12 that the best uniform function was guessing along with the majority, and an arbitrary guess if there's a 50-50 split. However, in the non-uniform case you can do a lot better.
For n=6, you can get 48 out 64 assignments correct, as opposed to 44 For n=8, you can get 204 out of 256 assignments correct, as opposed to 186 For n=10, you can get 853 out of 1024 assignments correct, as opposed to 772 For n=12, you can get 3497 out of 4096 assignments correct, as opposed to 3172 (I don't know if 3497 is the best -- the program hasn't finished).
The computation for n=12 is taking quite a while, so I probably won't be going much further.
Victor
On Mon, Jun 19, 2017 at 8:04 PM, Michael Kleber < michael.kleber@gmail.com <javascript:;>> wrote:
Yeah, Andy has the right point of view here. I think that the prisoners can guess majority-correctly around 98% of the time.
Think of the configuration space as the vertices and 1-dimensional edges of the 100-dimensional unit cube. A single vertex corresponds to one possible coloring of all prisoners' hats. Prisoner p gets to look at the other 99 hats, i.e. knows that the config is one of the two endpoints of one particular edge of the cube (an edge oriented parallel to the p'th basis vector).
Therefore a strategy for the prisoners corresponds to assigning an *orientation* to each edge of the cube: the arrow on the edge tells the prisoner to guess the hat color they would have in the configuration the arrow points to. We want to orient all the edges so that most vertices have 51 arrows pointing at them, and the rest have ~100 arrows pointing away.
If we didn't need to think about the connectivity of the cube, then of course this would be easy: for each group of fifty-one points, have one with 100 out-edges, and the other fifty with 51 in-edges and 49 out-edges. That would have the prisoners win 50/51 of the time.
With an actual 100-dim cube, we surely can't quite attain that upper bound; for example the number of vertices is 2^100, which is widely known to not be a multiple of 51. But I have some hand-wavy intuition that says we should be able to get pretty close to it.
Here's my plan. Pick a random 1/51 of the points to be the "losers" where we guess nearly all wrong. Now for each other point ("winner"), draw two paths connecting it to nearby losers. If it has two neighbors who are losers then this is really easy (and Bernoulli says that should be the case around 59% of the time). If you can't do this using just its immediate neighbors, then try to draw a path of length greater than 1 to a further-away loser, but don't use any already-used edges. Maybe this will be too hard with exactly ceiling(1/51) of the points being losers; those losers would need to end up with all 100 of their edges used by these paths. But if we increase the density of losers a bit, say from 1/51 = 1.96% to 2.5%, then on average each loser would only have around 80 of its 100 edges used by all the disjoint paths. It seems to me (hand-wavy!) that this is low-enough density that fitting all the paths in should be easy.
Once we have this collection of edge-disjoint paths, we can easily build a strategy from it. For each edge on the path from a loser to a winner, orient all the edges to point from the loser end towards the winner end. Each winner now has two in-edges because of the two paths we drew connecting it to losers, plus some matched set of in/out pairs of edges because of other paths which passed through it, leaving an even number of not-yet-oriented edges. We can orient all of the remaining edges via Eulerian paths through the graph: the only places where these remaining paths would start/end are at the maybe-odd-degree losers, and so on all the winners, they preserve the property of having two more in-edges than out-edges.
if we did go with 2.5% losers, then those vertices would each end up with around 10 people guessing correctly and 90 guessing wrong, while all the winners were 51-49 correct. The closer we can drive the loser density to 1/51, the closer the losers will get to all 100 people guessing incorrectly.
How close you can come to optimal seems like a weird coding-theory-ish sort of question, but the fact that you can use arbitrarily long paths to connect winners to losers (as long as they all remain edge-disjoint) makes the codes point of view taste funny.
--Michael
On Mon, Jun 19, 2017 at 1:07 PM, Andy Latto <andy.latto@pobox.com <javascript:;>> wrote:
I think Jim's solution is the optimal symmetrical solution, where each prisoner uses the same algorithm, but there might be better asymmetric strategies.
A configuration C is a map C : {prisoners} -> {R, B} A guessing strategy is a map S:{configurations} x {prisoners} -> {R, B}, with the constraint that if
C1(Q) = C2(Q), for all Q != P, then
S(C1, P) = S(C2, P) (this expresses the fact that you can't see your own hat)
Given a strategy S we have a "guessed-right" subset G of {configurations} x {prisoners}, where (C,P) is in G whenever S(C,P) = C(P)
The size of G, for any strategy, is exactly half of |configurations|
|prisoners|, since when C1 and C2 only differ by prisoner P's hat, the constraint on strategies means that exactly one of (C1, P) and {C2, P) is in G. So we can divide the domain of S into pairs, each containing exactly one element of G.
Since we can't change the total number of correct guesses (summed over all configurations and all prisoners), the way to maximize the number of configurations with 51 or greater correct guesses would be to have winning configurations with as close as possible to 51 correct guesses, and losing configurations with as close to 100 incorrect guesses as possible.
Jim's solution does perfextly on the latter criterion; when the prisoners lose, every prisoner guesses wrong, which is perfect. But it does poorly on the first criterion; when there are 95 blue hats, for example, then 95, rather than 51, prisoners guess right, which is wasteful. If there were fewer prisoners who guessed right in these configurations, then there would be more correct guesses available for other configurations, allowing the possibility of fewer losing configurations.i
If the prisoner's strategy is symmetric, then the number of correct guesses with 5 blue hats is either 0, 5, 95, or 100, which is why I think Jim's is the best symmetric solution. But an asymmetric one, where only 51 prisoners answer correctly with (at least some) 95-5 configurations, will leave more correct guesses available for other configs, possibly allowing us to decrease the number of "all-fail" configs. So I'm not convinced that Jim's solution is optimal when we include asymmetric strategies. Asymmetric strategies can be very complicated; not only do different prisoners have different algorithms, put a prisoner's guesses may depend not only on the hat count, but on exactly which prisoners have blue hats.
I think I can prove that randomness doesn't help, that is, that the best nondeterministic strategy is no better than the best deterministic strategy. A nondeterministic strategy is map
S:{configurations} x {prisoners} x P -> {R, B}, where P has a measure on it with total measure 1. P is the set f all possible "die rolls", or whatever other randomization technique the prisoners employ. The "Can't see your own hat" restriction in this case is just that for each p in P, the map S restricted to p satisfies the above restriction.
Each element p in P has an associated set of success configurations (where 51 or more prisoners are correct). and the overall success probability of S is just the integral over P of the success probability of the strategy restricted to p. So the average value can never be greater than the maximum value, and there is some particular die roll we can choose in advance which does at least as well as the randomized strategy does overall.
Andy
On Mon, Jun 19, 2017 at 12:03 PM, James Davis < lorentztrans@gmail.com <javascript:;>> wrote:
Me too. I was thinking that 51 answers that agree with the majority is enough, but we need 51 answers that are accurate to their own hat.
In a 51-49 split, the 51 folks who see 49-50 are those who would get the right answer under your strategy, but not necessarily the modified. The 49 folks who see the 51-49 split as 51-48 are *still* getting the wrong answer under the simple or modified strategy (Hence Dan's idea about switching). Since 51-49 or 49-51 is about twice as likely as 50-50, it seems tricky to make a rule that gives 50-50 a chance of success without dropping the success of 49-51 below 50%.
On Mon, Jun 19, 2017 at 10:56 AM, James Propp < jamespropp@gmail.com <javascript:;>> wrote:
Why strike it? It convinced me! What's the fallacy?
Jim
On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com <javascript:;>> wrote:
> Oops, strike that first paragraph! I'm inclined to agree with Propp. > > On Mon, Jun 19, 2017 at 4:12 AM, James Davis < lorentztrans@gmail.com <javascript:;> > <javascript:;>> wrote: > >> I believe that this is best possible, but I don't have even the > beginnings > >> of a proof. > > > > Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance > > of success on a 50-50 split, and only decreases the failure on a 49-51 > > overall split from 100% to ~100%, so I think the overall success is > > around 96% as the problem suggests. > > > > It's interesting that the solution smacks of a (reverse) gambler's > > fallacy. Even more, if the problem slightly favored one color, you > > often put the prisoners in the paradoxical position of having to play > > an individually losing/irrational strategy that somehow works en > > masse. > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com <javascript:;> <javascript:;> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com <javascript:;>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thanks for clearing up my confusion! Jim On Wednesday, June 21, 2017, Victor Miller <victorsmiller@gmail.com> wrote:
Jim, For such small n you can't get to .9. The strategy of guessing the color that the majority (that you can see) has, gives you 2^n - (2n) choose n. For n really large this is very good since 2n choose n is asymptotic (roughly) to 4^n/sqrt(n), which gets you to 90% when n=100, but nowhere near that when n is much smaller.
Victor
On Wed, Jun 21, 2017 at 5:44 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
I think I'm missing something. 853/1024 and 3497/4096 are both less than .9, so how is this an improvement?
Jim Propp
On Wednesday, June 21, 2017, Victor Miller <victorsmiller@gmail.com <javascript:;>> wrote:
You can definitely improve things by a different strategy. For very small examples -- 6, 8, 10 and 12 prisoners you can write an integer program to give you the best strategy. What I mean is the following -- prisoner i, has a function f_i of the assignment of hat colors that he can see -- i.e. a function {0,1}^{n-1} ---> {0,1} which tells him what color to guess. You have 2^{n-1}*n 0/1 integer variables for that function. You then have 2^n 0/1 variables which are 1, if the majority of the guesses are correct. The objective, to maximize, is the sum of all of those variables. A uniform strategy would make all of the functions the same. I found, that for n=6, 8, 10, 12 that the best uniform function was guessing along with the majority, and an arbitrary guess if there's a 50-50 split. However, in the non-uniform case you can do a lot better.
For n=6, you can get 48 out 64 assignments correct, as opposed to 44 For n=8, you can get 204 out of 256 assignments correct, as opposed to 186 For n=10, you can get 853 out of 1024 assignments correct, as opposed to 772 For n=12, you can get 3497 out of 4096 assignments correct, as opposed to 3172 (I don't know if 3497 is the best -- the program hasn't finished).
The computation for n=12 is taking quite a while, so I probably won't be going much further.
Victor
On Mon, Jun 19, 2017 at 8:04 PM, Michael Kleber < michael.kleber@gmail.com <javascript:;> <javascript:;>> wrote:
Yeah, Andy has the right point of view here. I think that the prisoners can guess majority-correctly around 98% of the time.
Think of the configuration space as the vertices and 1-dimensional edges of the 100-dimensional unit cube. A single vertex corresponds to one possible coloring of all prisoners' hats. Prisoner p gets to look at the other 99 hats, i.e. knows that the config is one of the two endpoints of one particular edge of the cube (an edge oriented parallel to the p'th basis vector).
Therefore a strategy for the prisoners corresponds to assigning an *orientation* to each edge of the cube: the arrow on the edge tells the prisoner to guess the hat color they would have in the configuration the arrow points to. We want to orient all the edges so that most vertices have 51 arrows pointing at them, and the rest have ~100 arrows pointing away.
If we didn't need to think about the connectivity of the cube, then of course this would be easy: for each group of fifty-one points, have one with 100 out-edges, and the other fifty with 51 in-edges and 49 out-edges. That would have the prisoners win 50/51 of the time.
With an actual 100-dim cube, we surely can't quite attain that upper bound; for example the number of vertices is 2^100, which is widely known to not be a multiple of 51. But I have some hand-wavy intuition that says we should be able to get pretty close to it.
Here's my plan. Pick a random 1/51 of the points to be the "losers" where we guess nearly all wrong. Now for each other point ("winner"), draw two paths connecting it to nearby losers. If it has two neighbors who are losers then this is really easy (and Bernoulli says that should be the case around 59% of the time). If you can't do this using just its immediate neighbors, then try to draw a path of length greater than 1 to a further-away loser, but don't use any already-used edges. Maybe this will be too hard with exactly ceiling(1/51) of the points being losers; those losers would need to end up with all 100 of their edges used by these paths. But if we increase the density of losers a bit, say from 1/51 = 1.96% to 2.5%, then on average each loser would only have around 80 of its 100 edges used by all the disjoint paths. It seems to me (hand-wavy!) that this is low-enough density that fitting all the paths in should be easy.
Once we have this collection of edge-disjoint paths, we can easily build a strategy from it. For each edge on the path from a loser to a winner, orient all the edges to point from the loser end towards the winner end. Each winner now has two in-edges because of the two paths we drew connecting it to losers, plus some matched set of in/out pairs of edges because of other paths which passed through it, leaving an even number of not-yet-oriented edges. We can orient all of the remaining edges via Eulerian paths through the graph: the only places where these remaining paths would start/end are at the maybe-odd-degree losers, and so on all the winners, they preserve the property of having two more in-edges than out-edges.
if we did go with 2.5% losers, then those vertices would each end up with around 10 people guessing correctly and 90 guessing wrong, while all the winners were 51-49 correct. The closer we can drive the loser density to 1/51, the closer the losers will get to all 100 people guessing incorrectly.
How close you can come to optimal seems like a weird coding-theory-ish sort of question, but the fact that you can use arbitrarily long paths to connect winners to losers (as long as they all remain edge-disjoint) makes the codes point of view taste funny.
--Michael
On Mon, Jun 19, 2017 at 1:07 PM, Andy Latto <andy.latto@pobox.com <javascript:;> <javascript:;>> wrote:
I think Jim's solution is the optimal symmetrical solution, where each prisoner uses the same algorithm, but there might be better asymmetric strategies.
A configuration C is a map C : {prisoners} -> {R, B} A guessing strategy is a map S:{configurations} x {prisoners} -> {R, B}, with the constraint that if
C1(Q) = C2(Q), for all Q != P, then
S(C1, P) = S(C2, P) (this expresses the fact that you can't see your own hat)
Given a strategy S we have a "guessed-right" subset G of {configurations} x {prisoners}, where (C,P) is in G whenever S(C,P) = C(P)
The size of G, for any strategy, is exactly half of |configurations|
|prisoners|, since when C1 and C2 only differ by prisoner P's hat, the constraint on strategies means that exactly one of (C1, P) and {C2, P) is in G. So we can divide the domain of S into pairs, each containing exactly one element of G.
Since we can't change the total number of correct guesses (summed over all configurations and all prisoners), the way to maximize the number of configurations with 51 or greater correct guesses would be to have winning configurations with as close as possible to 51 correct guesses, and losing configurations with as close to 100 incorrect guesses as possible.
Jim's solution does perfextly on the latter criterion; when the prisoners lose, every prisoner guesses wrong, which is perfect. But it does poorly on the first criterion; when there are 95 blue hats, for example, then 95, rather than 51, prisoners guess right, which is wasteful. If there were fewer prisoners who guessed right in these configurations, then there would be more correct guesses available for other configurations, allowing the possibility of fewer losing configurations.i
If the prisoner's strategy is symmetric, then the number of correct guesses with 5 blue hats is either 0, 5, 95, or 100, which is why I think Jim's is the best symmetric solution. But an asymmetric one, where only 51 prisoners answer correctly with (at least some) 95-5 configurations, will leave more correct guesses available for other configs, possibly allowing us to decrease the number of "all-fail" configs. So I'm not convinced that Jim's solution is optimal when we include asymmetric strategies. Asymmetric strategies can be very complicated; not only do different prisoners have different algorithms, put a prisoner's guesses may depend not only on the hat count, but on exactly which prisoners have blue hats.
I think I can prove that randomness doesn't help, that is, that the best nondeterministic strategy is no better than the best deterministic strategy. A nondeterministic strategy is map
S:{configurations} x {prisoners} x P -> {R, B}, where P has a measure on it with total measure 1. P is the set f all possible "die rolls", or whatever other randomization technique the prisoners employ. The "Can't see your own hat" restriction in this case is just that for each p in P, the map S restricted to p satisfies the above restriction.
Each element p in P has an associated set of success configurations (where 51 or more prisoners are correct). and the overall success probability of S is just the integral over P of the success probability of the strategy restricted to p. So the average value can never be greater than the maximum value, and there is some particular die roll we can choose in advance which does at least as well as the randomized strategy does overall.
Andy
On Mon, Jun 19, 2017 at 12:03 PM, James Davis < lorentztrans@gmail.com <javascript:;> <javascript:;>> wrote:
Me too. I was thinking that 51 answers that agree with the majority is enough, but we need 51 answers that are accurate to their own hat.
In a 51-49 split, the 51 folks who see 49-50 are those who would get the right answer under your strategy, but not necessarily the modified. The 49 folks who see the 51-49 split as 51-48 are *still* getting the wrong answer under the simple or modified strategy (Hence Dan's idea about switching). Since 51-49 or 49-51 is about twice as likely as 50-50, it seems tricky to make a rule that gives 50-50 a chance of success without dropping the success of 49-51 below 50%.
On Mon, Jun 19, 2017 at 10:56 AM, James Propp < jamespropp@gmail.com <javascript:;> <javascript:;>> wrote: > Why strike it? It convinced me! What's the fallacy? > > Jim > > On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com <javascript:;> <javascript:;>> wrote: > >> Oops, strike that first paragraph! I'm inclined to agree with Propp. >> >> On Mon, Jun 19, 2017 at 4:12 AM, James Davis < lorentztrans@gmail.com <javascript:;> <javascript:;> >> <javascript:;>> wrote: >> >> I believe that this is best possible, but I don't have even the >> beginnings >> >> of a proof. >> > >> > Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance >> > of success on a 50-50 split, and only decreases the failure on a 49-51 >> > overall split from 100% to ~100%, so I think the overall success is >> > around 96% as the problem suggests. >> > >> > It's interesting that the solution smacks of a (reverse) gambler's >> > fallacy. Even more, if the problem slightly favored one color, you >> > often put the prisoners in the paradoxical position of having to play >> > an individually losing/irrational strategy that somehow works en >> > masse. >> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com <javascript:;> <javascript:;> <javascript:;> >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com <javascript:;> <javascript:;> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com <javascript:;> <javascript:;>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
OK, for 100 prisoners there is a way to lose only 1/32 of the time. Start with the length-31 Hamming code. This code contains 1/32 of all the 31-bit strings, such that each 31-bit string is either a codeword or is a 1-bit change away from a codeword. This gives a solution to the majority-correct hats problem for 31 people: Everyone should firmly hold the belief that all the hat colors do not form a Hamming codeword. In the 1/32 case that it really is a codeword, everyone guesses wrong. The other 31/32 of the time, one person's guess is forced by the not-a-codeword logic and is correct, and the other 30 people would be happy guessing either way. We just need to make sure that the other 30 people's guesses are evenly split right vs wrong, and (as I mentioned last time), the "Eulerian cycle" point of view on the edges of the 31-cube shows that can be done. My Google colleague Piotr Zielinski pointed out that you can bootstrap that from 31 people to 62 people with the same winning probability: Tell the 62 people to partner up into 31 pairs, and then instead of guessing "my hat is red (blue)", each one guesses "my hat and my partner's hat colors are the same (opposite)". This lets 62 people play the hats game and only be wrong 1/32 of the time, and when they're right they win 32-30. It's easy to pad out from 62 people to 100 with the extra 38 people guessing half right and half wrong. The Eulerian cycle view tells us it's possible, but in this case it's easy to be explicit: pair these 38 people up as well, and half one person of each pair guess that their two hats are the same, and the other person guess they are different. In the 1/32 case, the guessers will now lose 81-19 (with zero Hamming guessers getting it right, and half of the 38 pad-to-100 guesses correct). The other 31/32 of the time, the guessers will win 51-49. Using Hamming code is kind of a cop-out, of course: all that stuff I said in my last post, about tying winners to losers at distance >1, isn't used at all. So I certainly expect that you can do better than this 1/32 = 3.125% loss rate, much closer to the 1/51 ~ 1.96% bound. --Michael On Thu, Jun 22, 2017 at 1:13 PM, James Propp <jamespropp@gmail.com> wrote:
Thanks for clearing up my confusion!
Jim
On Wednesday, June 21, 2017, Victor Miller <victorsmiller@gmail.com> wrote:
Jim, For such small n you can't get to .9. The strategy of guessing the color that the majority (that you can see) has, gives you 2^n - (2n) choose n. For n really large this is very good since 2n choose n is asymptotic (roughly) to 4^n/sqrt(n), which gets you to 90% when n=100, but nowhere near that when n is much smaller.
Victor
On Wed, Jun 21, 2017 at 5:44 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
I think I'm missing something. 853/1024 and 3497/4096 are both less than .9, so how is this an improvement?
Jim Propp
On Wednesday, June 21, 2017, Victor Miller <victorsmiller@gmail.com <javascript:;>> wrote:
You can definitely improve things by a different strategy. For very small examples -- 6, 8, 10 and 12 prisoners you can write an integer program to give you the best strategy. What I mean is the following -- prisoner i, has a function f_i of the assignment of hat colors that he can see -- i.e. a function {0,1}^{n-1} ---> {0,1} which tells him what color to guess. You have 2^{n-1}*n 0/1 integer variables for that function. You then have 2^n 0/1 variables which are 1, if the majority of the guesses are correct. The objective, to maximize, is the sum of all of those variables. A uniform strategy would make all of the functions the same. I found, that for n=6, 8, 10, 12 that the best uniform function was guessing along with the majority, and an arbitrary guess if there's a 50-50 split. However, in the non-uniform case you can do a lot better.
For n=6, you can get 48 out 64 assignments correct, as opposed to 44 For n=8, you can get 204 out of 256 assignments correct, as opposed to 186 For n=10, you can get 853 out of 1024 assignments correct, as opposed to 772 For n=12, you can get 3497 out of 4096 assignments correct, as opposed to 3172 (I don't know if 3497 is the best -- the program hasn't finished).
The computation for n=12 is taking quite a while, so I probably won't be going much further.
Victor
On Mon, Jun 19, 2017 at 8:04 PM, Michael Kleber < michael.kleber@gmail.com <javascript:;> <javascript:;>> wrote:
Yeah, Andy has the right point of view here. I think that the prisoners can guess majority-correctly around 98% of the time.
Think of the configuration space as the vertices and 1-dimensional edges of the 100-dimensional unit cube. A single vertex corresponds to one possible coloring of all prisoners' hats. Prisoner p gets to look at the other 99 hats, i.e. knows that the config is one of the two endpoints of one particular edge of the cube (an edge oriented parallel to the p'th basis vector).
Therefore a strategy for the prisoners corresponds to assigning an *orientation* to each edge of the cube: the arrow on the edge tells the prisoner to guess the hat color they would have in the configuration the arrow points to. We want to orient all the edges so that most vertices have 51 arrows pointing at them, and the rest have ~100 arrows pointing away.
If we didn't need to think about the connectivity of the cube, then of course this would be easy: for each group of fifty-one points, have one with 100 out-edges, and the other fifty with 51 in-edges and 49 out-edges. That would have the prisoners win 50/51 of the time.
With an actual 100-dim cube, we surely can't quite attain that upper bound; for example the number of vertices is 2^100, which is widely known to not be a multiple of 51. But I have some hand-wavy intuition that says we should be able to get pretty close to it.
Here's my plan. Pick a random 1/51 of the points to be the "losers" where we guess nearly all wrong. Now for each other point ("winner"), draw two paths connecting it to nearby losers. If it has two neighbors who are losers then this is really easy (and Bernoulli says that should be the case around 59% of the time). If you can't do this using just its immediate neighbors, then try to draw a path of length greater than 1 to a further-away loser, but don't use any already-used edges. Maybe this will be too hard with exactly ceiling(1/51) of the points being losers; those losers would need to end up with all 100 of their edges used by these paths. But if we increase the density of losers a bit, say from 1/51 = 1.96% to 2.5%, then on average each loser would only have around 80 of its 100 edges used by all the disjoint paths. It seems to me (hand-wavy!) that this is low-enough density that fitting all the paths in should be easy.
Once we have this collection of edge-disjoint paths, we can easily build a strategy from it. For each edge on the path from a loser to a winner, orient all the edges to point from the loser end towards the winner end. Each winner now has two in-edges because of the two paths we drew connecting it to losers, plus some matched set of in/out pairs of edges because of other paths which passed through it, leaving an even number of not-yet-oriented edges. We can orient all of the remaining edges via Eulerian paths through the graph: the only places where these remaining paths would start/end are at the maybe-odd-degree losers, and so on all the winners, they preserve the property of having two more in-edges than out-edges.
if we did go with 2.5% losers, then those vertices would each end up with around 10 people guessing correctly and 90 guessing wrong, while all the winners were 51-49 correct. The closer we can drive the loser density to 1/51, the closer the losers will get to all 100 people guessing incorrectly.
How close you can come to optimal seems like a weird coding-theory-ish sort of question, but the fact that you can use arbitrarily long paths to connect winners to losers (as long as they all remain edge-disjoint) makes the codes point of view taste funny.
--Michael
On Mon, Jun 19, 2017 at 1:07 PM, Andy Latto <andy.latto@pobox.com <javascript:;> <javascript:;>> wrote:
I think Jim's solution is the optimal symmetrical solution, where each prisoner uses the same algorithm, but there might be better asymmetric strategies.
A configuration C is a map C : {prisoners} -> {R, B} A guessing strategy is a map S:{configurations} x {prisoners} -> {R, B}, with the constraint that if
C1(Q) = C2(Q), for all Q != P, then
S(C1, P) = S(C2, P) (this expresses the fact that you can't see your own hat)
Given a strategy S we have a "guessed-right" subset G of {configurations} x {prisoners}, where (C,P) is in G whenever S(C,P) = C(P)
The size of G, for any strategy, is exactly half of |configurations|
|prisoners|, since when C1 and C2 only differ by prisoner P's hat, the constraint on strategies means that exactly one of (C1, P) and {C2, P) is in G. So we can divide the domain of S into pairs, each containing exactly one element of G.
Since we can't change the total number of correct guesses (summed over all configurations and all prisoners), the way to maximize the number of configurations with 51 or greater correct guesses would be to have winning configurations with as close as possible to 51 correct guesses, and losing configurations with as close to 100 incorrect guesses as possible.
Jim's solution does perfextly on the latter criterion; when the prisoners lose, every prisoner guesses wrong, which is perfect. But it does poorly on the first criterion; when there are 95 blue hats, for example, then 95, rather than 51, prisoners guess right, which is wasteful. If there were fewer prisoners who guessed right in these configurations, then there would be more correct guesses available for other configurations, allowing the possibility of fewer losing configurations.i
If the prisoner's strategy is symmetric, then the number of correct guesses with 5 blue hats is either 0, 5, 95, or 100, which is why I think Jim's is the best symmetric solution. But an asymmetric one, where only 51 prisoners answer correctly with (at least some) 95-5 configurations, will leave more correct guesses available for other configs, possibly allowing us to decrease the number of "all-fail" configs. So I'm not convinced that Jim's solution is optimal when we include asymmetric strategies. Asymmetric strategies can be very complicated; not only do different prisoners have different algorithms, put a prisoner's guesses may depend not only on the hat count, but on exactly which prisoners have blue hats.
I think I can prove that randomness doesn't help, that is, that the best nondeterministic strategy is no better than the best deterministic strategy. A nondeterministic strategy is map
S:{configurations} x {prisoners} x P -> {R, B}, where P has a measure on it with total measure 1. P is the set f all possible "die rolls", or whatever other randomization technique the prisoners employ. The "Can't see your own hat" restriction in this case is just that for each p in P, the map S restricted to p satisfies the above restriction.
Each element p in P has an associated set of success configurations (where 51 or more prisoners are correct). and the overall success probability of S is just the integral over P of the success probability of the strategy restricted to p. So the average value can never be greater than the maximum value, and there is some particular die roll we can choose in advance which does at least as well as the randomized strategy does overall.
Andy
On Mon, Jun 19, 2017 at 12:03 PM, James Davis < lorentztrans@gmail.com <javascript:;> <javascript:;>> wrote: > Me too. I was thinking that 51 answers that agree with the majority > is enough, but we need 51 answers that are accurate to their own hat. > > In a 51-49 split, the 51 folks who see 49-50 are those who would get > the right answer under your strategy, but not necessarily the > modified. The 49 folks who see the 51-49 split as 51-48 are *still* > getting the wrong answer under the simple or modified strategy (Hence > Dan's idea about switching). Since 51-49 or 49-51 is about twice as > likely as 50-50, it seems tricky to make a rule that gives 50-50 a > chance of success without dropping the success of 49-51 below 50%. > > On Mon, Jun 19, 2017 at 10:56 AM, James Propp < jamespropp@gmail.com <javascript:;> <javascript:;>> wrote: >> Why strike it? It convinced me! What's the fallacy? >> >> Jim >> >> On Monday, June 19, 2017, James Davis <lorentztrans@gmail.com <javascript:;> <javascript:;>> wrote: >> >>> Oops, strike that first paragraph! I'm inclined to agree with Propp. >>> >>> On Mon, Jun 19, 2017 at 4:12 AM, James Davis < lorentztrans@gmail.com <javascript:;> <javascript:;> >>> <javascript:;>> wrote: >>> >> I believe that this is best possible, but I don't have even the >>> beginnings >>> >> of a proof. >>> > >>> > Adding that a prisoner who sees 49-50 pick randomly gives ~46% chance >>> > of success on a 50-50 split, and only decreases the failure on a 49-51 >>> > overall split from 100% to ~100%, so I think the overall success is >>> > around 96% as the problem suggests. >>> > >>> > It's interesting that the solution smacks of a (reverse) gambler's >>> > fallacy. Even more, if the problem slightly favored one color, you >>> > often put the prisoners in the paradoxical position of having to play >>> > an individually losing/irrational strategy that somehow works en >>> > masse. >>> >>> _______________________________________________ >>> math-fun mailing list >>> math-fun@mailman.xmission.com <javascript:;> <javascript:;> <javascript:;> >>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math- fun >>> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com <javascript:;> <javascript:;> >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math- fun > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com <javascript:;> <javascript:;> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com <javascript:;> <javascript:;>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
On Mon, Jun 19, 2017 at 8:04 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Think of the configuration space as the vertices and 1-dimensional edges of the 100-dimensional unit cube. A single vertex corresponds to one possible coloring of all prisoners' hats. Prisoner p gets to look at the other 99 hats, i.e. knows that the config is one of the two endpoints of one particular edge of the cube (an edge oriented parallel to the p'th basis vector).
Therefore a strategy for the prisoners corresponds to assigning an *orientation* to each edge of the cube: the arrow on the edge tells the prisoner to guess the hat color they would have in the configuration the arrow points to. We want to orient all the edges so that most vertices have 51 arrows pointing at them, and the rest have ~100 arrows pointing away.
This is a really nice way to visualize the problem.
Here's my plan. Pick a random 1/51 of the points to be the "losers" where we guess nearly all wrong. Now for each other point ("winner"), draw two paths connecting it to nearby losers. If it has two neighbors who are losers then this is really easy (and Bernoulli says that should be the case around 59% of the time).
I'm missing some details of this calculation; is it that 59% will be adjacent to two losers, or to at least one loser? How did you calculate this? Anyway, my intuition is that finding the edge-disjoint paths from each winner to 2 losers should be pretty easy, because of how strongly connected the hypercube is. If you're looking for a path from A to B, and A and B differ in the bits in set S, then the shortest path is of length S, flipping one of the bits in S each time (like an easy word-ladder). This already gives us |S|! paths to try, so there are likely to be problems only near the beginning or the end, where there are only |S| choices for the first and last steps, |S|*|S-1| possible edges for the second and penultimate steps, and so forth. But if all the choices for the next bit to flip would travel over an already-used edge, there are many, many, only slightly longer alternatives. Instead of flipping bit X, flip bit Y, Y!= X, then flip bit X, then flip bit Y back again. There are a hundred length-3 paths to use if your length-1 path is unavailable, And if all hundred of these are unavailable, there are thousands of length-5 paths to try. In the same way that collisions between cars happen much more than collisions between planes, because there's "more room" in 3 dimensions than 2, it's very easy to "go around" an obstacle in 100-dimensional space. I know a lot of work has been done on random graphs. What percent of the edges do you have to remove from a hypercube graph before the rest of it becomes disconnected? This sounds like a relevant fact, and like the kind of question that random-graph theory has already answered. Andy
participants (5)
-
Andy Latto -
James Davis -
James Propp -
Michael Kleber -
Victor Miller