Counterintuitive Problem with HTH patterns

[TheCanadian]

Just came across this exercise in David Williams' book and thought it was worth sharing.

 

[haruspex]

View attachment 110343 View attachment 110344

Just came across this exercise in David Williams' book and thought it was worth sharing.

Yes, very interesting. I could not find an easy way to figure it out ... lots of little transition diagrams.
The hardest ones to beat are HTH and THT. In each case there is only one choice.
HHH and TTT do not beat anything.

 

[FactChecker]

Yes, very interesting. I could not find an easy way to figure it out ... lots of little transition diagrams.
The hardest ones to beat are HTH and THT. In each case there is only one choice.
HHH and TTT do not beat anything.

CORRECTION: THIS POST IS WRONG (see the next two posts)
This is talking about the first occurrence of those patterns in a long string, right? I think that as long as your last two letters match his first two and your first letter is different from your second (his first), you string has strictly better odds of occurring first. It doesn't matter what his last letter is.
If he picks HTH, you pick THT. If he picks THT, you pick HTH. You will have better odds. His first occurrence is matched in probability by your choice occurring just before his. ( T HTH gives you a win in the first case and H THT gives you a win in the second case. )

 

[haruspex]

This is talking about the first occurrence of those patterns in a long string, right? I think that as long as your last two letters match his first two and your first letter is different from your second (his first), you string has strictly better odds of occurring first. It doesn't matter what his last letter is.

No, that does not work. If she chooses HTH then your algorithm chooses THT, but by symmetry those are equal. To win you must choose HHT.

 

[FactChecker]

No, that does not work. If she chooses HTH then your algorithm chooses THT, but by symmetry those are equal. To win you must choose HHT.

CORRECTION: I am having second thoughts about this post (see edit below)
(I added some to my prior post.) Looking only at the first occurrence of his pick, 'HTH', your pick of 'THT' will have equal odds and will come before in the string 'T HTH'. They are not symmetric cases since you have guaranteed yourself a win in a small subset that he needed for a win.

EDIT: I see your point. It is symmetric, since his 'HTH' has the same advantage of coming before my first 'THT' in the string 'H THT'. So your solution is to copy the first two characters of his as your second and third and to make your first character different from his second character (your third char). That would make it asymmetric and give you an advantage.

 

[haruspex]

copy the first two characters of his as your second and third and to make your first character different from his second character (your third char)

Yes, that seems to work. Haven't figured out whether that gives the best advantage in each case.

 

[Zafa Pi]

View attachment 110343 View attachment 110344

Just came across this exercise in David Williams' book and thought it was worth sharing.

In fact I can choose one such that probability of my winning is 2/3, except in the cases where you selected HHH or TTT, then my chances are 7/8.
When I was a student back in the 50s I won my food money with this and the Monte Hall trick.
The cute part is that A beats B beats C beats D beats A. Winning isn't transitive.

 

[FactChecker]

CORRECTION: I am having second thoughts about this post (see edit below)
(I added some to my prior post.) Looking only at the first occurrence of his pick, 'HTH', your pick of 'THT' will have equal odds and will come before in the string 'T HTH'. They are not symmetric cases since you have guaranteed yourself a win in a small subset that he needed for a win.

EDIT: I see your point. It is symmetric, since his 'HTH' has the same advantage of coming before my first 'THT' in the string 'H THT'. So your solution is to copy the first two characters of his as your second and third and to make your first character different from his second character (your third char). That would make it asymmetric and give you an advantage.

EDIT2: This is wrong again. It can end up with your string being the same as his. I give up as far as stating a simple solution that works for all cases.

 

[Zafa Pi]

In fact I can choose one such that probability of my winning is 2/3, except in the cases where you selected HHH or TTT, then my chances are 7/8.

I can even do better. Let's list the 4 cases with more Ts than Hs in alphabetical order (the other cases are symmetric):
HTT is beat by HHT with probability 2/3.
THT is beat by TTH with probability 2/3.
TTH is beat by HTT with probability 3/4.
TTT is beat by HTT with probability 7/8.

The proof of the 1st case: Let p = the probability that HHT beats HTT. We must eventually start with H in either case.
If the next is H (probability 1/2) then HHT wins.
If the next is T (probability 1/2) then !/2 the time HHT loses and 1/2 the time we start over. So p = 1/2 + 1/2*(1/2*0 + 1/2*p), thus p = 2/3.

The 2nd case has the same argument. The 3rd and 4th cases are easier.

 

[haruspex]

EDIT2: This is wrong again. It can end up with your string being the same as his. I give up as far as stating a simple solution that works for all cases.

No, I think it works. Without loss of generality, he chose a sequence starting with H. Your rule gives:

His    Yours
HHH  THH
HHT  THH
HTH  HHT
HTT  HHT

Generalising to strings length N>2, let his choice be (c₁, .. , c_N). For convenience, abbreviate c₁, .. , c_N-1 to S.
So he chose (S, c_N). You choose (c₀, S), where c₀ is not c₂.
There are equal probabilities that the first N tosses will produce one of the two sequences. Otherwise, let your probability of winning be p.
To reach a decision, the sequence S has to arise. There is an evens chance it was preceded by c₀, making you the winner, and an evens chance that it will not be followed by c_N, giving you another chance. The rule for choosing c₀ prevents that argument working symmetrically.
This appears to give p = 1/2+p/4, so p = 2/3.
But here's the problem: If S is not followed by c_N in the throw sequence then we might nevertheless still be in a partial match with either chosen sequence. E.g. if his sequence is HTHH and the tosses produce HTHT, that last HT puts him back to a half-way match. Our sequence, HHTH, is doing even better, but is that generally true?

 

[FactChecker]

No, I think it works. Without loss of generality, he chose a sequence starting with H. Your rule gives:

His    Yours
HHH  THH
HHT  THH
HTH  HHT
HTT  HHT

Oh! Thanks! I got myself confused.