Make a bijection between Alice's and Bob's wins in coin-tossing game

coinbijection.py

# Re https://twitter.com/littmath/status/1770236243911000334
# Coin flipping bijection, based on @NoahJSnyder et al's proof

# Original score: HH scores 1 to Alice and HT scores 1 to Bob
# Adjusted score to Bob: as above except (the last) HT only scores 1/2 to Bob if there isn't a later H.
# Using adjusted scores, the number of Alice wins equals the number of Bob wins.
# The function below produces an explicit, though obscure, "local" bijection between Alice's wins and Bob's wins
# that doesn't involve collecting all of them first.

import sys
n=5
if len(sys.argv)>1: n=int(sys.argv[1])

# 0=H, 1=T

def sgn(x): return (x>0)-(x<0)
def HT(seq): return "".join("HT"[i] for i in seq)

# Return (Alice's score) - (Bob's adjusted score)
def score(seq):
  prev=1
  pendbob=0
  sc=0
  for coin in seq:
    if prev==0:
      if coin==0: sc+=1
      if coin==1: pendbob=1
    if coin==0:
      sc-=pendbob
      pendbob=0
    prev=coin
  return sc-pendbob/2

# do_f() can be any bijection between HH<stuff> and HT<stuff>
def do_f(seq):
  seq[1]=1-seq[1]

# A bijection between Alice's wins and Bob's wins for sequences starting with H that have no other tying H.
# Apply f g f g f ... g f = f(gf)^n to sequence of coin flips, seq, where
# f = any fixed bijection between HH<stuff> and HT<stuff>,
# g = reversal of flips up to the position of the first tying H (after 0)
# n = the minimum value for which (f(gf)^n)(seq) has no tying H (after 0)
def F(seq):
  assert seq!=[]
  if len(seq)<=1: return seq
  seq=seq[:]
  assert seq[0]==0
  do_f(seq)
  n=len(seq)
  while 1:
    fth=None# Will be set to the position of the first tying H (after 0)
    prev=1
    sc=0
    pendbob=0
    for (i,coin) in enumerate(seq):
      if prev==0:
        if coin==0: sc+=1
        if coin==1: pendbob=1
      if coin==0:
        sc-=pendbob
        pendbob=0
        if sc==0 and i>0: fth=i;break
      prev=coin
    if fth==None: return seq
    
    # Reverse the order of flips up to the first tying H
    seq=seq[:1]+seq[fth-1:0:-1]+seq[fth:]
    
    do_f(seq)

# A bijection between Alice's wins and Bob's wins (for any sequence)
def bij(seq):
  lth=None# Will be set to the position of the last tying H
  prev=1
  sc=0
  pendbob=0
  for (i,coin) in enumerate(seq):
    if prev==0:
      if coin==0: sc+=1
      if coin==1: pendbob=1
    if coin==0:
      sc-=pendbob
      pendbob=0
      if sc==0: lth=i
    prev=coin
  if lth==None: return seq
  else: return seq[:lth]+F(seq[lth:])

image=set()
a=b=0
for pseq in range(2**n):
  seq=[pseq>>j&1 for j in range(n)]
  bseq=bij(seq)
  image.add(tuple(bseq))
  sc0,sc1=score(seq),score(bseq)
  a+=(sc0>0)
  b+=(sc0<0)
  print("%s %8.1f   %s %8.1f"%(HT(seq),sc0,HT(bseq),sc1))

  # Check we have exchanged Alice's wins and Bob's wins
  assert sgn(sc1)==-sgn(sc0)

print("Alice wins",a)
print("Bob wins",b)
assert a==b

# Check we have a bijection
assert len(image)==2**n