prob/central_limit_theorem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Central Limit Theorem (CLT)\n",
    "\n",
    "## Definition:\n",
    "Let $X_{1}$, $X_{2}$, $X_{3}$,... be i.i.d random variables from some distribution with finite mean $\\mu$ and finite variance $\\sigma^{2}$. \n",
    "\n",
    "As $n \\rightarrow \\infty$, let $S=\\sum_{k=1}^n X_{i}$, we have $S \\rightarrow \\mathcal{N}(n\\mu, n\\sigma^{2})$ and $\\frac{S-n\\mu}{\\sqrt{n\\sigma^{2}}} \\rightarrow \\mathcal{N}(0,1)$\n",
    "\n",
    "Equivalently, let $M=\\frac{1}{n}\\sum_{k=1}^n X_{i}$, we have\n",
    "$M \\rightarrow \\mathcal{N}(\\mu,\\frac{\\sigma^2}{n})$ and $\\frac{M-\\mu}{\\sqrt{\\frac{\\sigma^2}{n}}} \\rightarrow \\mathcal{N}(0,1)$\n",
    "\n",
    "\n",
    "Notation:\n",
    " - $\\mathcal{N}(\\mu,\\sigma^2)$ denotes [Normal distribution](https://en.wikipedia.org/wiki/Normal_distribution) with mean of $\\mu$ and variance of $\\sigma^2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Discussions:\n",
    "\n",
    "Naturally CLT appears in questions that invovle sum or average of a large number of random variablse and especially when the questions only ask for an approximate answer. \n",
    "\n",
    "Here are a few examples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<br>\n",
    "***Example 1:***\n",
    "\n",
    "Suppose we have a fair coin and we flip it 400 times. What is the probability you will see 210 heads or more?\n",
    "\n",
    "---\n",
    "\n",
    "<br>\n",
    "**Exact answer**\n",
    "\n",
    "Let the outcome of each coin flip be a random variable $I_{i}$. Thus we are dealing with the random variable $S=\\sum_{i=1}^{400}I_{i}$. $S$ is te sume of a series of i.i.d Bernoulie trials, thus it follows Binomial distribution. So the exact answer is: $P(S\\geq210)= \\sum_{k=210}^{400}C_{400}^{k}\\left(\\frac{1}{2}\\right)^{400}$ which requires a program to calculate (Actually try implementing this, beware of roudoff errors and compare it against the approximate answer below.).\n",
    "\n",
    "\n",
    "Notation:\n",
    " - $C_{n}^{k}$ is the notation for \"[n choose k](https://en.wikipedia.org/wiki/Binomial_coefficient)\", which denotes the number of ways to choose k items from n items where order doesn't matter.\n",
    "\n",
    "<br>\n",
    "**Approximation**\n",
    "\n",
    "We use CLT to easily get an approxmate answer quickly. First recognize that for each $I_{i}$ we have $\\mu=0.5$ and $\\sigma^2=0.5\\times(1-0.5)=0.25$. Then, $Z=\\frac{S-400*0.5}{\\sqrt{400*0.25}}=\\frac{S-200}{10}$ is approximately $\\mathcal{N}(0,1)$. For $S \\geq 210$, we have $Z\\geq1$. \n",
    "\n",
    "The 68-95-99.7 rule tells us that for a standard Normal distribution $\\mathcal{N}(0,1)$, the probability of the random variable taking value more than 1 standard deviation away from the center is $1-0.68=0.32$ and thus the one sided probability for $P(Z\\geq1) = 0.32/2 = 0.16$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "***Example 2:***\n",
    "\n",
    "Suppose you use Monte Carlo simulation to estimate the numerical value of $\\pi$.\n",
    "- How would you implement it? \n",
    "- If we require an error of 0.001, how many trials do you need?\n",
    "\n",
    "---\n",
    "\n",
    "**Solution**\n",
    "\n",
    "One possible implementation is to start with a rectangle, say $x \\in [-1,1], y\\in[-1,1]$. If we uniformly randomly draw a point from this rectangle, the probability $p$ of the point following into the circle region $x^2+y^2\\lt1$ is the ratio of the area between the circle and rectangle, i.e $p=\\frac{\\pi}{4}$\n",
    "\n",
    "Formally, let random indicator variable $I$ take value 1 if the point falls in the circle and 0 otherwise, then $P(I=1)=p$ and $E(I)=p$. If we do $n$ such trials, and define $M=\\frac{1}{n}\\sum_{k=1}^n I_{k}$, then $M$ follows approximately $\\mathcal{N}(\\mu_{I},\\frac{\\sigma_{I}^2}{n})$. In this setup, $\\mu_{I}=E(I)=p$ and $\\sigma_{I}^2=p(1-p)$ (see [Probability Distribution](prob-dist-discrete.ipynb) section for details on $\\sigma_{I}^2$).\n",
    "\n",
    "One thing we need to clarify with the interviewer is what error really means? She might tell you to consider it as the standard deviation of the estimated $\\pi$. Therefore the specified error translates into a required sigma of $\\sigma_{req}=\\frac{error}{4}$ for random variable $M$. Thus $n = \\frac{\\sigma_{I}^2}{\\sigma_{req}^2}=\\frac{p(1-p)}{(0.00025)^2}\\approx2.7\\times 10^6$.\n",
    "\n",
    "By the way, we can see that the number of trials $n$ scales with $\\frac{1}{error^2}$, which is caused by the $\\frac{1}{\\sqrt{n}}$ scaling of the $\\sigma_{M}$ in the CLT, and is generally the computationaly complexity entailed by [Monte Carlo integration](https://en.wikipedia.org/wiki/Monte_Carlo_integration).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}