module-3/day-1-probability/probability.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Objectives\n",
    "\n",
    "- Basics of counting: Factorials - permutations and combinations\n",
    "\n",
    "- What is probability:\n",
    " \n",
    "- Axioms of Probability:\n",
    " \n",
    "- Mutually exclusive events and independence\n",
    "\n",
    "- Conditional Probability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Counting \n",
    "\n",
    "\n",
    "<img src=\"img/counting.png\"\n",
    "     alt=\"Dice\"\n",
    "     style=\"float: center; margin-left: 40px;\" />\n",
    "     \n",
    "### Product Rule of Counting :\n",
    "\n",
    "If an experiment has two parts, where the first part can result in one of _m_ outcomes and the second part can result in one of _n_ outcomes regardless of the outcome of the first part, then the total number of outcomes for the experiment is _mn_.\n",
    "\n",
    "\n",
    "__Q:__ Can you think of any example of that this rule is very handy when you are working with Python? (Hint - (i,j))\n",
    "\n",
    "__A:__\n",
    "\n",
    "__Example:__ Later on we will be using GridSearchCV algorithm to fine-tune parameters. There we can also use this basic principal of counting.\n",
    "[Sklearn - GridSearchCV](https://scikit-learn.org/stable/modules/grid_search.html#grid-search)\n",
    "\n",
    "\n",
    "### Factorials\n",
    "\n",
    "Factorials are basically a short hand notation for recursive multiplication. \n",
    "We start with assuming \n",
    "0! = 1\n",
    "1! = 1\n",
    "\n",
    "Then recursively define:\n",
    "\n",
    "2! = 2.1!\n",
    "\n",
    "3! = 3.2! = 3.2.1\n",
    "\n",
    "4! = 4.3! = 4.3.2.1\n",
    ".\n",
    ".\n",
    ".\n",
    "n! = n.(n-1)! = n.(n-1).(n-2)...2.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# for simulating the experiments\n",
    "import numpy as np\n",
    "\n",
    "# for visualizing the probabilities\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define a function that returns factorials\n",
    "def factorial(n):\n",
    "    product = 1\n",
    "    while n != 0:\n",
    "        product *= n\n",
    "        n -= 1\n",
    "    return product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's check whether our function works well.\n",
    "factorial(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Permutations\n",
    "\n",
    "Permutation Rule: A permutation is an ordered arrangement of n distinct object. Those n objects can be permuted in $n \\times (n–1) \\times (n–2)\\times... \\times 2 \\times 1=n!$ ways.\n",
    "\n",
    "Example: iPhones have 4-digit passcodes. Suppose there are 4 smudges over 4 digits on the screen. How many distinct passcodes are possible?\n",
    "\n",
    "A: \n",
    "\n",
    "__What if..__ \n",
    "What if there are 3 smudges over 3 digits on screen?\n",
    "\n",
    "Let's write a code to solve this problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "\n",
    "# here numbers are arbitrary and\n",
    "# just for the purpose of demonstration\n",
    "\n",
    "permutations = list(itertools.permutations([5, 2, 9, 8]))\n",
    "print(permutations)\n",
    "\n",
    "# can you write a function that returns\n",
    "# all combinations with 3 letter?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Hint: Suppose that the numbers are {0,3,7} and\n",
    "# suppose we know 0 is repeating.\n",
    "# Then the following code returns all the possible\n",
    "# 4 digit passwords with 0,3,7 with 0 is the only number repeating.\n",
    "\n",
    "\n",
    "set(itertools.permutations([7, 3, 0, 0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Permutation of Indistinct Objects: \n",
    "Generally when there are n objects and $n_1$ are the same (indistinguishable) and $n_2$ are the same and\n",
    "... $n_r$ are the same, then there are $ \\frac{n!}{n_1 ! n_2 ! \\cdots n_r !}$ different permutations.\n",
    "\n",
    "Example: How many distinct bit strings can be formed from three 0’s and two 1’s?\n",
    "\n",
    "### Combinations\n",
    "\n",
    "A combination is an unordered selection of r objects from a set of n objects. If all objects are distinct, then the number of ways of making the selection is:\n",
    "$${n\\choose r} = \\frac{n!}{(n-r)! r!}$$ \n",
    "\n",
    "We read the expression on the left as \"n choose k\"\".\n",
    "\n",
    "__Q:__ Suppose we are given $5$ variables $x_1, \\cdots, x_{5}$. How many terms are there in a second degree polynomial that we can create by using these variables? Note that we can have \n",
    "\n",
    "$$ 1+ a_1 x_1 + a_2 x_2 + \\cdots +a_5 x_5 + b_{11} x_{1}^{2}+ \\cdots + b_{55}x_{5}^{2} + b_{12}x_{1}x_{2} + \\cdots + b_{45}x_{4}x_{5} $$\n",
    "\n",
    "__Note__ This problem will be useful when we working with polynomial regression problems.\n",
    "\n",
    "\n",
    "If you want to read extra examples on combinations please open the pdf using the link below and read the section clustering. This discussion will be relevant when we discuss machine learning algorithms like KNN, Kmeans etc.\n",
    "\n",
    "[Counting](stanford_lecture_notes_counting.pdf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Probability\n",
    "\n",
    "[It turns out that every coin toss is biased a little bit](https://www.youtube.com/watch?v=AYnJv68T3MM)\n",
    "\n",
    "__What is Probability?__\n",
    "\n",
    "- Probability is a measure between 0 and 1 quantifying the likelihood that events will occur. (Note that there are different philosophies to define probability but we will discuss later)\n",
    "\n",
    "### Where do we use probability in data science?\n",
    "\n",
    "__Classification problem:__\n",
    "\n",
    "<img src=\"img/classification.png\"\n",
    " alt=\"Dice\"\n",
    " width = 400\n",
    " style=\"float: center; margin-left: 9px;\" />\n",
    "\n",
    "[Source of the image](https://en.wikipedia.org/wiki/Logistic_regression)\n",
    "\n",
    "\n",
    "__Language Models__\n",
    "\n",
    "<img src=\"img/NLP.png\"\n",
    " alt=\"Dice\"\n",
    " width = 400\n",
    " style=\"float: center; margin-left: 9px;\" />\n",
    "\n",
    "[Source of the image](https://towardsdatascience.com/learning-nlp-language-models-with-real-data-cdff04c51c25)\n",
    "\n",
    "\n",
    "and many other applications.\n",
    "\n",
    "### Event Space and Sample Space\n",
    "\n",
    "__Sample Space (Usually denoted with S):__ The set of all possible outcomes of an experiment.\n",
    "\n",
    "Experiments:\n",
    "\n",
    "- coin flip\n",
    "\n",
    "- Flipping two coins\n",
    "\n",
    "- Roll of 6-sided die\n",
    "\n",
    "- number of hours someone spends watching 'Friends':\n",
    "\n",
    "__Event space:__ Some subset of sample space\n",
    "\n",
    "Some event spaces corresponding to above experiments:\n",
    "\n",
    "- Coin flip is heads:\n",
    "\n",
    "- Number of heads is bigger or equal than 1 in flipping two coins experiment:\n",
    "\n",
    "- Event of wasted days:(you spend more than 3 hours watching 'Friends'):\n",
    "\n",
    "### Probability of an Event\n",
    "\n",
    "$$ P(E) = \\lim \\frac{n(E)}{n} $$\n",
    "\n",
    "What this means try the experiment $n$ times and count the number of times the event $E$ occurs ($n(E)$). Ratio as $n$ gets bigger and bigger defines the probability of E.\n",
    "\n",
    "\n",
    "### Python playground\n",
    "Let's simulate the probability of getting one or more heads in the experiment of tossing two coins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# note that you can use multinomial to generate\n",
    "# data from the experiment of flipping two coins\n",
    "experiments = np.random.multinomial(n=2,\n",
    "                                    pvals=[0.5, 0.5],\n",
    "                                    size=10)\n",
    "experiments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prob_of_E(outcomes, num_of_heads):\n",
    "    \"\"\"\n",
    "    :param outcomes: np.array - [experiment_size, n_trials]\n",
    "    :param num_of_heads: int. Event is the getting num_of_heads or more.\n",
    "    :return: float - returns the frequency of event getting num_of_heads or more given outcomes\n",
    "    \"\"\"\n",
    "    n_E = (outcomes[:, 0] >= num_of_heads).sum()\n",
    "    return n_E/len(outcomes)\n",
    "\n",
    "\n",
    "probabilities = []\n",
    "\n",
    "for i in range(1, 10001):\n",
    "    experiment = np.random.multinomial(n=2, pvals=[0.5, 0.5], size=i)\n",
    "    prob = prob_of_E(outcomes=experiment, num_of_heads=1)\n",
    "    probabilities.append(prob)\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "plt.plot(range(1, 10001, 100),\n",
    "         probabilities[::100])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Axioms of Probability\n",
    "\n",
    "- Axiom 1: Probability of an event is always between 0 and 1 (therefore non-negative) \n",
    "\n",
    "$$0 \\leq P(E) \\leq 1$$\n",
    "\n",
    "- Axiom 2: With probability 1, an outcome of an experiment will be an element of the sample space.  \n",
    "\n",
    "$$P(S) = 1$$\n",
    "\n",
    "__Mutually Exclusive Events:__\n",
    "\n",
    "We say two events *E* and _F_ are mutually exclusive if $E\\cap F = \\emptyset$. \n",
    "\n",
    "- Axiom 3: For mutually exclusive events \n",
    "\n",
    "For mutually exclusive events $E, F$ we have $P(E \\cup F) = P(E) + P(F)$.\n",
    "\n",
    "More generally, if $E_1, E_2, \\cdots\\, E_{n}$ are mutually exclusive then we have:\n",
    "\n",
    "$$P \\big(\\bigcup\\limits_{i=1}^{n} E_{i} \\big) = \\sum\\limits_{i=1}^{n} P(E_{i})$$\n",
    "\n",
    "From these axioms we can prove the following properties of the probability: (Try these!)\n",
    "\n",
    "$$ P(E^{c}) = 1- P(E)$$\n",
    "\n",
    "$$ P(\\emptyset) = 0 $$\n",
    "\n",
    "$$ P(E \\cup F) = P(E) + P(F) - P(E \\cap F)$$\n",
    "\n",
    "\n",
    "### Conditional Probability and Independence\n",
    "\n",
    "#### Independent Events\n",
    "\n",
    "Events $A$ and $B$ are independent when the occurrence of $A$ has no effect on whether $B$ will occur (or not).\n",
    " \n",
    "Examples:\n",
    "\n",
    "* Getting heads after flipping a coin **and** getting a 5 after throwing a fair dice\n",
    "* Choosing a marble from a container **and** getting heads after flipping a coin\n",
    "\n",
    "\n",
    "#### Dependent Events\n",
    "\n",
    "\n",
    "Events $A$ and $B$ are dependent when the occurrence of $A$ somehow has an effect on whether $B$ will occur (or not).\n",
    "\n",
    "[Let's see an example of dependent events from learn.co](https://learn.co/tracks/data-science-career-v2/module-3-probability-sampling-and-ab-testing/section-17-combinatorics-and-probability/conditional-probability)\n",
    "\n",
    "\n",
    "#### Conditional Probability\n",
    "\n",
    "\n",
    "Conditional probability emerges when the outcome a trial may influence the results of the upcoming trials.\n",
    "\n",
    "* Drawing a 2nd Ace from a deck of cards given that the first card you drew was an Ace.\n",
    "* Finding the probability of liking \"The Matrix\" given that you know this person likes science fiction.\n",
    "\n",
    "__Notation__: The conditional probability (Probability of $A$ **given** $B$) can be written as:\n",
    "$$ P (A \\mid B) = \\dfrac{P(A \\cap B)}{P(B)}$$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Recap and Exit ticket\n",
    "\n",
    "- Factorials - permutations - combinations\n",
    "\n",
    "- Definition of probability\n",
    "\n",
    "- Axioms of probability\n",
    "\n",
    "- Mutually exclusive events\n",
    "\n",
    "- Independent events\n",
    "\n",
    "- Conditional probability\n",
    "\n",
    "[Exit Ticket](https://forms.gle/j6FQzdAfGGLzRsXc8)\n",
    "\n",
    "\n",
    "\n",
    "[If time allows](https://learn.co/tracks/data-science-career-v2/module-3-probability-sampling-and-ab-testing/section-17-combinatorics-and-probability/introduction-to-probability-lab)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "202.167px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}