14-Solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Collecting Coupons\n",
    "\n",
    "- Coupons in cereal boxes are numbered 1 to 5\n",
    "    - All 5 coupons must be collected to receive a prize\n",
    "- *With one coupon per box, how many coupons on average are required to make a complete set?*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_____\n",
    "\n",
    "# Solution Attempt 1\n",
    "\n",
    "- First, we'll think of the probability that we get all 5 coupons in our first 5 boxes\n",
    "    - There are $5!$ different permutations of the ordering of coupons, and $5^{5}$ different scenarios overall for the 5 boxes\n",
    "    \n",
    "$$\n",
    "P(\\text{5 distinct coupons in 5 boxes}) = \\frac{5!}{5^{5}} = \\frac{4!}{5^{4}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Next, we consider the case where it takes us 6 boxes to get all 5 coupons\n",
    "    - The easy part is knowing that there are $5^{6}$ different scenarios to get 6 coupons\n",
    "- Now, counting the number of ways we can get 5 coupons in 6 boxes:\n",
    "    - For the first coupon, it's impossible for it already to be a duplicate, so there are 5 possible \"first coupons\"\n",
    "    - Next, **if the second coupon is a duplicate**, there's only one possible coupon it can be (the first one)\n",
    "        - So, the number of ways this can happen is $5\\cdot1\\cdot4\\cdot3\\cdot2\\cdot1$\n",
    "    - Assuming the **second coupon is NOT a duplicate**, then there's 4 possible coupons to get in the second box\n",
    "    - If the **third coupon is a duplicate**, there are 2 options now (the first or the second coupon)\n",
    "        - Therefore, the number of ways this can happen is $5\\cdot4\\cdot2\\cdot3\\cdot2\\cdot1$\n",
    "    - If the **fourth coupon is a duplicate**, there are now 3 options so the number of ways it can happen is $5\\cdot4\\cdot3\\cdot3\\cdot2\\cdot1$\n",
    "    - The final scenario is that the **fifth is a duplicate** which has $5\\cdot4\\cdot3\\cdot2\\cdot4\\cdot1$ ways of happening\n",
    "        - *Why can't the 6th be the duplicate?*\n",
    "            - Because we wouldn't open a 6th box if we hadn't had a duplicate yet (since we'd already have all 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Therefore the probability is:\n",
    "\n",
    "$$\n",
    "P(\\text{5 distinct coupons in 6 boxes}) = \\frac{(1 + 2 + 3 + 4)\\cdot5\\cdot4\\cdot3\\cdot2\\cdot1}{5^{6}} = \\frac{10 \\cdot 4!}{5^{5}} = 2 \\frac{4!}{5^{4}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Now, let's consider the case of getting 5 distinct in 7 boxes\n",
    "    - First can't be a duplicate\n",
    "    - If the **second is a duplicate**, then we need to consider where the other duplicate goes\n",
    "        - If it's the third, it can only be one card (the first)\n",
    "        - If it's the fourth, it can be one of two (the first or the third)\n",
    "        - If it's fifth, if can be one of three (the first, the third, or the fouth)\n",
    "        - If it's the sixth, if can be one of four (the first, the third, the fourth, or the fifth)\n",
    "        - The subtotal number of ways this can happen is $(1+2+3+4)\\cdot5\\cdot1\\cdot4\\cdot3\\cdot2\\cdot1 = 10\\cdot1\\cdot5!$\n",
    "    - If the second isn't a duplicate and the **third is**, it's the same calculation above except with some small adjustments\n",
    "        - The subtotal number of ways this can happen is $(2+3+4)\\cdot5\\cdot4\\cdot2\\cdot3\\cdot2\\cdot1 = 9\\cdot2\\cdot5!$\n",
    "    - If the **first duplicate is the fourth**, the subtotal number of ways this can happen is $(3+4)\\cdot5\\cdot4\\cdot3\\cdot3\\cdot2\\cdot1 = 7\\cdot3\\cdot5!$\n",
    "    - If the **first duplicate is the fifth**, the subtotal number of ways this can happen is $(4)\\cdot5\\cdot4\\cdot3\\cdot2\\cdot4\\cdot1=4\\cdot4\\cdot5!$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Therefore, the probability is equal to:\n",
    "\n",
    "$$\n",
    "P(\\text{5 distinct coupons in 7 boxes}) = \\frac{(10 + 18 + 15 + 16)\\cdot5!}{5^{7}} = \\frac{65\\cdot4!}{5^{6}} = \\frac{13}{5}\\frac{4!}{5^{4}}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- As we can see, **this is a clusterfuck**\n",
    "    - We need to come up with a better solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "\n",
    "# Solution Attempt 2\n",
    "\n",
    "- Let's think of each coupon individually\n",
    "\n",
    "- Let $T_{1}$ be the random variable representing the number of boxes required to get the first distinct coupon\n",
    "    - We know right away that no matter what box we open first, we'll get our first coupon that must be distinct (since we haven't gotten any yet)\n",
    "        - Therefore $T_{1} = 1$\n",
    "        \n",
    "- Let $T_{2}$ be the random variable for the number of **additional boxes** (after the first) to get our second distinct coupon\n",
    "    - For $T_{2}$ to be equal to 1, that means we've opened a box with one of the 5 remaining coupons therefore\n",
    "    \n",
    "$$\n",
    "P(T_{2}=1) = \\frac{4}{5}\n",
    "$$\n",
    "\n",
    "- From this, we can extend this to $T_{2}=2$ where we get the same coupon as before on our first box, then a distinct one on our second so:\n",
    "\n",
    "$$\n",
    "P(T_{2} = 2) = \\frac{1}{5}\\frac{4}{5}\n",
    "$$\n",
    "\n",
    "- It's clear from here that:\n",
    "\n",
    "$$\n",
    "P(T_{2}=k) = \\left ( \\frac{1}{5} \\right )^{k-1} \\frac{4}{5}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Similarly:\n",
    "\n",
    "$$\n",
    "P(T_{3} = k) = \\left (1 - \\frac{3}{5} \\right)^{k-1}\\frac{3}{5}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "P(T_{4}=k) = \\left (1-\\frac{2}{5} \\right )^{k-1}\\frac{2}{5}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "P(T_{5}=k) = \\left (1-\\frac{1}{5} \\right )^{k-1}\\frac{1}{5}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Now, if we define $T$ as the total time required to get our 5 distinct coupons, we want to solve for $E(T)$\n",
    "    - But $T = T_{1}+T_{2}+T_{3}+T_{4}+T_{5}\\implies E(T) = E(T_{1}+T_{2}+T_{3}+T_{4}+T_{5}) = E(T_{1})+E(T_{2})+E(T_{3})+E(T_{4})+E(T_{5})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "E(T_{1}) = 1\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "E(T_{2}) = \\sum_{k=1}^{\\infty}k\\cdot\\left ( \\frac{1}{5} \\right )^{k-1} \\frac{4}{5} = \\frac{5}{4}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "E(T_{3}) = \\sum_{k=1}^{\\infty}k\\cdot\\left (\\frac{2}{5} \\right)^{k-1}\\frac{3}{5} = \\frac{5}{3}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "E(T_{4}) = \\sum_{k=1}^{\\infty}k\\cdot\\left (\\frac{3}{5} \\right)^{k-1}\\frac{2}{5} = \\frac{5}{2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "E(T_{5}) = \\sum_{k=1}^{\\infty}k\\cdot\\left (\\frac{4}{5} \\right)^{k-1}\\frac{1}{5} = 5\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Therefore:\n",
    "\n",
    "$$\n",
    "E(T) = 1 + \\frac{5}{4} + \\frac{5}{3} + \\frac{5}{2} + 5 = \\frac{137}{12}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "\n",
    "- Let's simulate this"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sim():\n",
    "    list_coupons = []\n",
    "    count = 0\n",
    "    while sorted(set(list_coupons))!=[1,2,3,4,5]:\n",
    "        count += 1\n",
    "        new_coupon = np.random.randint(1,6)\n",
    "        list_coupons.append(new_coupon)\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_trials = 100000\n",
    "list_results = []\n",
    "\n",
    "for trial in range(n_trials):\n",
    "    list_results.append(sim())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11.42426"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(list_results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11.416666666666666"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "137/12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Eyyyy"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}