Game Theory problem i remembered

[DrSavage]

Here's an interesting game i stumbled upon awhile ago.
Let's say dealer is throwing coins and whenever tails come up he writes 0 on a piece of paper and whenever heads come up he writes 1. So after , say, 5 flips of tails tails heads tails heads he would have 00101 written.
Now we have two players. First player chooses any combination of 3 0s and 1s , such as 000. Second player then knowing first player's choice chooses a combination for himself, such as 101.
Then the game starts and whoever's combination comes up first on dealer's list wins the bet. In the above situation second player wins since his combination came up first. Game restarts after that.
Questions:
1) Are there combinations you can pick which are better than others?
2) Who has the advantage , first player or second player?
3) What would be the combination choosing strategy for whoever has the advantage ?

I'll post an answer in a couple of days.

[Copernicus]

It seems too obvious so there must be a trick that I'll try to come up with later, but off the top of my head:

1) since the flips are random, there should be no sequence any more likely than another.

2) and 3) if its an infinite game neither player should have the advantage and no method of choosing a sequence would be preferred

however if its a finite game, either a freezout or there is limited capital, then 2d player has the advantage using a strategy of mimicking first player's picks. It doesnt change his expectation, but lowers his variance to 0, and is therefore less likely to go broke.

If they alternate going first and second, I suppose there is a marginal advantage to being second first, the extent of that advantage depending on the original stacks.

[DrSavage]

Well, to make it easier for people i'll answer to the 1st question right now.
Combinations are NOT all the same. For instance it's easy to see that 000 is a HUGE dog to 100. The only way it can win if 000 comes on first 3 flops, otherwise (if at least one 1 came up) 100 will always win since before 3 sequential 0 come up 2 sequential 0 will come up one step before. Therefore a probability of 000 beating 100 is 12.5%.

[Copernicus]

Just so your update doesnt totally throw off those who think before they write:

