statistics/10_days/06_day2basicprobability.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution to: [Day 2: Basic Probability](https://www.hackerrank.com/challenges/s10-mcq-1/tutorial)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 id=\"tocheading\">Table of Contents</h1>\n",
    "<div id=\"toc\"></div>\n",
    "\n",
    "- Table of Contents\n",
    "- Probability Notes\n",
    "    - Event, Sample Space, and Probability\n",
    "    - Fundamental probability rules\n",
    "    - Sample question\n",
    "    - Sample question 2\n",
    "- Math Solution\n",
    "    - Information\n",
    "    - Formula:\n",
    "    - Implementation\n",
    "- Solution\n",
    "    - Imports\n",
    "    - Process\n",
    "    - Probability of dice rolls at target\n",
    "    - Main"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/javascript": [
       "$.getScript('https://kmahelona.github.io/ipython_notebook_goodies/ipython_notebook_toc.js')\n"
      ],
      "text/plain": [
       "<IPython.core.display.Javascript object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%javascript\n",
    "$.getScript('https://kmahelona.github.io/ipython_notebook_goodies/ipython_notebook_toc.js')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Probability Notes\n",
    "\n",
    "## Event, Sample Space, and Probability\n",
    "In probability theory, an **experiment** is any procedure that can be infinitely repeated and has a well-defined set of possible outcomes, known as the sample space, **S**. We define an event to be a set of outcomes of an experiment (also known as a subset of **S**) to which a probability (numerical value) is assigned.\n",
    "\n",
    "The probability of the occurrence of an event, A, is:\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "\\mathrm{P}(A) = \n",
    "\\frac\n",
    "{\\text{Number of favorable outcomes}}\n",
    "{\\text{Total number of outcomes}}\n",
    "$$\n",
    "\n",
    "\n",
    "### Fundamental probability rules\n",
    "Here are the first two fundamental rules of probability:\n",
    "1. Any probability, **P(A)** , is a number between 0 and 1 *(0 <= P(A) <= 1)*.\n",
    "2. The probability of the sample space, **S**, is 1 *(P(S) = 1)*.\n",
    "\n",
    "So how do we bridge the gap between the value of **P(A)** and the sample space **P(S)**? \n",
    "We know that **P(A)** is the probability that event will occur, then we define $P(A^{c})$ - the complement of **P(A)** to be the probability that event **P(A)** will not occur. \n",
    "\n",
    "\n",
    "If our sample space is composed of the probabilities of P(A)'s occurrence and non-occurrence, we can then say:\n",
    "\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "P(A) + P(A^{c}) = 1\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "or, that the sum of all possible outcomes of A in the sample space is equal to 1. \n",
    "\n",
    "This is the third fundamental rule of probability:\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "\\text{P}(A^{c}) = 1 - \\text{P(A)}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sample question\n",
    "Find the probability of getting an odd number when rolling a 6-sided fair die.\n",
    "\n",
    "Given the above question, we can extract the following:\n",
    "- Experiment: rolling a 6-sided die.\n",
    "- Sample space (1): .\n",
    "- Event (3): that the number rolled is odd (i.e., 1, 3, 5).\n",
    "\n",
    "P(A) = (number of favorable outcomes) / (total number of outcomes) = P(A) / P(S) = 3/6 = 1/2\n",
    "\n",
    "\\begin{equation}\n",
    "\\normalsize\n",
    "P(A) = \\frac\n",
    "{\\text{number of favorable outcomes}}\n",
    "{\\text{total number of outcomes}}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\normalsize\n",
    "= \\frac\n",
    "{P(A)}{P(S)}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\normalsize\n",
    "= \\frac{3}{6}\n",
    "= \\frac{1}{2}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sample question 2\n",
    "\n",
    "Let A and B be two events such that P(A) = 2/5 and P(B) = 4/5. If the probability of the occurrence of either A or B is 3/5, find the probability of the occurrence of both A and B together (i.e., P(A n B)).\n",
    "\n",
    "We can use our fundamental rules of probability to solve this problem:\n",
    "\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "|A \\cup B| = |A| + |B| - |A \\cap B|\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "P(A \\cup B) = P(A) + P(B) - P(A \\cap B)\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "P(A \\cap B) = P(A) + P(B) - P(A \\cup B)\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "P(A \\cap B) = \\frac{2}{5} + \\frac{4}{5} - \\frac{3}{5}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "= \\frac{3}{5}\n",
    "\\end{equation}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Math Solution\n",
    "\n",
    "## Information\n",
    "In a single roll of 2 fair (evenly-weighted) six-sided dice, find the probability that their sum will be at most 9.\n",
    "- Experiment: rolling 2 dice\n",
    "- Sample space(S) = possible outcomes = 6 * 6 = 36\n",
    "- Event P(A + B) <= 9\n",
    "\n",
    "\n",
    "## Formula:\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "P(A) = \\frac{\\text{Number of favorable events}}{\\text{Probability Space}}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "P(A) = \\frac{P(A)}{P(S)}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "P(A) = P(S) - P(A^{c})\n",
    "\\end{equation}\n",
    "\n",
    "We can also find $P(A^{C})$, which is easier to calculate given the experiment context.\n",
    "\n",
    "\n",
    "## Implementation\n",
    "*Determine the probability of rolling 10+*\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "P(A) = P(S) - P(A^{C})\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "P(A^{C}) = P( (4, 6)) + P( (5, 5), (5, 6)) + P( (6, 4), (6, 5), (6, 6))\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "= \\frac{1 + 2 + 3}{36}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "= 1 - \\frac{6}{36}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "= \\frac{30}{36}\n",
    "= \\frac{5}{6}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\large\n",
    "= 0.833\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Imports\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "lines_to_next_cell": 2
   },
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 1
   },
   "source": [
    "## Process\n",
    "- Iterate through all possible rolling combinations and create list of values <= 9\n",
    "- Divide by number of total events"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Probability of dice rolls at target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_possible_combinations(num_dice: int, dice_face: int, target: int) -> List[List[int]]:\n",
    "\t\"\"\"Returns Cartesian product of all possible dice rolls.\n",
    "\t\n",
    "\tUses two helper functions:\n",
    "\t\t- get_possible_rolls, generator func to yield all die rolls.\n",
    "\t\t- recurse_roll_combos, helper recursion to create combinations for `num_dice`\n",
    "\t\"\"\"\n",
    "\tdef get_possible_rolls(dice_face: int) -> int:\n",
    "\t\t\"\"\"Generator funct to yield possible rolls.\"\"\"\n",
    "\t\tfor i in range(1, dice_face + 1): yield i\n",
    "\t\n",
    "\n",
    "\tdef recurse_roll_combos(processed_dice: int, all_roll_combos: list) -> List[List[int]]:\n",
    "\t\t\"\"\"Helper func to recurse through all dice.\"\"\"\n",
    "\t\tif processed_dice == num_dice:\t\t## Base case\n",
    "\t\t\treturn all_roll_combos\n",
    "\t\t\n",
    "\t\tnew_roll_combos = []\n",
    "\t\tfor roll in all_roll_combos:\n",
    "\t\t\troll_combo = [roll + [val] for val in get_possible_rolls(dice_face)]\n",
    "\t\t\tnew_roll_combos += (roll_combo)\n",
    "\t\t\n",
    "\t\tprocessed_dice += 1\n",
    "\t\treturn recurse_roll_combos(processed_dice= processed_dice, all_roll_combos = new_roll_combos)\n",
    "\n",
    "\t\n",
    "\tfirst_rolls = [[val] for val in get_possible_rolls(dice_face)]\n",
    "\troll_combinations = recurse_roll_combos( 1, first_rolls)\n",
    "\n",
    "\n",
    "\tassert (len(roll_combinations) == dice_face ** num_dice)\n",
    "\treturn roll_combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Main"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "lines_to_next_cell": 2
   },
   "outputs": [],
   "source": [
    "def main():\n",
    "\tnum_dice = 2\n",
    "\tdice_face = 6\n",
    "\ttarget = 9\n",
    "\n",
    "\t## Get Combinations\n",
    "\troll_combos = get_possible_combinations(num_dice, dice_face, target)\n",
    "\n",
    "\t## Count combos at target\n",
    "\tnum_under_target = 0\n",
    "\tfor combo in roll_combos:\n",
    "\t\tif sum(combo) <= target:\n",
    "\t\t\tnum_under_target += 1\n",
    "\t\n",
    "\t## Return P(A) / P(S)\n",
    "\tprob = num_under_target / len(roll_combos)\n",
    "\tprint( round(prob, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.833\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "\tmain()"
   ]
  }
 ],
 "metadata": {
  "jupytext": {
   "cell_metadata_filter": "-all",
   "notebook_metadata_filter": "-all",
   "text_representation": {
    "extension": ".py",
    "format_name": "light"
   }
  },
  "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}