Skip to content

Instantly share code, notes, and snippets.

@SirLich

SirLich/code.py

Created February 24, 2024 08:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save SirLich/e0bf6b61eaa060f2bc56f10611e65c76 to your computer and use it in GitHub Desktop.
Save SirLich/e0bf6b61eaa060f2bc56f10611e65c76 to your computer and use it in GitHub Desktop.
Download ZIP
Markov Puzzle Solution
Raw
readme.md

Markov Chain Puzzle

Puzzle

Team A and Team B are perennial football rivals. Every year they meet for a series of games. The first team to win four games gets to take home the Golden Teapot and keep it for a year. The teams are evenly matched except for a small home advantage. When playing at home, each team has a 51 per cent chance of winning. (And a 49 per cent chance of losing. No ties are allowed.) Every year, the first three games are played at the home of Team A, and the rest at the home of Team B. Which team is more likely to win the Golden Teapot?

Or, what is the probability that Team A wins the Golden Teapot?

Viability of Markov Chains

To apply Markov chains to a probability puzzle, the puzzle must adhere to the markov principle (memorylessness). This is true here, because the chance of winning (or losing) is a set chance, and not dependent on past states.

However, Markov chains are still the wrong tool for the job. To track a first-to-four game state, we need all states from (0,0) to (4,4), totalling 25 in all. That's a 25x25 matrix! The fact that the chain is fully absorbing and contains no loops also makes it rather boring.

Results

Team A: 0.496874249699800 Team B: 0.503125750300200

Raw
code.py
from sympy import *
import itertools
# Number of matches to play at home, before playing away
HOME_MATCHES = 3
# First to this number wins.
MATCHES_TO_WIN = 4
# The chances of winning away or home games
# HOME_CHANCE = Rational(51/100)
# AWAY_CHANCE = Rational(49/100)
HOME_CHANCE = 0.51
AWAY_CHANCE = 0.49
def get_reference_list():
return itertools.product(range(MATCHES_TO_WIN + 1), repeat=2)
def get_reference_matrix():
reference_matrix = []
for i,x in enumerate(get_reference_list()):
reference_matrix.append([])
for j,y in enumerate(get_reference_list()):
reference_matrix[i].append([])
reference_matrix[i][j] = (y, x)
return reference_matrix
def board_size():
return len(list(get_reference_list()))
def get_starting_matrix():
empty = [S(0)] * board_size()
empty[0] = Rational(1)
return Matrix(empty)
def get_transition_matrix():
size = board_size()
matrix = zeros(size)
reference_matrix = get_reference_matrix()
for y in range(size):
for x in range(size):
reference = reference_matrix[x][y]
# The current state we're in: e.g., (1,3), representing 1 vs. 3 (away)
current_state = reference[0]
# The state we would transition to, if we would stay in this row!
next_state = reference[1]
# If we've reached a 'winning' state:
if current_state[0] == MATCHES_TO_WIN or current_state[1] == MATCHES_TO_WIN:
# Next state matches our winning state, so (1) makes a loop
if current_state == next_state:
matrix[x,y] = S(1)
# Zero out the rest of the column
else:
matrix[x,y] = S(0)
continue
# We can calculate whether this state is a home-game (first HOME_MATCHES game) by calculating total wins
# This logic is flimsy against points being awarded in some other way than matches.
is_home_game = current_state[0] + current_state[1] > HOME_MATCHES
a_victory = next_state[0] == current_state[0] + 1
b_victory = next_state[1] == current_state[1] + 1
a_stayed_same = next_state[0] == current_state[0]
b_stayed_same = next_state[1] == current_state[1]
# Winning in this state would be a home-A victory
if a_victory and b_stayed_same:
matrix[x,y] = HOME_CHANCE if is_home_game else AWAY_CHANCE
continue
# Winning in this state would be a team-B victory
if b_victory and a_stayed_same:
matrix[x,y] = AWAY_CHANCE if is_home_game else HOME_CHANCE
continue
# Technically not required since we started with zeros, but:
# Any other state would be illegal. For example some states would represent
# both teams winning at once, or one team winning lots of points at once.
matrix[x,y] = S(0)
return matrix
def main():
matrix = get_starting_matrix()
transform = get_transition_matrix()
pprint(transform, wrap_line=False)
for i in range(MATCHES_TO_WIN * 2):
matrix = transform * matrix
# print(matrix)
# print(list(get_reference_list()))
a_chance = 0
b_chance = 0
for m, r in zip(matrix, get_reference_list()):
if(r[0] == 4):
a_chance += m
if(r[1] == 4):
b_chance += m
print(Float(a_chance))
print(Float(b_chance))
main()
Raw
transition_matrix.txt
⎡ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎤
⎢ ⎥
⎢0.51 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0.51 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0.51 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0.51 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢0.49 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0.49 0 0 0 0.51 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0.49 0 0 0 0.51 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0.49 0 0 0 0.51 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0.49 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0.49 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0.49 0 0 0 0.51 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0.49 0 0 0 0.51 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0.51 0 0 0 0.49 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0 0 0 0.49 1 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0.49 0 0 0 0 0 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0 0.49 0 0 0 0.51 0 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0 0 0.51 0 0 0 0.49 0 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0 0 0 0.51 0 0 0 0.49 0 0 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.49 1 0 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.49 0 0 0 0 1 0 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.51 0 0 0 0 1 0 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.51 0 0 0 0 1 0 0⎥
⎢ ⎥
⎢ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.51 0 0 0 0 1 0⎥
⎢ ⎥
⎣ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1⎦
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment