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

- Miller, J.B. (2019) "Penney's game odds from no-arbitrage", OSF PDF Download
- Li, Shuo-Yen Robert. (1980) A martingale approach to the study of occurrence of sequence patterns in repeated experiments."
*the Annals of Probability*, 8(6) 1171-1176. PDF Download - Guibas, L. J. & Odlyzko, A. M. (1981), "String overlaps, pattern matching, and nontransitive games",

*Journal of Combinatorial Theory, Series A* 30(2), 183--208. PDF Download
2.

In [1]:

```
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
```

In [32]:

```
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

In [2]:

```
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:

In [6]:

```
help(conway.payoff_to_B_bettors_if_A_occurs_first)
```

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

In [17]:

```
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:

In [18]:

```
help(conway.oddsAB)
```

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$

- $AA=8+0+2=10$ (the $A$-bets initiated at $T-2$ and $T$ are winners)
- $AB=0+0+0=0$ (the $B$-bets never win)

In the case that B occurs before A, i.e we compare the trailing characters of $B\cdot$

- $BB=8+0+0=8$ (the $B$-bet inititiated at $T-2$ is a winner)
- $BA=0+0+2=2$ (the $A$-bet initiated at $T$ is a winner)

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:

In [19]:

```
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))
```

In [97]:

```
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)
```

Gardner's table (they match):

here is the simulation function:

In [11]:

```
help(conway.simulate_winrates_penney_game)
```

Cross-validate the simple case

In [258]:

```
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)')
```

Let's cross validate generalized Conway w/small alphabet & unequal probalities:

The simulation validates the formula

In [259]:

```
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)')
```

Let's cross validate Conway for longer patterns:

The simulation validates the formula

In [260]:

```
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)')
```

Let's cross validate generalized Conway w/with longer alphabet, unequal probabilities, and longer patterns

The simulation validates the formula

In [262]:

```
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)')
```

Waiting time for COVFEFE vs. other patterns.

In [13]:

```
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)')
```

What is the first mover's probability of winner if the second mover best responds, as a function of the probability of heads.

In [76]:

```
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])
```

In [108]:

```
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");
```