On Thu, Jun 28, 2018 at 6:52 AM, Telmo Menezes <[email protected]> wrote:
> On 28 June 2018 at 09:19, Telmo Menezes <[email protected]> wrote: > >> Here is one for you (and that list): > >> > >> Tomorrow you and another prisoner are to be executed. But you will both > be > >> spared if you can succeed in the following game. You and the other > prisoner > >> have tonight to decide on a strategy for playing this game: Tomorrow > you and > >> your fellow prisoner will be put in different rooms, and both of you > will > >> observe two completely independent and separate sequences of 100 coin > >> tosses. The goal is for each of you to choose a position in the other > >> person’s sequence of coin tosses such that the results of the coin > tosses in > >> those two selected positions match. (i.e., both heads or both tails). > What > >> is your strategy? > >> > >> Example: > >> Sequence: 1 2 3 4 5 6 7 8 9 ... 100 > >> You see: T H H T T H H H T ... T and choose position 3 in your > partner's > >> sequence > >> They see: H H T T H T T H T ... T and choose position 5 in your sequence > >> > >> You are both spared as you both chose matching results: both Tails. > > > > A naive strategy (e.g. both choose randomly) gives them a probability > > of survival of .5. Also, attaining a probability of 1 is impossible: > > if it comes all heads on one side and all tails on the other, there is > > not possible match. This limit is still pretty close to 1, as the > > probability of this happening is (2 x 2^100)^-1. So the best we can do > > actually 2 x 2^-100 > > > is improve the probability from .5. > > > > I found one improvement: > > > > Prisoner 1's strategy: > > If first head comes H, choose first position of the other sequence; > > If first head comes T, choose second position of the other sequence; > > "first head" -> "first toss" > > > > Prisoner 2's strategy: > > Always choose first position of the other sequence, unless first two > > tosses come T H. In this case choose the second position of the other > > sequence. > > > > From Prisoner 2's perspective, there are 4 options for the first two > tosses: > > > > T T -> doesn't matter what P1 chooses, probability of survival is .5 > > H H -> doesn't matter what P1 chooses, probability of survival is .5 > > H T -> match becomes guaranteed, probability of survival is 1 > > T H -> choosing the first position on the other side would guarantee > > defeat, but choosing the second gives a probability of survival of .5 > > > > So this improves the probability of survival to .625. > > > > I suspect it is possible to do better, by using more bits of > > information from player 1's sequence to determine the choice. Possibly > > some generalization of the strategy I proposed... > > Ok, here's a generalization. > > The first prisoner takes as many tosses from his side as possible to > index the other side. In this case he uses the first 6 tosses, mapping > to positions 1 to 64 on the other side. Player two can them inspect > his own sequence and consider the outcome for all possible choices in > {1 ... 64}. For each case he can assume a 6 toss configuration on the > other side. For each case he lists the choices on the other side that > lead to a guaranteed victory. In case there is not guaranteed victory, > he chooses 65 to keep to probability at .5 instead of guaranteeing > defeat, as per above. This is then used to compute the choice that > maximizes likelihood of match. > > Example with two bits. > > Prisoner 1 strategy: > HH -> choose position 1 on other side > HT -> choose position 2 on other side > TT -> choose position 3 on other side > TH -> choose position 4 on other side > > Prisioner 2 plying example: > > Let's say he got H T H H for the first 4 tosses. > > Position 1 (H) -> choosing {1, 2} guarantees match > Position 2 (T) -> choosing 2 guarantees match > Position 3 (H) -> choosing 3 keeps probability at .5 > Position 4 (H) -> choosing 2 guarantees match > > Choosing 2 maximizes likelihood of matching (p = .75). > > I don't feel like calculating the actual probabilities... Is this it? > > What I know is there is an extremely simple generalization of the first strategy you gave, only both players do the exact same thing. As you said the using the first 2 bits you get 0.625. Using them all gets you to ~2/3rds. This solution has a short, (about 5 english word) description and is as far as I got. There is a strategy though, which is more complex, but can achieve a 70% success rate. I don't recall how it works exactly, but if I remember correctly it only considers the first 3 bits, and can't be generalized for further improvement by considering more bits. Jason -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
