Coin Toss Oddity | Python Fiddle

#!/usr/bin/env python
"""
cointoss.py: Brute force demo of a counter-intuitive probability
result as descibed in:

https://www.quantamagazine.org/mathematicians-discover-prime-conspiracy-20160313

"If Alice tosses a coin until she sees a head followed by a tail,
   and Bob tosses a coin until he sees two heads in a row, then on
   average, Alice will require four tosses while Bob will require six
   tosses (try this at home!), even though head-tail and head-head
   have an equal chance of appearing after two coin tosses."

"""

def toss(n,s):
  """toss is a helper function

It takes a number and a string. It converts the least significant
  bit of the number to a character. If the bit is 1 toss turns it into
  an 'h' adn if it is a 0 toss turns it into a 't' -- the result is
  prepended to the string.

Args:
    n (int): An integer representation of a series of coin tosses
    s (string): A string representation of a series of coin tosses.

Returns:
    (tuple): tuple containing:

m(int): n shifted right such that the least significant bit is removed
      r(string): s with either 'h' or 't' prepended to it.

"""
  r = s
  lsb = n & 1

if lsb: # The least significant bit was a 1
    r = 'h' + r
  else: # The least significant bit was a 0
    r = 't' + r

return (n>>1, r)

def tosses(n,count):
  """tosses changes the representation of a coin toss from a number to a string

It takes the least significant count bits of the number and turns
  it into a series of 'h's and 't's. For example the number 2 would
  be 000010 in binary, and would be turned into the string "ttttht".

Args:
    n (int): An integer representation of a series of coin tosses
    count (int): The number of tosses

Returns:
    (string):  A count character representation of coin tosses
  """

m = n
  s = ''

for _ in xrange(count): # Do the following count times
    (m, s) = toss(m,s) # Iteratively convert the bits to a string

return s

def getit(trial, goal, acc):
  """getit is a helper function

It takes two strings, and an accumulator array of integers. If the
  second string occurs in the first then the element corresponding
  to the match position in the string in the integer array is
  incremented and the resulting array is returned otherwise the
  original array is returned.

Args:
    trial (string): A string to be searched
    goal (string): A string for which to search
    acc (list): A list of integers holding counts

Returns:
    (list):  A list of integers holding counts
  """
  try:
    ck = trial.index(goal)
    racc = acc
    racc[ck] = racc[ck] + 1
    return racc
  except ValueError: # goal does not occur in trial
    return acc
def flip(s):
  """flip inverts a sequence of coin tosses

It takes a string representation of a sequence of coin tosses and
  returns a sequence where each toss result is the reverse of the
  input e.g. 'htt' => 'thh'

Args:
    s(string): The input sequence

Returns:
    (string): The inverse of the input sequence
  """

mapping = { 'h': 't', 't': 'h' }
  r=''.join([mapping[c] for c in s])
  return r

def getitwithflip(trial,goal,acc):
  """getitwithflip is a helper function

It is the same as getit except that it also checks the flip of goal.

Args:
    trial (string): A string to be searched
    goal (string): A string for which to search
    acc (list): A list of integers holding counts

Returns:
    (list):  A list of integers holding counts
  """
  racc = acc
  ck1 = None
  ck2 = None

try:
    ck1 = trial.index(goal)
  except ValueError: # goal does not occur in trial
    pass

try:
    ck2 = trial.index(flip(goal))
  except ValueError: # the inverse of goal does not occur in trial
    pass

if ck1 is None:
    if ck2 is None: # Neither the goal nor its inverse was found
      return acc
    else:
      racc[ck2] = racc[ck2] + 1
  else:
    if ck2 is None: # Only goal was found
      racc[ck1] = racc[ck1] + 1
    else: # Both the goal and its inverse were found
      if ck1 < ck2: # If goal was found earlier count that
        racc[ck1] = racc[ck1] + 1
      else: # otherwise count the the inverse
        racc[ck2] = racc[ck2] + 1

return racc

if __name__ == '__main__':
  # There are 2**6 (two the sixth power, or 64) possible outcomes
  # of a number of coin tosses
  times = 6
  #times = 5
  osize = 2**times

# First, compute every possible sequence of six coin tosses
  bruteforce = [tosses(x,times) for x in xrange(osize)]
  #bruteforce = ['h' + tosses(x,times) for x in xrange(osize)]
  #bruteforce = ['t' + tosses(x,times) for x in xrange(osize)]

# This is the accumulator dictionary
  accs = { 'hh': [0,0,0,0,0], 'ht': [0,0,0,0,0] }

# Go through every possible coin toss result
  for trial in bruteforce:
    # For each of the targets
    for target in accs:
      # Find the first occurence of the target in the trial and
      # increment the accumulator accordingly
      accs[target] = getit(trial,target,accs[target])
      #accs[target] = getitwithflip(trial,target,accs[target]) # Check inverses as well

# Let's print the counts for each target
  print('COUNTS')
  for target in accs:
    print('\ntarget: ' + target)
    for count in xrange(len(accs[target])):
      print('\twill hit on {:d} coin flips in {:2d} of all {:d} possible flips.'.format(count+len(target),accs[target][count],osize))

# Let's convert the accumulators to probabolities in the range [0.0-1.0]
  for target in accs:
    accs[target] = [100.0*x/osize for x in accs[target]] # converts from int to float

# Let's print the percentages for each target
  print('\nPERCENTS')
  for target in accs:
    print('\ntarget: ' + target)
    for count in xrange(len(accs[target])):
      print('\twill hit on {:d} coin flips in {:7.4f} percent of all {:d} possible flips.'.format(count+len(target),accs[target][count],osize))

# Let's convert the accumulators to *cumulative* probabilities
  # which is the chance that the target will hit by (rather than
  # exactly on) given number of coin flips
  # XXX THIS IS WRONG, misses cases like 'hhh' and 'htht' where the target occurs multiple times in one sequence XXX 
  # XXX Nope. It's correct since the counts are for FIRST occurence. I need to go to sleep. XXX
  for target in accs:
    for x in range(1,len(accs[target])):
      accs[target][x] = accs[target][x-1] + accs[target][x]

# Let's print the percentages for each target
  print('\nCUMULATIVE PERCENTS')
  for target in accs:
    print('\ntarget: ' + target)
    for count in xrange(len(accs[target])):
      print('\twill hit by {:d} coin flips in {:7.4f} percent of all {:d} possible flips.'.format(count+len(target),accs[target][count],osize))

# And for a quick (text) visual comparison
  print('\nONE-LINE CUMULATIVE PERCENTS')
  for target in accs:
    fstring = '{}: '+ ' '.join(['{:7.4f}'] * len(accs[target]))
    fargs = tuple([target] + accs[target])
    print(fstring.format(*fargs))

Python Fiddle

Python Cloud IDE