Fiddler on the Proof: Fiddler (07/26/2024)

fiddler_20240726.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6479454d-d434-4808-a73d-01255eed4844",
   "metadata": {},
   "source": [
    "# Fiddler on the Proof\n",
    "\n",
    "Ravi Dayabhai 🎲 2024-07-26"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52b23e3c-c3d9-4a10-87b0-8f3910e19419",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "## Problem\n",
    "\n",
    "Suppose you (player A) and a friend (player B) are playing a game in which you alternate rolling a die. So the order of play is AB|AB|AB, and so on. (The vertical bars here are just for organizational purposes, and do not signify anything special that happens.) The first player to roll a five wins the game. As it turns out, whoever goes first has a distinct advantage!\n",
    "\n",
    "Kayla wondered about other ways you and your friend could take turns, ways that might result in a fairer game. For example, consider the “snake” method, in which the order is reversed after each time you both roll: AB|BA|AB|BA, and so on.\n",
    "\n",
    "Assuming you are the first to roll, what is the probability you will win the game?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eaa13279-6073-4c6d-8fa7-e57145e55b49",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "The probability player A wins the game is $\\frac{31}{61} \\approx 0.508$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75277d57-d547-41e9-9813-88d90e03dc12",
   "metadata": {},
   "source": [
    "### Rationale"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8931b3c-22d7-479f-9cc5-6d11e07e7cc0",
   "metadata": {},
   "source": [
    "This game, under the \"snake\" method, is self-similar after `AB|BA`. Therefore, we can compute $P(A)$, where $A$ is the event that player A wins as a recurrence using the law of total probability & the (conditional) probabilities of $A$ given $N_{i}$, where $N_{i}$ is the event there is no winner after $i$ rolls:\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "P(A) &= P(A | N_{0}) P(N_{0}) + P(A | N_{3}) P(N_{3}) + P(A | N_{4}) P(N_{4})\\\\\n",
    "     &= \\frac{1}{6} + \\left( \\frac{5}{6} \\right)^{3} \\left( \\frac{1}{6} \\right) + \\left( \\frac{5}{6} \\right)^{4} P(A)\\\\\n",
    "     &= \\frac{\\frac{1}{6} + \\left( \\frac{5}{6} \\right)^{3} \\left( \\frac{1}{6} \\right)}{1 - \\left( \\frac{5}{6} \\right)^{4}}\\\\\n",
    "     &= \\frac{31}{61}\n",
    "\\end{align*}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "80e78c1c-8c18-497b-b0ab-be3ca9cba827",
   "metadata": {},
   "outputs": [],
   "source": [
    "from fractions import Fraction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "bdd84d48-ea46-4262-9030-abd9ea304cfd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(31, 61)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_roll_win = Fraction(1, 6)\n",
    "p_A_wins = (p_roll_win + ((1 - p_roll_win) ** 3) * (p_roll_win)) / (1 - ((1 - p_roll_win) ** 4))\n",
    "\n",
    "p_A_wins"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "729e798d-d09d-4355-b039-2ece14b78d09",
   "metadata": {},
   "source": [
    "We see that player A still has a (slight) edge under the \"snake\" scheme!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55b45dbc-2223-47b4-9678-a7ce765e6c91",
   "metadata": {},
   "source": [
    "### Numerical Approach"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57477c54-1e9e-4c0e-b68e-244874f6bb1c",
   "metadata": {},
   "source": [
    "The following simulates the game under the \"snake\" method of determining the first player to roll in a round."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a998f94e-cda0-40bd-b39a-02289d26314d",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "948e84ed-c740-452d-886f-ab1dea0d12a5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5080885"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DICE = list(range(1, 6 + 1))\n",
    "WINNING_ROLL = 5\n",
    "N = 10_000_000\n",
    "\n",
    "def play(A_first: int = True) -> int:\n",
    "    while True:\n",
    "        if A_first:\n",
    "            if (A_roll := random.choice(DICE)) == WINNING_ROLL:\n",
    "                return 1\n",
    "            if (B_roll := random.choice(DICE)) == WINNING_ROLL:\n",
    "                return 0\n",
    "            else: \n",
    "                A_first = not A_first\n",
    "        else:\n",
    "            if (B_roll := random.choice(DICE)) == WINNING_ROLL:\n",
    "                return 0\n",
    "            if (A_roll := random.choice(DICE)) == WINNING_ROLL:\n",
    "                return 1\n",
    "            else: \n",
    "                A_first = not A_first\n",
    "\n",
    "A_wins_count = 0\n",
    "for _ in range(N):\n",
    "    A_wins_count += play()\n",
    "    \n",
    "A_wins_count / N"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89cd71d2-368f-40c3-a069-d23a5f1b60ae",
   "metadata": {},
   "source": [
    "We confirm the analytical result from above as $\\frac{31}{61} \\approx 0.508$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}