With a random picking strategy, 000 can win even when it is not one of the first three flips. Eg if the sequence is 01000101, 000 can still win as long as neither player has picked 010 or 100. Thus the correct strategy must be non-random and designed to take advantage of a non-random method of selecting sequences (since as we saw in a lengthy probability post a while back, sequences drawn in this way (pick 3, if not a hit, drop 1 from the front add one to the back) are not random.

[StevieG]

Suppose player #1 takes sequence ABC

If you go second and take XAB such that XAB != ABC (so if C==B and B==A then X = !A, otherwise X can be anything) then you have effectively lengthened their winning sequence to (!X)ABC while your XAB sequence is still a winner.

[Louie Landale]

If you pick 000 and are wrong its because you encountered a "1". When you do encounter a "1" then you gain no residual benefit of earlier patterns and you need to start againt starting from the next number. I didn't say that well, but perhaps an example helps:

You pick 000 and the sequence is 011... When you reach the 2nd flip (1) your match fails, and you need to start again from the 3rd flip trying to match your 1st choice.

You pick 010 and the sequence is 001... When you reach the 2nd flip (0) your match fails, but notice that by failing you automatically match your first choice, so your sequence matching starts over on the 2nd flip and NOT the 3rd flip as in the previous example. Thus this pattern improves your chances since there are MORE sequences you can match.

That's about as far as I can go ... but that's never stopped me before... I speculate: The best patterns are 011 and 100 since a fail on the 2nd or 3rd will automatically match your first choice. Since there are two equally "good" patterns then I'm sure that IF there is an advantage to either player than it must be to the player who chooses 2nd since at worst he can just pick the other sequence. Having said that, I am also confident that there IS a "best" strategy for this 2nd player although I don't know what it is.

Great quiz.

- Louie

What good is it? Perhaps if you are trying to snag a reasonable bluffer you should presume he bluffs alternately rather than randomly?

[George Rice]

Yes, there are numbers which are better than others. Specifically, the first player should pick a number that has the the first and third digits different. Specifically, he should pick 001, 011, 100, or 110. This is so because in any given sequence, this reduces the liklihood of your sequence appearing more than once, thus spreading your winners around. For example, six flips of a coin will yield 64 possible sequences. Any 3 digit number will appear exactly 32 times. However 000 will appear 4 times in the sequence 000000, 3 times in 000001 and 100000, twice in 000010, 000011, 100001 and 110000. 000 will appear in only 20 sequences. Whereas, a number like 110 is duplicated only once ( in 110110), and will appear in 31 sequences.

Yes, the second player has the advantage because he can pick a sequence that will win just as often, but will occur earlier in many of the sequences than the first players. He will do this by using some of the first players sequence.

The strategy for the second player is to pick a number where his last two digits are the first player's first two digits. The first digit will be the opposite of the last digit. So, here are the second players picks for each of the first players optimal picks:

First Second
______________

001 100
011 001
100 110
110 011

[DrSavage]

The answer to this problem is both entertaining and counterintuitive. I was glad to see that all posters came very close to solving it and were on the right track. But, the correct answer is as follows:
Second player has a big edge in this game. The reason being that for ANY combination a first player can choose second player can choose a combination which will be a strong favorite. This causes a strange loop, such as 100 beats 001 , 001 beats 011, 011 beats 110 and 110 beats 100 again.
Below is the table with correct strategy for second player. First column is a combination first player chose, second column is a correct choice for second player and 3rd column is a probability of second player winning. These numbers are easy to confirm with a computer simulation:

000 100 87.5%
001 100 75.0%
010 001 66.6%
011 001 66.6%
100 110 66.6%
101 110 66.6%
110 011 75.0%
111 011 87.5%

So there you have it. It's important to understand that these are HEADS UP probabilities. If we had 8 players and each one would choose a different combination probability of every one of them winning would be 12.5%. In heads up, you only need to choose your combination in such a way that it would be hard for your opponent to get his first. If you look closely at the table, each combination 2nd player chooses has last two digits the same as first two digits in first player's and the first digit is chosen in such a way that opposite wouldn't be true.
Anyhow, although it has no relation to poker whatsoever, I wish you luck tricking your friend and relatives to play this game against you. Just tell them "I will give you first choice, so you don't think i'm always picking the best combination there is".

[Copernicus]

How easy things are once you know the answer!

If you want to see why these strategies work at those rates, you just have to "backward propogate" (drop the last digit and put a 1 and alternatively a 0 before the first two digits) the predecessors to the first players choice. We also assume that we are propogating back from the first appearance of the first players choice. We are then concerned with how many of the backward branches pass through the second player's choice.

The first two cases are straightforward. 000 propagated back one digit was generated either by 000 or 100, but we've already assumed that the top level 000 was the first 000, ie the 000>000 branch cannot exist. Thus the only way 000 wins is if there are NO branches (ie just a point, 000, which occurs only when 000 is first...1/8 of the time). The remaining 7/8 of the time that 000 appears it is spawned from 100.

001 backward propogates to 100 and 000, but weve already seen that 100 dominates 000, so the only way 001 beats 100 is if it is first (1/8) or 000 is first (another 1/8).

For the inverses of these (111 and 110) just use the inverse strategy and the same winning % result.

For the rest you need to look at several levels of propogation. For the 010 case it was preceded in one branch immediately by 001, the second players choice. The second branch is 101, which sprouts two branches, 101>110 and 101>010. However the 101>010 branch doesnt exist because we've already assumed the first level 010 was the first appearance. The 101>110 branch then leads to a 101>110>011 branch which inevitably hits 001 or non-existant branches, and 101>110 leads to 101>110>111 which interestingly leads either to non-existant branches or branches that loop around to 111, never getting to 001. Therefore there are only 3 viable branches, 2 of which can lead to 001 and 1 which never gets to 001, so 001 is the winner 2/3 of the time.

the others im sure will have similar non-existant paths that lead to only 3 viable paths, 2 of which lead back to the winning choice.

[George Rice]

Just "backward proporgate" and make your first digit the opposite of your last one!

[BruceZ]

1) since the flips are random, there should be no sequence any more likely than another.

No sequence is any more likely than another starting on any given flip; however, it can be shown that 000 and 111 occur less frequently in a long sequence of flips than other sequences, and they will on average take longer to occur for the first time. This counterintuitive result comes from renewal theory. The only proof I know of this is somewhat advanced and involves Laplace tranforms. Refer to Feller p. 328 "...contrary to expectation, there is an essential difference in coin tossing between head runs and other patterns of the same length". There are formulas for computing the mean recursion time for all sequences given. You can see why this would be true. For the sequence 000, a 1 causes us to start over, but if we have 101 and get 11, we are still waiting for the second 0 no matter how many 1's we get. So we have more opportunities for success with this pattern. Another way to say this is that the trials of runs are not independent.

[BruceZ]

If we had 8 players and each one would choose a different combination probability of every one of them winning would be 12.5%.

That is true because someone has to win on the first 3 flips, and all sequences are equally likely. Otherwise, 000 and 111 occur less frequently in a long string of flips, and they take longer to occur for the first time than any other sequences on average. This is why, as you can see from your data, that it is never correct to choose these sequences heads-up. See my above post.