## Coin Flip Sequencing

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

### Coin Flip Sequencing

You are flipping a coin and looking for a certain sequence of heads and tails. For instance, if you were looking for tails-tails-tails, you would keep flipping until you got three tails in a row.

Now for the problem:
On average, does it take more flips of a (fair, unbiased) coin and get the sequence heads-tails-heads or heads-tails-tails or are they the same?

Tunga
Posts: 23
Joined: Tue Aug 19, 2008 10:30 am UTC
Contact:

### Re: Coin Flip Sequencing

Unless I am misunderstanding:
Spoiler:
50%.

There can be any sequence of H and T until "HT" comes up and these have no impact on the outcome. As soon as HT appears, the next will either be H or T.

Hence 50% HTH and 50% HTT.

This game is called Penney's Game and it is possible to gain an advantage by picking second.

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

### Re: Coin Flip Sequencing

Spoiler:
Actually, no. It isn't even, though you are correct that it bears strong similarity to Penney's game.

thomblake
Posts: 38
Joined: Mon Dec 15, 2008 7:24 pm UTC

### Re: Coin Flip Sequencing

Spoiler:
This may be too simple, but here goes:
trying for htt:
hthtt
trying for hth:
htthth

When trying for htt, getting the first two right and the last wrong requires only the sequence tt to win.

When trying for hth, getting the first two right and the last wrong requires the sequence hth to win.

(in all other cases they're equal)

So htt requires fewer flips on average.

lordatog
Posts: 84
Joined: Tue Feb 10, 2009 5:09 am UTC

### Re: Coin Flip Sequencing

Spoiler:
If you have one person flipping coins and stopping as soon as he hits either sequence, then the chance of either sequence being the first one hit is exactly 50%, for the reasons Tunga gave. If you have two different people flipping coins, one of them looking for HTH and one looking for HTT, then the one looking for HTT is more likely to hit his sequence first. If the HTH guy gets heads then tails in that order, then the next flip will either come up heads and complete the sequence, or come up tails and wreck it, forcing him to start over. If the HTT guy gets heads then tails in that order, then the next flip will either come up tails and complete the sequence, or come up heads - which does not force a complete restart, as it's the first step needed in the sequence.

Tunga
Posts: 23
Joined: Tue Aug 19, 2008 10:30 am UTC
Contact:

### Re: Coin Flip Sequencing

Yep that would be correct, I misunderstood the intention regarding two seperate coins.

levantis
Posts: 20
Joined: Thu Feb 05, 2009 1:42 pm UTC

### Re: Coin Flip Sequencing

I ran the actual test on A Million Random Digits, and, as I suspected (mwahahah),it`s 50% )
The flaw in the reasoning is that after a hth sequence, BOTH sequences are likely to be encountered sooner.

however, after experimenting with sequences and BIG files of random digits, i found out a strange thing
Here`s the code of a program that did it, in case any questions arise.

Code: Select all

`#!/usr/bin/pythonf=open('../all.txt','r')dict1={'0':0,'1':0}def gennew(old):   new={}   for i in old.keys():      new.setdefault(i+'0',0)      new.setdefault(i+'1',0)   return newdict2=gennew(dict1)dict3=gennew(dict2)dict4=gennew(dict3)s=f.read(4)for i in range(15099999):   dict4[s]+=1   s=s[1:]+f.read(1)for a,b in dict4.items():   print a,bf.close()`

bengeance
Posts: 9
Joined: Sun Jul 13, 2008 10:34 pm UTC
Location: School Medford/Somerville, break Worcester MA
Contact:

### Re: Coin Flip Sequencing

levantis wrote:I ran the actual test on A Million Random Digits, and, as I suspected (mwahahah),it`s 50% )
The flaw in the reasoning is that after a hth sequence, BOTH sequences are likely to be encountered sooner.

Spoiler:
No, thomblake's explanation is correct.

Suppose two people are flipping for hth and htt respectively.

It is intuitive that they will encounter ht equally early on average. Also, if they encounter ht, there is a 50% chance that they will finish their sequence on the next flip.

However, the 50% of the time when hth flips a tails, he will need to start his sequence over and flip hth.

Contrast this with htt, who after failing to get a htt after ht now has a hth, and only needs tt in order to complete his sequence.

http://www.ted.com/index.php/talks/pete ... uries.html
"Maturity is the ability to pretend you are not immature" - my grandfather