Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

B Counterintuitive Problem with HTH patterns

  1. Dec 12, 2016 #1
    Screen Shot 2016-12-12 at 9.50.47 PM.png Screen Shot 2016-12-12 at 9.50.55 PM.png

    Just came across this exercise in David Williams' book and thought it was worth sharing.
     
  2. jcsd
  3. Dec 13, 2016 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  4. Dec 13, 2016 #3

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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 occuring just before his. ( T HTH gives you a win in the first case and H THT gives you a win in the second case. )
     
    Last edited: Dec 14, 2016
  5. Dec 13, 2016 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  6. Dec 13, 2016 #5

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
    Last edited: Dec 13, 2016
  7. Dec 14, 2016 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, that seems to work. Haven't figured out whether that gives the best advantage in each case.
     
  8. Dec 14, 2016 #7

    Zafa Pi

    User Avatar
    Gold Member

    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.
     
  9. Dec 15, 2016 #8

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  10. Dec 15, 2016 #9

    Zafa Pi

    User Avatar
    Gold Member

    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.
     
  11. Dec 15, 2016 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

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

    His    Yours
    HHH  THH
    HHT  THH
    HTH  HHT
    HTT  HHT
     
    Generalising to strings length N>2, let his choice be (c1, .. , cN). For convenience, abbreviate c1, .. , cN-1 to S.
    So he chose (S, cN). You choose (c0, S), where c0 is not c2.
    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 c0, making you the winner, and an evens chance that it will not be followed by cN, giving you another chance. The rule for choosing c0 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 cN 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?
     
  12. Dec 16, 2016 #11

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Oh! Thanks! I got myself confused.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Counterintuitive Problem with HTH patterns
  1. Finding patterns (Replies: 0)

Loading...