see https://github.com/joshua-benjamin-miller/penneysgame for .ipynb and .py files.
This interactive notebook explores an algorithm that solves a generalized version of Penney's pattern-matching game for a q-sided die ($q\geq 3$), with potentially unequal probabilities.
The solution implements a generalized version of Conway's leading number algorithm , and cross-validates it via simulation.
References
Journal of Combinatorial Theory, Series A 30(2), 183--208. PDF Download 2.
import time
import os #for benchmarking
import numpy as np
#in case we need to update user-defined code e.g. importlib.reload(diffP)
import importlib
current_dir=os.getcwd()
print(current_dir)
for file in os.listdir(current_dir):
if file[-3:]=='.py':
print(file)
C:\Users\Miller\Dropbox\josh\work\projects\Patterns\python conway.py
import conway #The programs live here
importlib.reload(conway)
#help(conway)
print('Locked and loaded')
Locked and loaded
note: In the speccial case of a fair coin flip, this is $2\times \text{Conway Leading Number}$
Conway leading number is an (asymmetric) measure of overlap between two patterns A and B.
AB measures how the leading numbers of B overlap with the trailing numbers of A, as B is shifted to the right (assuming B is not a subpattern of A)
Here is the function:
help(conway.payoff_to_B_bettors_if_A_occurs_first)
Help on function payoff_to_B_bettors_if_A_occurs_first in module conway: payoff_to_B_bettors_if_A_occurs_first(A, B, alphabet) (string, string, dictionary)-> (float) Calculates the fair payoff to those betting on characters according to pattern B, if pattern A occurs first. For example: >>>A='THH' >>>B='HHH' >>>alphabet={'T':.5, 'H':.5}) >>>AB=payoff_to_B_bettors_if_A_occurs_first(A,B,alphabet) Then in this case AB=4+2=6 as B betters who come in at T-1 win twice, and those that come in at T win once.
If A=THH comes first, how much does a player who, on each trial, initiates a asequence of bets on characters according to B=HHH, get paid?
The players that arrive at time T-1 and time T walk out with $4 and $2 respectively, for a total of $6
distribution={'H':.5, 'T':.5}
A = "THH"
B = "HHH"
print(conway.payoff_to_B_bets_if_A_occurs_first(A, B, distribution))
6.0
Here is the function:
help(conway.oddsAB)
Help on function oddsAB in module conway: oddsAB(A, B, alphabet) (string, string, dictionary)-> [list] returns odds against pattern A preceding pattern B odds[0] = "chances against A" odds[1] = "chances in favor of A" note: odds= 2* Conway's odds; see Miller (2019) for proof
What are the odds that that pattern A=HTH precedes pattern B=TTH?
In the case that A occurs before B, i.e we compare the trailing characters of $A\cdot$
In the case that B occurs before A, i.e we compare the trailing characters of $B\cdot$
so odds against $A$ occuring before $B$ are ${AA-AB}:{BB-BA} = 10:6$, or $5:3$
this translates to a probability that $A$ occurs first equal to $3/8$
Let's check this below:
distribution={'H':.5, 'T':.5}
A = "HTH"
B = "TTH"
print('odds against A = [chances against, chances in favor] = ',conway.oddsAB(A, B, distribution))
print('probability A occurs before B = ', conway.probAB(A, B, distribution))
odds against A = [chances against, chances in favor] = [10.0, 6.0] probability A occurs before B = 0.375
Let's create the table, the probability the row pattern comes before the column pattern, and cross-validate with table from Gardner
from fractions import Fraction
pH = .5
pT = 1-pH
distribution={'H':pH, 'T':pT}
k = 3
#initialize the globals within the module
conway.list_pattern=['-']*k
conway.patterns = []
#build the patterns
help(conway.all_patterns)
conway.all_patterns(k,distribution)
patterns = conway.patterns
print("all patterns of length",k,"= ",patterns)
row = 0
print("-" * 70)
print("", end='\t')
print(*patterns, sep='\t')
while row < 8:
col = 0
print(patterns[row],end='\t')
while col <= 7:
r='\t'
if col ==7:
r='\n'
if patterns[row]==patterns[col]:
print('', end=r)
else:
o=conway.oddsAB(patterns[row],patterns[col], distribution)
F = Fraction(int(o[1]),int(o[0]+o[1]))
N = F.numerator
D = F.denominator
print(N,"/",D,end=r)
col += 1
row += 1
print("-" * 70)
Help on function all_patterns in module conway: all_patterns(j, alphabet) recusively builds all patterns of length j from alphabet note: before calling must initialize following two lists: >>>k=3 >>>list_pattern=['-']*k >>>patterns = [] all patterns of length 3 = ['HHH', 'HHT', 'HTH', 'HTT', 'THH', 'THT', 'TTH', 'TTT'] ---------------------------------------------------------------------- HHH HHT HTH HTT THH THT TTH TTT HHH 1 / 2 2 / 5 2 / 5 1 / 8 5 / 12 3 / 10 1 / 2 HHT 1 / 2 2 / 3 2 / 3 1 / 4 5 / 8 1 / 2 7 / 10 HTH 3 / 5 1 / 3 1 / 2 1 / 2 1 / 2 3 / 8 7 / 12 HTT 3 / 5 1 / 3 1 / 2 1 / 2 1 / 2 3 / 4 7 / 8 THH 7 / 8 3 / 4 1 / 2 1 / 2 1 / 2 1 / 3 3 / 5 THT 7 / 12 3 / 8 1 / 2 1 / 2 1 / 2 1 / 3 3 / 5 TTH 7 / 10 1 / 2 5 / 8 1 / 4 2 / 3 2 / 3 1 / 2 TTT 1 / 2 3 / 10 5 / 12 1 / 8 2 / 5 2 / 5 1 / 2 ----------------------------------------------------------------------
Gardner's table (they match):
here is the simulation function:
help(conway.simulate_winrates_penney_game)
Help on function simulate_winrates_penney_game in module conway: simulate_winrates_penney_game(A, B, alphabet, number_of_trials) (string, string, dictionary, integer)-> (list) Play generalized Penney's game and calculate how often pattern A precedes pattern B, and vice versa
Cross-validate the simple case
distribution={'H':.5, 'T':.5}
A = "HTH"
B = "TTH"
p = conway.probAB(A,B,distribution)
wait = conway.expected_waiting_time(A,B,distribution)
N=10000
np.random.seed(0)
prop, average_n_flips= conway.simulate_winrates_penney_game(A,B,distribution,N)
print('Pr(A<B) = ', "%.3f" %p , ' (Theoretical Probability)')
print('Prop(A<B) = ', "%.3f" %prop[0], ' (Simulation with N =', N, ' trials)\n')
print('E[number of flips] = ', "%.2f" %wait , ' (Theoretical Expectation)')
print('Average number of flips = ', "%.2f" %average_n_flips, ' (Simulation with N =', N, ' trials)')
Pr(A<B) = 0.375 (Theoretical Probability) Prop(A<B) = 0.383 (Simulation with N = 10000 trials) E[number of flips] = 5.00 (Theoretical Expectation) Average number of flips = 5.00 (Simulation with N = 10000 trials)
Let's cross validate generalized Conway w/small alphabet & unequal probalities:
The simulation validates the formula
distribution={'H':.75, 'T':.25}
A = "HTH"
B = "TTH"
p = conway.probAB(A,B,distribution)
wait = conway.expected_waiting_time(A,B,distribution)
N=10000
np.random.seed(0)
prop, average_n_flips= conway.simulate_winrates_penney_game(A,B,distribution,N)
print('Pr(A<B) = ', "%.3f" %p , ' (Theoretical Probability)')
print('Prop(A<B) = ', "%.3f" %prop[0], ' (Simulation with N =', N, ' trials)\n')
print('E[number of flips] = ', "%.2f" %wait , ' (Theoretical Expectation)')
print('Average number of flips = ', "%.2f" %average_n_flips, ' (Simulation with N =', N, ' trials)')
Pr(A<B) = 0.703 (Theoretical Probability) Prop(A<B) = 0.709 (Simulation with N = 10000 trials) E[number of flips] = 6.33 (Theoretical Expectation) Average number of flips = 6.35 (Simulation with N = 10000 trials)
Let's cross validate Conway for longer patterns:
The simulation validates the formula
distribution={'H':.5, 'T':.5}
A = "HTHT"
B = "TTTH"
p = conway.probAB(A,B,distribution)
wait = conway.expected_waiting_time(A,B,distribution)
N=10000
np.random.seed(0)
prop, average_n_flips= conway.simulate_winrates_penney_game(A,B,distribution,N)
print('Pr(A<B) = ', "%.3f" %p , ' (Theoretical Probability)')
print('Prop(A<B) = ', "%.3f" %prop[0], ' (Simulation with N =', N, ' trials)\n')
print('E[number of flips] = ', "%.2f" %wait , ' (Theoretical Expectation)')
print('Average number of flips = ', "%.2f" %average_n_flips, ' (Simulation with N =', N, ' trials)')
Pr(A<B) = 0.438 (Theoretical Probability) Prop(A<B) = 0.447 (Simulation with N = 10000 trials) E[number of flips] = 9.88 (Theoretical Expectation) Average number of flips = 9.81 (Simulation with N = 10000 trials)
Let's cross validate generalized Conway w/with longer alphabet, unequal probabilities, and longer patterns
The simulation validates the formula
distribution={'a':.5, 'b':.25, 'c':.25}
A = "aaac"
B = "abba"
p = conway.probAB(A,B,distribution)
wait = conway.expected_waiting_time(A,B,distribution)
N=10000
np.random.seed(0)
prop, average_n_flips= conway.simulate_winrates_penney_game(A,B,distribution,N)
print('Pr(A<B) = ', "%.3f" %p , ' (Theoretical Probability)')
print('Prop(A<B) = ', "%.3f" %prop[0], ' (Simulation with N =', N, ' trials)\n')
print('E[number of flips] = ', "%.2f" %wait , ' (Theoretical Expectation)')
print('Average number of flips = ', "%.2f" %average_n_flips, ' (Simulation with N =', N, ' trials)')
Pr(A<B) = 0.667 (Theoretical Probability) Prop(A<B) = 0.674 (Simulation with N = 10000 trials) E[number of flips] = 22.00 (Theoretical Expectation) Average number of flips = 21.99 (Simulation with N = 10000 trials)
Waiting time for COVFEFE vs. other patterns.
import string
uppercase_alphabet = dict.fromkeys(string.ascii_uppercase, 0)
distribution = {x: 1/26 for x in uppercase_alphabet}
A = 'COVFEFE'
B = 'CCOVFEF'
p = conway.probAB(A,B,distribution)
print('Pr(',A,'<',B,') = ', "%.3f" %p , ' (Theoretical Probability)')
print('------------------')
wait = conway.expected_waiting_time(A,B,distribution)
print('E[number of flips until',A,'or',B,'] = ', "%.2f" %wait , ' (Theoretical Expectation)')
Pr( COVFEFE < CCOVFEF ) = 0.490 (Theoretical Probability) ------------------ E[number of flips until COVFEFE or CCOVFEF ] = 4094648325.02 (Theoretical Expectation)
What is the first mover's probability of winner if the second mover best responds, as a function of the probability of heads.
import matplotlib.pyplot as plt
import numpy as np
k = 3
#initialize the globals within the module
conway.list_pattern=['-']*k
conway.patterns = []
#build the patterns
conway.all_patterns(k,distribution)
patterns=conway.patterns
pHs = [i/100 for i in range(1,100)]
min_prob_each_pattern = []
#plt.gca().set_prop_cycle(None)
for pH in pHs:
pT = 1-pH
distribution={'H':pH, 'T':pT}
min_probs = []
for A in patterns:
probABs = []
for B in patterns:
if A != B:
probABs.append(conway.probAB(A,B,distribution))
else:
probABs.append(None)
min_probAB = min(p for p in probABs if p is not None)
min_probs.append(min_probAB)
min_prob_each_pattern.append(min_probs)
#plt.figure(figsize=(8, 6),facecolor="white")
#don't include gray borders
plt.figure(facecolor="white")
#plt.style.use('grayscale')
#don't incude negative x-axis
plt.xlim(0, 1)
#plot each graph
i = 0
for pattern in patterns:
#make list x/y-values for plotting
min_probs = [min_prob_each_pattern[j][i] for j in range(len(pHs)) ]
plt.plot(pHs,min_probs,label=pattern)
i +=1
#plot axis labels
#plt.ylabel('Expected Proportion')
#plt.xlabel('Number of shots')
#plot reference lines
plt.plot([0, 100], [.5, .5], 'k--',lw=.75)
#plot legend
plt.legend(bbox_to_anchor=(1, 1), loc=2,prop={'size': 8})
#plot axis labels
plt.ylabel('Probability wins worst match-up')
plt.xlabel('Probability of Heads')
#save figure
filename = 'win_worst_case_'+str(k)+'.pdf'
plt.savefig(filename, bbox_inches="tight");
#plt.axis([0, 6, 0, 20])
What is the expected waiting time for the game to end given the first mover's strategy (when second mover best responds) vs. if the first mover were waiting alone for the pattern.
import matplotlib.pyplot as plt
import numpy as np
#help(conway)
#Difference in waiting time for each pattern, as a function of probability.
k = 3
#initialize the globals within the module
conway.list_pattern=['-']*k
conway.patterns = []
#build the patterns
pH =.5
pT = 1-pH
distribution={'H':pH, 'T':pT}
conway.all_patterns(k,distribution)
patterns=conway.patterns
pHs = [i/1000 for i in range(300,701)]
#print(pHs)
diff_wait_time = []
#plt.gca().set_prop_cycle(None)
for pH in pHs:
pT = 1-pH
distribution={'H':pH, 'T':pT}
diff_waiting_time_A = []
for A in patterns:
probABs = []
for B in patterns:
if A != B:
probABs.append(conway.probAB(A,B,distribution))
else:
probABs.append(None)
waiting_time_A = conway.expected_waiting_time(A,A,distribution)
#in case of times
min_probAB = min(p for p in probABs if p is not None)
min_indices = [i for i in range(len(probABs)) if probABs[i]==min_probAB]
waiting_times_AminB =[]
for i in min_indices:
waiting_times_AminB.append(conway.expected_waiting_time(A,patterns[i],distribution))
waiting_time_AB = min(waiting_times_AminB)
diff_waiting_time_A.append(waiting_time_AB-waiting_time_A)
diff_wait_time.append(diff_waiting_time_A)
#print(wait_time_pairs)
#plt.figure(figsize=(8, 6),facecolor="white")
#don't include gray borders
#plt.figure(facecolor="white")
#plt.style.use('grayscale')
#don't incude negative x-axis
#plt.xlim(0, 50)
#plot each graph
i = 0
#plot each graph
i = 0
for pattern in patterns:
#make list x/y-values for plotting
y = [diff_wait_time[j][i] for j in range(len(pHs)) ]
plt.plot(pHs,y,label=pattern)
i +=1
#plot axis labels
#plt.ylabel('Expected Proportion')
#plt.xlabel('Number of shots')
#plot reference lines
plt.plot([.3, .7], [0, 0], 'k--',lw=.75)
#plot legend
plt.legend(bbox_to_anchor=(1, 1), loc=2,prop={'size': 8})
#plot axis labels
plt.ylabel('E[time game ends] - E[time of pattern]')
plt.xlabel('Probability of Heads')
#save figure
filename = 'waiting_time'+str(k)+'.pdf'
plt.savefig(filename, bbox_inches="tight");