Using python to analyse coin tossing statistics

Question

I have been learning python programming on edX which is a very good course and I can so far fully recommend. Having just watched a TED talk on Statistics I thought great, a simple way of exercising the python skills I have picked up on a real world scenario. The guy gave an example on probability of continually flipping a coin and looking out for two recurring sequences, which he explained, you would think had the same probability of happening which he claimed in fact don't. Put simply he claims the sequence Heads Tails Heads is more likely to occur than Heads Tails Tails as at the end of the first sequence you are are already one third towards repeating the sequence again where at the end of the second sequence you then have to toss a further head to begin the sequence again. This makes perfect sense, so I set about trying to prove it with my small python program shown here.

import random

HTH = 0
HTT = 0
myList = []
i = 0
numberOfTosses = 1000000

while i < numberOfTosses:
    myList.append(random.randint(0,1))
    i += 1

for i in range (len(myList)):

    if i+2 >= len(myList):
        break

    if myList[i] == 1 and myList[i+1] == 0 and myList[i+2] == 1:
        HTH +=1

    if myList[i] == 1 and myList[i+1] == 0 and myList[i+2] == 0:
        HTT +=1

print 'HTT :' ,numberOfTosses, HTT, numberOfTosses/HTT
print 'HTH :' ,numberOfTosses, HTH, numberOfTosses/HTH

So I have run the program many times and changed the max iteration value higher and higher, yet cannot seem to prove his claim that on average the HTH sequence should happen evey 8 tosses and the HTT sequence every 10, as it would seem that I get on average balanced results either way. So my question is where have I gone wrong in my implementation of the problem?

Answer 1

Your expert is right, and your code for what you stated he said is right, but he actually said something else. He says that when you start flipping coins, you should expect to see HTT first come up in an average of 8 flips, and HTH first come up in an average of 10 flips.

If you revise your program to test that assertion, it might look like this:

import random

HTH = 0
HTT = 0
numberOfTrials = 10000

for t in xrange( numberOfTrials ):
    myList = [ random.randint(0,1), random.randint(0,1), random.randint(0,1) ]
    flips = 3
    HTHflips = HTTflips = 0

    while HTHflips == 0 or HTTflips == 0:
        if HTHflips == 0 and myList[flips-3:flips] == [1,0,1]:
            HTHflips = flips
        if HTTflips == 0 and myList[flips-3:flips] == [1,0,0]:
            HTTflips = flips
        myList.append(random.randint(0,1))
        flips += 1

    HTH += HTHflips
    HTT += HTTflips


print 'HTT :', numberOfTrials, HTT, float(HTT)/numberOfTrials
print 'HTH :', numberOfTrials, HTH, float(HTH)/numberOfTrials

Running that will confirm the expected values of 8 and 10 tosses.

Answer 2

As for your code, this is functionally equivalent:

import random

HTH = 0
HTT = 0

numberOfTosses = 1000000

myList = [random.randint(0,1) for x in range(numberOfTosses)]

for i in range(len(myList)-2):
    a,b,c= myList[i:i+3]
    HTH += int(a==c==1 and b==0)
    HTT += int(a==1 and b==c==0)

print 'HTT :' ,numberOfTosses, HTT, numberOfTosses/float(HTT)
print 'HTH :' ,numberOfTosses, HTH, numberOfTosses/float(HTH)

As to why the two sequences appear the same number of times, my hunch is that they should. You may want to ask on stats.stackexchange.com

Answer 3

import random

HTH = 0
HTT = 0
myList = []
numberOfTosses = 1000000

myList.append(random.randint(0,1))
myList.append(random.randint(0,1))

for x in range (3, numberOfTosses + 3):
    myList.append(random.randint(0,1))
    if myList[x-3:x] == [1,0,1]:
        HTH += 1
    elif myList[x-3:x] == [1,0,0]:
        HTT += 1

print (HTH, " ", HTT)

Answer 4

Your code confirms that the probability of either string occurring is equal when you select 3 consecutive samples from a long sequence.

Actually for any given chain the probability of three samples matching it is always 1/ 2^[length of chain] - the only variable is the length, not the contents.

The TED talk you described sounds like a description of Penney's Game:http://en.wikipedia.org/wiki/Penney%27s_game But a key difference here is that Penney's game describes the likelihood of either sequence occurring FIRST (so a given player can win) - not the total occurrences overall - which your code finds. Also possible the TED speaker got the 2nd sequence backwards (HHT, not HTT.)

The code below tests ( and confirms) the statistical anomaly in Penney's game. Notice it 'breaks' or exits the inner loop on discovery.

It outputs: HTH : 1000000 332854 3 3.00432021247 HHT : 1000000 667146 1 1.49892227488

import random

HTH = 0
HHT = 0
myList = []
i = 0

numberOfTests = 1000000
maxTosses = 10000

hthConditionMeant=0
hhtConditionMeant=0

while i < numberOfTests  :
    myList = []
    j = 0
    while (j < maxTosses):
        myList.append(random.randint(0,1))
        if myList[j-3:j] == [1,0,1]:
                HTH += 1
                break
        elif myList[j-3:j] == [1,1,0]:
                HHT += 1
                break
        j += 1
    i += 1


cyclesToSeeHTHprecise =  numberOfTests / float(HTH)
cyclesToSeeHHTprecise =  numberOfTests / float(HHT)

print 'HTH :' ,numberOfTests, HTH, numberOfTests/HTH, cyclesToSeeHTHprecise
print 'HHT :' ,numberOfTests, HHT, numberOfTests/HHT, cyclesToSeeHHTprecise`

`

Answer 5

I think your expert is wrong, or you misunderstood what he was saying. I don't see anything wrong with your code for detecting HTH and HTT sequences.

For small numbers of rolls it's possible to work through every possible outcome rather than using random numbers.

For 3 rolls it's easy to reason that there are 8 possible outcomes, and exactly one of those will be HTH and one other will be HTT.

For 4 rolls there are 16 possible outcomes. 2 of them will start with HTH and 2 will start with HTT; likewise 2 will end with HTH and 2 will end with HTT.

I've modified your code to go through all the combinations and count the number of times the sequence is detected. In all the cases I tested the two counts are equal. http://ideone.com/YtixtV

from __future__ import division
import random

def every_combination(n):
    bits = [2**i for i in range(n)]
    for value in xrange(2**n):
        yield [1 if value & bits[i] else 0 for i in range(n)]

for n in range(3, 16):
    HTH = 0
    HTT = 0
    numberOfTosses = 0

    for myList in every_combination(n):

        numberOfTosses += len(myList)
        for i in range (len(myList) - 2):

            if myList[i] == 1 and myList[i+1] == 0 and myList[i+2] == 1:
                HTH +=1

            if myList[i] == 1 and myList[i+1] == 0 and myList[i+2] == 0:
                HTT +=1

    print 'For number of rolls', n
    print 'HTT :' ,numberOfTosses, HTT, numberOfTosses/HTT
    print 'HTH :' ,numberOfTosses, HTH, numberOfTosses/HTH