Nov_15_19-Classic.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">From Ricky Jacobson comes a puzzle of seeing how low you can roll:\n",
    ">\n",
    ">You are given a fair, unweighted 10-sided die with sides labeled 0 to 9 and a sheet of paper to record your score. (If the very notion of a fair 10-sided die bothers you, and you need to know what sort of three-dimensional solid it is, then forget it — you have a random number generator that gives you an integer value from 0 to 9 with equal probability. Your loss — the die was a collector’s item.)\n",
    ">\n",
    ">To start the game, you roll the die. Your current “score” is the number shown, divided by 10. For example, if you were to roll a 7, then your score would be 0.7. Then, you keep rolling the die over and over again. Each time you roll, if the digit shown by the die is less than or equal to the last digit of your score, then that roll becomes the new last digit of your score. Otherwise you just go ahead and roll again. The game ends when you roll a zero.\n",
    ">\n",
    ">For example, suppose you roll the following: 6, 2, 5, 1, 8, 1, 0. After your first roll, your score would be 0.6, After the second, it’s 0.62. You ignore the third roll, since 5 is greater than the current last digit, 2. After the fourth roll, your score is 0.621. You ignore the fifth roll, since 8 is greater than the current last digit, 1. After the sixth roll, your score is 0.6211. And after the seventh roll, the game is over — 0.6211 is your final score.\n",
    ">\n",
    ">What will be your average final score in this game?\n",
    "\n",
    "[FiveThirtyEight](https://fivethirtyeight.com/features/how-low-can-you-roll/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Initial Thoughts\n",
    "\n",
    "It's clear that we're going to have a uniform distribution between the first decimal digits (0.0..., 0.1..., ..., 0.9...) as each has a probability of 0.1. This suggests that the expected score should be near the mean of 0.45. However, as the first decimal digit gets higher we're going to encounter higher and higher subsuquent digits (it's not possible to get a 9 after a 1, but it is possible after a 9), which should nudge the expected score to the right a little bit. So the expected score should be between **0.45 and 0.5**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Simulation\n",
    "This problem is easier to simulate than rigorously compute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "def gen_digits(dig):\n",
    "    digits = []\n",
    "    last = randint(0,dig)\n",
    "    digits.append(last)\n",
    "    while last != 0:\n",
    "        nextt = randint(0,dig)\n",
    "        if nextt <= last:\n",
    "            digits.append(nextt)\n",
    "            last = nextt\n",
    "    \n",
    "    # Turn the list into a decimal number\n",
    "    # A list like [5, 3, 1] will be turned in to 0.531\n",
    "    str_decimal = '0.'\n",
    "    for digit in digits:\n",
    "        str_decimal += str(digit)\n",
    "    dec = float(str_decimal)\n",
    "    return dec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.47340238530666706"
      ]
     },
     "execution_count": 195,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sim_gen_digits(n=1000000,dig = 9):\n",
    "    total = 0\n",
    "    for _ in range(n):\n",
    "        total += gen_digits(dig)\n",
    "    return total/n\n",
    "sim_gen_digits()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ~0.473\n",
    "Interesting! Almost exactly in the middle of the range I initially guessed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mathematical Solution\n",
    "## Expected Score\n",
    "Let $ES$ be the expected score; $f$, the first digit; $ES_f$, the expected score given that the first digit is $f$.\n",
    "\n",
    "$$ES = P(f=0)ES_0 + P(f=1)ES_1 + \\dots + P(f=9)ES_9$$ \n",
    "\n",
    "We know that:\n",
    "\n",
    "$$P(f=0) = \\dots = P(f=9) = 0.1$$\n",
    "\n",
    "Hence:\n",
    "\n",
    "$$ES = \\frac{ES_0 + ES_1 + \\dots + ES_9}{10}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Expected Score Given the First Digit\n",
    "If we can calculate $ES_0 - ES_9$, then all we have to do is to calculate their mean.\n",
    "\n",
    "We know that if $f = 0$ then the expected score is 0 becuase that means the game has ended right at the outset by rolling a 0:\n",
    "$$ES_0 = 0$$\n",
    "\n",
    "What about $ES_1$?  \n",
    "Die rolls that are higher than 1 have no effect whatsoever at this point. If we conditionalize on the roll being either a 0 or a 1 (the only efficacious rolls) we can see that with equal probability we'll either roll a 0 and the game will end, or roll a 1 and get to roll the die once more. Since there are only two efficacious rolls when $f = 1$, both have a probability of 0.5.  \n",
    "$$ES_1 = 0.1 + 0.01(0.5) + 0.001(0.5)^2 + \\dots$$\n",
    "Now, we are already assuming that the first die roll was a 1. With 0.5 probability the second roll will be a 1, which will add 0.01 to our score. So the second roll adds an expected score of 0.005. The third roll will add an expected score 0.001 with probability of (0.5)^2. And so on.\n",
    "\n",
    "$$= \\sum_{n=0}^{\\infty}0.1(0.05)^n$$\n",
    "$$ES_1 \\simeq 0.10526$$\n",
    "\n",
    "$ES_2:$ We assume that the first roll was a 2 (i.e. starting with 0.2).\n",
    "In this case, we have three efficacious rolls: 0, 1, 2, with 1/3 probability each.  \n",
    "If the second roll is a 0, $ES_{2,0} = 0.2$  \n",
    "If it is a 1, $ES_{2,1} = 0.2 + ES_1/10.$ We can use our findings above! We divide $ES_1$ by 10 merely because we moved by one decimal point.  \n",
    "If it is a 2, same thing: $ES_{2,2} = 0.2 + ES_2/10$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ES_2 = \\frac{1}{3}\\left(\\frac{2}{10} + \\frac{2 + ES_1}{10} + \\frac{2+ES_2}{10}\\right)$$\n",
    "\n",
    "Once we isolate $ES_2$ on the left hand side, all that is left is simple arithmetic.\n",
    "\n",
    "$$ = \\frac{1}{29}\\left(2 \\cdot 3 + ES_1 \\right)$$\n",
    "\n",
    "$$ES_2 \\simeq 0.2105$$\n",
    "\n",
    "$ES_n:$ What's nice about this is we can generalize it for any $n$.\n",
    "\n",
    "$$ES_n = \\frac{1}{n+1}\\left( \\frac{n}{10} + \\frac{n + ES_1}{10} + \\dots + \\frac{n + ES_{n-1}}{10} + \\frac{n + ES_n}{10}\\right)$$\n",
    "Isolating $ES_n$:\n",
    "$$ES_n = \\frac{1}{10n + 9}\\left( n(n+1) + \\sum_{i=1}^{n-1}ES_i \\right)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Takeaways\n",
    "The interesting thing about this problem is that the die-rolls can go on indefinitely. For instance, it's perfectly possible to have a sequence like '0.999998888888777777766655555544433221111.' So a brute force solution where we compute each individual probability is impossible, barring approximations.\n",
    "\n",
    "But the problem has this beautiful, doubly self-referential nature: Not only does the solution for $n$ rely on all $m < n$, it also relies on itself. And that makes all the difference between having some kind of a vague idea on level 0 (i.e. Initial Thoughts) and having the full picture just by going one level deeper (i.e. where we are now)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Code\n",
    "With no optimizations whatsoever, we can compute the expected score in microseconds now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Expected score when the first digit is 0: 0\n",
      "Expected score when the first digit is 1: 0.1053\n",
      "Expected score when the first digit is 2: 0.2105\n",
      "Expected score when the first digit is 3: 0.3158\n",
      "Expected score when the first digit is 4: 0.4211\n",
      "Expected score when the first digit is 5: 0.5263\n",
      "Expected score when the first digit is 6: 0.6316\n",
      "Expected score when the first digit is 7: 0.7368\n",
      "Expected score when the first digit is 8: 0.8421\n",
      "Expected score when the first digit is 9: 0.9474\n"
     ]
    }
   ],
   "source": [
    "def first_digit(n):\n",
    "    '''\n",
    "    Computes the expected value when the first digit == n\n",
    "    '''\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    # n(n+1)\n",
    "    res = (n)*(n+1)\n",
    "    i = 1\n",
    "    # the sum\n",
    "    while i < n:\n",
    "        add = first_digit(i)\n",
    "        res += add\n",
    "        i += 1\n",
    "    # 1/(10n + 9)\n",
    "    res = res/(10*n+9)\n",
    "    return res\n",
    "\n",
    "exp_value_per_first_digit = [first_digit(n) for n in range(10)]\n",
    "for i in range(len(exp_value_per_first_digit)):\n",
    "    print(f'Expected score when the first digit is {i}:',\n",
    "          round(exp_value_per_first_digit[i],4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Given that all first digits are equally likely, we can just take the mean of the expected values for each first digit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4736842105263158"
      ]
     },
     "execution_count": 182,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Average\n",
    "sum(exp_value_per_first_digit)/len(exp_value_per_first_digit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Expected Score = 0.4737"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bonus\n",
    "We have our answer already. But those $ES_n$ values we computed strongly suggest that there is a much simpler answer. Think about the following:  \n",
    "Why does $ES = (ES_9 - 0.9)\\cdot 10?$  \n",
    "And why does it look like $ES_n = n \\cdot ES_1$?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}