Fiddler on the Proof: Fiddler (10/04/2024)

fiddler_20241004.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6479454d-d434-4808-a73d-01255eed4844",
   "metadata": {},
   "source": [
    "# Fiddler on the Proof\n",
    "\n",
    "Ravi Dayabhai & Conrad Warren 🎲 2024-10-04"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52b23e3c-c3d9-4a10-87b0-8f3910e19419",
   "metadata": {},
   "source": [
    "## Problem\n",
    "\n",
    "From Ryan Lafitte comes a delectable dilemma of dice:\n",
    "\n",
    "When supervising the Board Games club at the high school where he teaches, Ryan saw a group break out TENZI. In this game, each player has 10 dice of the same color (in case the rolls get into each others’ areas, presumably).\n",
    "\n",
    "To get started, you roll all 10 dice—whichever number comes up most frequently becomes your target number. In the event multiple numbers come up most frequently, you can choose your target number from among them. At this point, you put aside all the dice that came up with your target number.\n",
    "\n",
    "From there, you continue rolling any remaining dice, putting aside any that come up with your target number. Once all 10 dice show the same number, you yell, “Tenzi!” If you’re the first to do so, you win.\n",
    "\n",
    "Now, consider a simplified version of the game in which you begin with three total dice (call it “THREEZI”).\n",
    "\n",
    "On average, how many dice will you put aside after first rolling all three?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eaa13279-6073-4c6d-8fa7-e57145e55b49",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "\n",
    "You will, in expectation, put aside $\\frac{53}{36} \\approx 1.47$ dice."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75277d57-d547-41e9-9813-88d90e03dc12",
   "metadata": {},
   "source": [
    "### Rationale\n",
    "\n",
    "Let $X$ be a random variable that counts the number of dice we put aside after the first roll (of $3$ initial dice). We want to know $E(X)$.\n",
    "\n",
    "By definition, $E(X) = \\sum_{x = 1}^{3} x \\cdot P(X = x)$.\n",
    "\n",
    "The probability that we put aside $1$ dice is equivalent to having all three dice result in _different_ values:\n",
    "\n",
    "$$P(X = 1) = \\frac{6 \\cdot 5 \\cdot 4}{6^{3}}\\text{.}$$\n",
    "\n",
    "The probability that we put aside $3$ dice is equivalent to having all three dice result in the _same_ values:\n",
    "\n",
    "$$P(X = 3) = \\frac{6}{6^{3}}\\text{.}$$\n",
    "\n",
    "Finally, since $2$ is the only remaining possible value $X$ can take on, we have:\n",
    "\n",
    "$$P(X = 2) = 1 - P(X = 1) - P(X = 3) = \\frac{6 \\cdot 5 \\cdot 3}{6^{3}}\\text{.}$$\n",
    "\n",
    "Therefore, \n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "E(X) &= 1 \\cdot \\left( \\frac{6 \\cdot 5 \\cdot 4}{6^{3}} \\right)\n",
    "       + 2 \\cdot \\left(\\frac{6 \\cdot 5 \\cdot 3}{6^{3}} \\right)  + 3 \\cdot \\left( \\frac{6}{6^{3}} \\right)\\\\\n",
    "     &= \\frac{53}{36} = 1.47\\bar{2}\\text{ .}\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2881ca6f-8752-4fa0-9a16-390ff41e14aa",
   "metadata": {},
   "source": [
    "## Extra Credit\n",
    "\n",
    "From Ryan Lafitte also comes some Extra Credit:\n",
    "\n",
    "Let’s return to the original game of TENZI, which has 10 dice.\n",
    "\n",
    "On average, how many dice will you put aside after first rolling all 10? (What if, instead of 10 dice, you have N dice?)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8f4e691-e6a0-40af-871c-0bb961af5914",
   "metadata": {},
   "source": [
    "## Solution\n",
    "\n",
    "\n",
    "You will, in expectation, put aside $\\approx 3.44$ dice (when rolling $10$ dice initially)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a12409db-def2-436d-84ca-e6b0033f6576",
   "metadata": {},
   "source": [
    "### Rationale\n",
    "\n",
    "Now let random variable $\\mathbf{X}_{N}$ be the frequency counts from rolling $N$ dice, i.e., each outcome $\\vec{x} = \\langle x_{1}, x_{2}, \\ldots, x_{6} \\rangle$ takes stock of the counts of $1$'s rolled ($x_{1}$), $2$'s rolled ($x_{2}$), etc. Hence, $\\mathbf{X}_{N} \\sim \\text{Multinomial}(N, \\langle \\frac{1}{6}, \\frac{1}{6}, \\frac{1}{6}, \\frac{1}{6}, \\frac{1}{6}, \\frac{1}{6} \\rangle)$.\n",
    "\n",
    "Ultimately, we are trying to compute $E(g(\\mathbf{X}_{N}))$, where $g(\\vec{x}) = \\max \\lbrace x_{1}, x_{2}, \\ldots, x_{6} \\rbrace$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "144c74b7-ecb3-4d08-a6c6-731a0241198a",
   "metadata": {},
   "source": [
    "### Numerical Approximation\n",
    "\n",
    "We wrote some code to directly calculate $E(g(\\mathbf{X}_{10}))$ below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "196d6af6-7562-4561-ac98-ed67bbfcb5f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools as it\n",
    "from collections import defaultdict\n",
    "import math\n",
    "\n",
    "\n",
    "def expected_value_modal_frequency(N: int) -> float:\n",
    "\n",
    "    modal_freq_distribution = defaultdict(int)\n",
    "    expectation = 0\n",
    "    \n",
    "    for outcome in it.product(range(N + 1), repeat=6):\n",
    "        if sum(outcome) == N:\n",
    "            x = list(outcome)\n",
    "            p = (math.factorial(N) / math.prod(map(math.factorial, x))) * ((1/6) ** N)\n",
    "            highest_freq = max(x)\n",
    "            modal_freq_distribution[highest_freq] += 1\n",
    "            expectation += highest_freq * p\n",
    "\n",
    "    return expectation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "abc57370-5ef4-4cb0-ac67-35def8a25fec",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.4447466960702426"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expected_value_modal_frequency(10)"
   ]
  }
 ],
 "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
}