[ExI] Amazement at sequence's expected appearance was Re: It's simply obvious, right?

[Alejandro Dubrovsky]

On Sun, 2007-11-25 at 14:15 -0800, Jef Allbright wrote:
> > > <http://www.ted.com/index.php/talks/view/id/67>

> The opening puzzle was only incidental to my interest.  Anyway, your
> response kindled a little more interest in me so I wrote my own
> program and did a little more experimenting.
> 
More programs but I promise I'll stop soon.  This one compares all
strings of length x.  Still wanting someone to point me to The Formula.
eg, length 5, run of 10 million tosses. 

Total for TTTTT: 160805 Average: 62.187121
Total for HHHHH: 161354 Average: 61.975532
Total for HTHTH: 237658 Average: 42.077271
Total for THTHT: 237917 Average: 42.031465
Total for TTHTT: 262838 Average: 38.046249
Total for HHTHH: 263012 Average: 38.021079
Total for HTTHT: 277783 Average: 35.999323
Total for THHTH: 278147 Average: 35.952212
Total for THTTH: 278162 Average: 35.950274
Total for HTHHT: 278202 Average: 35.945105
Total for HTHHH: 293976 Average: 34.016382
Total for HTTTH: 294031 Average: 34.010019
Total for THTTT: 294063 Average: 34.006318
Total for HHTTH: 294098 Average: 34.002271
Total for TTTHT: 294281 Average: 33.981127
Total for THHHT: 294298 Average: 33.979164
Total for HHHTH: 294330 Average: 33.975470
Total for HTTHH: 294630 Average: 33.940875
Total for TTHHT: 294787 Average: 33.922798
Total for THHTT: 294930 Average: 33.906351
Total for HHHTT: 311835 Average: 32.068241
Total for HHHHT: 311881 Average: 32.063511
Total for THHHH: 311881 Average: 32.063511
Total for TTHHH: 312098 Average: 32.041218
Total for TTTHH: 312553 Average: 31.994574
Total for HHTTT: 312868 Average: 31.962361
Total for HTTTT: 312869 Average: 31.962259
Total for TTTTH: 312869 Average: 31.962259
Total for THTHH: 312967 Average: 31.952251
Total for TTHTH: 312984 Average: 31.950515
Total for HHTHT: 313111 Average: 31.937556
Total for HTHTT: 313129 Average: 31.935720

#!/usr/bin/python
#Call as python whateveryoucallthescript.py <length> <number of tosses>
import os,  sys
import random

class Contender(object):
	def __init__(self,  sequence):
		self.sequence = sequence
		self.count = 0
		self.offer = ''

	def flip(self,  face):
		self.offer += face
		if self.offer[-len(self.sequence):] == self.sequence:
			self.count += 1
			self.offer = ''
		
def tosser():
	while True:
		yield random.choice(['H', 'T'])
		

		
def decimal2binary(n):
	b = ''
	while True:
		if n <= 0:
			break
		if (n % 2) == 0:
			b = '0' + b
		else:
			b = '1' + b
		n //= 2
		
	if b == '':
		b = '0'
	
	return b

def main(args):
	if len(args) <= 0:
		length = 2
	else:
		try:
			length = int(args[0])
			if length < 1:
				raise ValueError()
		except ValueError:
			print >> sys.stderr,  "Need a length parameter that is an integer
bigger than zero"
			sys.exit(1)

	if len(args) > 1:
		try:
			samples = int(args[1])
		except ValueError:
			print >> sys.stderr,  "Second parameter is the number of samples"
			sys.exit(1)
	else:
		samples = 100000
			
	upper = 2 ** length
	contenders = [Contender(decimal2binary(k).rjust(length,
'0').replace('0', 'H').replace('1', 'T')) for k in range(upper)]

	for c in contenders:
		print c.sequence
	
	for index,  face in enumerate(tosser()):
		if index > samples:
			break
		
		if (index % 10000) == 0:
			print index
	
		for c in contenders:
			c.flip(face)
	
	contenders.sort(key=lambda k: k.count)
	for c in contenders:
		print "Total for %s: %d\tAverage: %f" % (c.sequence,  c.count,
float(samples)/c.count)
	
if __name__ == '__main__':
	main(sys.argv[1:])