Author |
Topic: Coin triplets (Read 7641 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Coin triplets
« on: Oct 9th, 2002, 2:03pm » |
 Quote  Modify
|
Two players play the following game with a fair coin. Player 1 chooses (and announces) a triplet (HHH, HHT, HTH, HTT, THH, THT, TTH, or TTT) that might result from three successive tosses of the coin. Player 2 then chooses a different triplet. The players toss the coin until one of the two named triplets appears. The triplets may appear in any three consecutive tosses: (1st,2nd,3rd), (2nd,3rd,4th), and so on. The winner is the player whose triplet appears first.
With best play, who should win? Would the answer change if the choice of triplet were private?
Nick
|
| « Last Edit: Sep 20th, 2003, 9:01pm by Icarus » |
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #1 on: Oct 11th, 2002, 9:35pm » |
Quote Modify
|
I'm probably missing a neat approach to this one that justifies putting it in the "easy" section. I modeled the situation as a Markov process with 6 states: { HH, HT, TH, TT, 1Won, 2Won }. The first four are the states when neither player has yet won and the last two coins flipped are as shown. I then went into Gnu Octave and defined transition matrices for various possible selections by 1 and 2, and multiplied the vector after the first two flips [ 0.25, 0.25, 0.25, 0.25, 0, 0 ] by the matrix 100 times to get a good approximation of each player's winning probability.
I came up with the following answer, hidden by color: player 2 wins.
The best strategy I found was:
If 1 chooses HTT, choose HHT. 2 wins with probability 2/3.
If 1 chooses HTH, choose HHT. 2 wins with probability 2/3.
If 1 chooses HHT, choose THH. 2 wins with probability 3/4.
If 1 chooses HHH, choose THH. 2 wins with probability 7/8.
(You can swap H and T to fill in the rest of the table.)
I didn't search exhaustively, so this might not be best. I just applied the following intuition and tried a strategy that fits it:
2 wants the last two coins in his pattern to be the first two in 1's, because then he "steals" half the cases where 1 could win on the next round by winning first. Similarly, 2 wants the first two coins in his pattern not to be the last two coins in 1's.
Given this, it's clear that:
The game would be different if the two players chose in secret; it would remove player 2's advantage. Hmm, it looks like I need to draw up a game-theory payoff matrix to see what the right strategy is. I'll come back to that later.
Edit: corrected the typo pointed out by Icarus below. Thanks!
|
| « Last Edit: Oct 13th, 2002, 1:06am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #2 on: Oct 12th, 2002, 7:20pm » |
Quote Modify
|
It fits in the easy category because NickH doesn't ask for an optimal strategy, just one that will bias the results one way or another, and your intuition remarks are sufficient to figure out who can improve their odds without a full analysis. (Not that your results aren't interesting! I glad you did it because I am way too lazy to do something like that. Not to mention I never studied Markov chains.) By the way did you accidently reverse the choice for player 2 in the last strategy line? It's just opposite what your intuition lines would suggest!
As for the "private" game, it is symmetric with respect to the players, so any strategy used by one can also be used by the other. With best play, both players can expect only 50% of the victories.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #3 on: Oct 13th, 2002, 1:24am » |
Quote Modify
|
Icarus, thanks for noticing my error! I transcribed my notes wrong there.
You're right about the symmetry of the private version, of course. Finding the optimal strategy is still a bit interesting, I think -- I haven't worked on it yet.
I was way too lazy to do it with pencil and paper, or to think of a way to get the probabilities other than brute-force approximation. Doing the approximate calculation was pretty simple with Octave, even though I hadn't used it before. I just typed in stuff like:
v = [ 0.25 0.25 0.25 0.25 0 0 ]
d = [ 0 0.5 0 0 0.5 0 ; 0 0 0.5 0.5 0 0 ; 0 0.5 0 0 0 0.5 ; 0 0 0.5 0.5 0 0 ; 0 0 0 0 1 0 ; 0 0 0 0 0 1 ]
v * (d^100)
This analyzes the correct strategy for the case you noticed my typo on. Octave instantly printed:
ans=
0.00000 0.00000 0.00000 0.00000 0.12500 0.87500
The other cases didn't give quite this precise an answer after 100 iterations, but they were close. Here's another one:
a = [ 0.5 0 0 0 0 0.5 ; 0 0 0.5 0 0.5 0 ; 0.5 0.5 0 0 0 0 ; 0 0 0.5 0.5 0 0 ; 0 0 0 0 1 0 ; 0 0 0 0 0 1 ]
v * (a^100)
ans=
5.1296e-28 1.0058e-29 1.0058e-29 1.9722e-31 3.3333e-01 6.6667e-01
|
| « Last Edit: Oct 13th, 2002, 1:47am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #4 on: Oct 13th, 2002, 12:36pm » |
Quote Modify
|
I've worked out the optimal strategy for the private version. It was a bit tedious, since to fill out the payoff matrix I had to look at how every strategy does against every other, but not hard using Octave. Due to the many symmetries, there aren't really a lot of cases to consider, so although I should have written a loop, it seemed quicker to go through them by hand.
Then I realized I knew even less game theory than I thought I did, and I don't have a textbook on it at home, so I had to poke around the Web looking for a refresher. Pleasantly, there are a couple of Web sites that actually have applets on them where you can type in a small payoff matrix and have the applet solve the game for you! The applet converts the game to a linear programming problem and applies the simplex method.
Both the applets I tried say that an optimal strategy is for each player to randomly choose between HTT and THH with probabilities (0.4, 0.6). This seems not to make a lot of sense at first, as the strategies are completely symmetric, so there is no reason to prefer one over the other. What's actually happening here is that any strategy that randomly selects between HTT and THH, with 0.4 <= P(HTT) <= 0.6, is optimal. To spout some linear programming terminology that I'm only superficially familar with, the (0.4, 0.6) solution is found because the simplex method searches for an optimal solution that's a vertex of the feasible region -- loosely, it's at an extreme of the solution space.
By the way, filling out the whole payoff matrix shows that the solution I gave earlier for the version of the game where 1 announces his choice before 2 chooses is optimal and unique.
This was a fun problem. It motivated me to go back to several areas of math that I only know a little about, review, and learn a little more, and also to get started with Octave. At the same time it wasn't difficult.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #5 on: Oct 15th, 2002, 7:40pm » |
Quote Modify
|
It's been far too long since I've dealt with simplexes (and I never dealt with the "simplex method"), but I think I recall enough to follow that! And I agree it is interesting. Thanks, NickH, for a good problem, and thanks, TimMann, for sharing your results.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #6 on: Oct 16th, 2002, 5:50am » |
Quote Modify
|
Icarus,
I learned the simplex method in school, but I never learned about simplexes. Could it be that they're not related? The simplex method is just the fastest way that's been devised to maximize a linear combination of n variables, subject to a certain number of constraints. Example:
maximize a + 2b + d
subject to
a >= 0, b >= 0, c >= 0, d >= 0
b + c + 5d <= 8
a + 1/3c + d <= 6
(This is just an example--I don't know how it works out). I also don't remember enough of the method to tell you how to do it. However, think of the allowed solution space as a volume in n dimensions, with the constraints as the planes surrounding the volume (note that the volume is a "convex hull"  ).
Because the payoff function is a linear combination of variables, the maximum must be at a "corner", where three or more constraints intersect (like the corner of your living room).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #7 on: Oct 16th, 2002, 9:23am » |
Quote Modify
|
My understanding was that the simplex method is named that because the feasible solution set of a linear programming problem (the "volume" you mentioned) is a simplex in n-space. Isn't it? I never studied simplexes...
|
| « Last Edit: Oct 16th, 2002, 9:26am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
 |
Re: NEW PUZZLE: Coin triplets
« Reply #8 on: Oct 17th, 2002, 4:15pm » |
Quote Modify
|
I'm glad this problem was appreciated. I have some workings to post, when I get the chance...
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #9 on: Oct 19th, 2002, 5:29am » |
Quote Modify
|
The feedback on this puzzle has been fascinating!
Here is another way to calculate the probability of one triplet appearing before another. Take as an example HTT vs. HHT. The probability HTT appears first is the mean of that probability over the four possibilities for the first two coin tosses. Let, for example, p(HT) be the probability HTT appears first following HT. Then we have:
(1) p(HH) = p(HH)/2
(2) p(HT) = p(TH)/2 + 1/2
(3) p(TH) = p(HH)/2 + p(HT)/2
(4) p(TT) = p(TH)/2 + p(TT)/2
(1) => p(HH) = 0. (Following HH, we can avoid losing only by hoping for an infinite string of heads!)
(3) => p(TH) = p(HT)/2.
(2) => p(HT) = p(HT)/4 + 1/2 => p(HT) = 2/3.
(3) => p(TH) = 1/3.
(4) => p(TT) = p(TH) => p(TT) = 1/3.
The mean of these four results gives us a probability of HTT appearing before HHT of 1/3.
Here is the full table. I've taken the liberty of writing it in hex so that the columns (almost) line up! It confirms TimmMann's clever strategy.
2/1: HHH HHT HTH HTT THH THT TTH TTT
HHH
HHT 1/2
HTH 3/5 1/3
HTT 3/5 1/3 1/2
THH 7/8 3/4 1/2 1/2
THT 7/C 3/8 1/2 1/2 1/2
TTH 7/A 1/2 5/8 1/4 2/3 2/3
TTT 1/2 3/A 5/C 1/8 2/5 2/5 1/2
The table also suggests that choosing at random (p = 1/2) between HTT and THH is an optimal strategy. Intuitively, I expected p <> 1/2 to be suboptimal, so I'm very interested to see TimMann's result of optimality where |p - 1/2| <= 1/10. I shall look into this further...
Another question is: what is optimal play against a randomly chosen (p = 1/8 for each) triplet? Here again, HTT or THH is the optimal play, this time in any combination of frequencies. HTT shows an expected profit of almost 14% against a random triplet, HHT around 10%, HTH ~ 3% loss, with HHH showing ~ 21% loss.
I like the surprising non-transitivity. Example: HHT beats HTT beats TTH beats THH beats HHT.
How about generalizing to n-tuplets?
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #10 on: Oct 19th, 2002, 11:42am » |
Quote Modify
|
James: My math background was far more theoretical than calculational, which is why I know about symplexes but not the symplex method. A symplex is essentially the n-dimensional version of a triangle or tetrahedron (including the interior). They have a variety of applications in differential geometry where I met them. From what Tim said, I assume the symplex method works by finding the vertices of the symplex of all solutions. It's not hard to see that any linear function on a symplex must take on its max and min values at a vertex.
NickH: n-tuplets? Oy! It's clear that the same "steal his lead-in" strategy works for player 2, but I will leave a full analysis to you and Tim, who are obviously much better at it than I am. (I did come up with the stealing strategy on my own, but it never occured to me until I read it in Tim's message, that player 2 had better be careful not to leave player 1 stealing his lead-in!)
At least this is true for n >= 3. For n = 2, Player 1 can choose HT or TH, forcing Player 2 to choose the other just to keep the odds even.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #11 on: Oct 19th, 2002, 5:15pm » |
Quote Modify
|
NickH, glad you weighed in again. I was wondering what you had in mind.
I thought of the method you used too, but not until after I got started doing the problem by writing out the Markov transition matrices and multiplying, which is quicker if you have a matrix calculator handy.
I looked around the web later and found a site with a nice introduction to Markov processes, which I really know only a little about. See http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/Summary8.html
It turns out this is a standard type of Markov system, called an absorbing system. The states where 1 or 2 has won and you don't have to flip anymore are the absorbing states, and the standard problem is to find the probability of ending up in each absorbing state if you run the process for an unlimited time.
What I did of course only gives a good approximation that let us see what the right answer must be. Getting the exact answer turns out to be quite simple, though; the web page shows how. I think the calculations you did by hand (write down some linear equations and solve them) end up being essentially the same as the calculations that the standard solution does by writing down a matrix and inverting it.
Hmm, a few more things to think about. I'll probably post more later.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #12 on: Oct 19th, 2002, 6:06pm » |
Quote Modify
|
Oh, about the (.4, .6) strategy working. Let's write out the full table (with markup) to make it easier to see what's going on. Sorry about the big space above the table and the large font. It appears to be a YaBB bug.| 1 \ 2 | HHH | HHT | HTH | HTT | THH | THT | TTH | TTT | | HHH | 1/2 | 1/2 | 2/5 | 2/5 | 1/8 | 5/12 | 3/10 | 1/2 | | HHT | 1/2 | 1/2 | 2/3 | 2/3 | 1/4 | 5/8 | 1/2 | 7/10 | | HTH | 3/5 | 1/3 | 1/2 | 1/2 | 1/2 | 1/2 | 3/8 | 7/12 | | HTT | 3/5 | 1/3 | 1/2 | 1/2 | 1/2 | 1/2 | 3/4 | 7/8 | | THH | 7/8 | 3/4 | 1/2 | 1/2 | 1/2 | 1/2 | 1/3 | 3/5 | | THT | 7/12 | 3/8 | 1/2 | 1/2 | 1/2 | 1/2 | 1/3 | 3/5 | | TTH | 7/10 | 1/2 | 5/8 | 1/4 | 2/3 | 2/3 | 1/2 | 1/2 | | TTT | 1/2 | 3/10 | 5/12 | 1/8 | 2/5 | 2/5 | 1/2 | 1/2 |
Notice that HHT dominates HHH (HHT is always at least as good, no matter what the opponent does), TTH dominates TTT, HTT dominates HTH, and THH dominates THT. So we can ignore the HHH, TTT, HTH, and THT rows and columns, leaving us with a 4x4 payoff matrix.
I played around with some different numbers in the payoff matrix to get a feeling for why a (.4 HTT, .6 THH) strategy works. One way to put this is that you need to randomize somewhat evenly between HTT and THH to prevent your opponent from (say) noticing that you're biased in favor of HTT and mixing HHT into his strategy to defeat you. If your opponent chooses HHT, you win with probability 1/3 by choosing HTT or 3/4 by choosing THH. So if you're heavily biased toward HTT, you'll tend to do worse than your normal 1/2. But a light bias toward HTT is OK, because 1/3 + 3/4 > 1. At a .4:.6 bias, your probability of winning against HHT is still 1/2, so there's no benefit to your opponent in choosing it; in fact, since he doesn't know for sure you'll do a .4:.6 mix, he can't afford to mix HHT into his strategy at all.
|
| « Last Edit: Oct 19th, 2002, 6:33pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #13 on: Oct 21st, 2002, 3:13pm » |
Quote Modify
|
Tim, your answer is right, but I think your analysis of the payoff matrix isn't correct if you're taking this to be a game theory question.
In the world of game theory, which we seem to have entered, you have to assume that the opponent will know exactly which random strategy you're going to pick, though not an individual outcome.
Let's say you, as player 1, take the 40% HTT and 60% THH strategy. Against this strategy, player 2 could respond HTT or THH to guarantee 50% wins, so we'll try to do better with .
Say player 2 picks HHT with probability p, and TTH with probability 1-p. (ignoring the "uninteresting" responses HTT and THH). Then 2's expected gain is: (each term is prob(player 1 chooses here) * prob(player 2 chooses here) * (payoff to 2))
(2/5 * p * 2/3) + (2/5 * (1-p) * 1/4) + (3/5 * p * 1/4) + (3/5 * (1-p) * 2/3) = (6-p)/12.
Therefore player 2 maximizes his gain at p=0 (that is, only choosing TTH), for a 50% win.
If player 1 changes from 40/60 to 50/50 HTT/THH, player 2 can no longer afford the risk of trying for the occasional 2/3 point gain in TTH/HHT, so he must take the safety play of responding HTT/THH in order to guarantee himself 50%. If player 1 makes a distribution wider than 40/60 (such as 70/30), then player 2 has a good percentage play on TTH/HHT to gain himself more than 50%. I'll do the math for this one and then be done:
(7/10 * p * 2/3) + (7/10 * (1-p) * 1/4) + (3/10 * p * 1/4) + (3/10 * (1-p) * 2/3) = (9+4p)/24
Which is maximized at p=1, so player 2 can manage 13/24 win ratio this time.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #14 on: Oct 22nd, 2002, 12:13am » |
Quote Modify
|
Garzahd, you say that my analysis is wrong, but your analysis agrees completely with mine. Perhaps the post where I tried to give some intuition for why 40%/60% works was unclear, but rather than refuting it, you've just said the same thing over again, adding an example of how 30%/70% in particular doesn't work.
Any strategy in which you choose randomly between HTT and THH is optimal, as long as you set P(HTT) to be between 0.4 and 0.6. If you use this strategy, your opponent can't do better than 0.5 no matter what strategy he uses, and no matter whether he knows what strategy you are using. But if you use any other strategy, and your opponent knows you are doing so, he can do better than 0.5. As you said, that's the definition of a game-theoretic solution.
If you look back to the first post where I gave those numbers, you'll notice that I said I constructed the payoff matrix and solved it using the standard game theory technique. (I.e., translate the payoff matrix into a linear programming problem and solve it using any handy method, which in practice is always the simplex method.) I didn't do the linear programming bit by hand -- I used a web page that lets you type in the payoff matrix and solves the game for you -- but I'm confident the answer is correct. I actually found two different web sites with different implementations of a game theory solver, and both gave the same answer. And, as we've both noticed, the answer makes sense.
By the way, one of the applets I found (along with a nice refresher on game theory) is on another page at the same web site as the Markov process page that I pointed out above. See http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/Summary9.html
and http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/gametheory/game s.html.
|
| « Last Edit: Oct 22nd, 2002, 12:18am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #15 on: Oct 22nd, 2002, 5:21pm » |
Quote Modify
|
You were correct, but I didn't think your explanation was sufficient from a game-theory standpoint. Especially the comment "he doesn't know if you're going .4/.6" and "heavy bias / light bias" without explaining why 40/60 was the critical threshold.
I should have used the word "insufficient" rather than "incorrect" in my previous post.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: NEW PUZZLE: Coin triplets
« Reply #16 on: Oct 22nd, 2002, 10:03pm » |
Quote Modify
|
I wasn't trying to give a "sufficient explanation" (i.e., proof of correctness?) for the result, since it was correct by construction; just trying to give some insight into what property of the payoff matrix leads to the 0.4:0.6 values. I gather my post didn't make either its purpose or its content clear. Sigh.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print