Below is the response for Many Flips Quiz from Problem Set 2 - Probability Section in Udacity's Intro to Statistics. An awesome person Mr. Goldsong has given this answer. Unfortunately, Udacity's discussion forums have dropped support for Mathjax long back, so all these replies having latex were messed up in original post. So I have cleaned it u…

goldsong.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:** Below is the response for ```Many Flips``` Quiz from ```Problem Set 2 - Probability``` Section in Udacity's ```Intro to Statistics```. An awesome person Mr. Goldsong has given this answer. Unfortunately, Udacity's discussion forums have dropped support for Mathjax long back, so all these replies having latex were messed up in original post. So I have cleaned it up a little, and re posting so it could be helpful for others. \n",
    "\n",
    "[Original Post link](https://discussions.udacity.com/t/help-me-visualize-many-flips-statements/76150/3)\n",
    "\n",
    "<hr>\n",
    "\n",
    "I rewrote the examples for pts 4 and 5 which were unclear. Thanks to the people that pointed this out. The explanation is now longer but hopefully better and more interesting.\n",
    "\n",
    "### 1 - The probability of every sequence becomes small.\n",
    "\n",
    "The probability of any one sequence is \n",
    "\n",
    "$$\n",
    "\\textstyle\n",
    "\\begin{array}{l}\n",
    "P(\\text {any one sequence}) = \\dfrac{1}{\\text {num permutations}} = \\dfrac{1}{2^{\\text {flips}} }\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "\n",
    "so more flips, smaller probability\n",
    "\n",
    "|# flips    |# cases    |Pr. per case   |possible cases     |\n",
    "|------|------|------|------|\n",
    "|2|$2^2 = 4$|$\\dfrac{1}{4} = 0.25$ |HH, HT, TH, TT|\n",
    "|3|$2^3 = 8$|$\\dfrac{1}{8} = 0.125$|HHH, HHT, HTH, HTT, THH, THT, TTH, TTT|\n",
    "|4|$2^4 = 16$|$\\dfrac{1}{16}= 0.0625$|HHHH, HHHT, HHTH, HHTT, HTHH, HTHT, ...|\n",
    "\n",
    "\n",
    "### 2 - The probability of every number of heads becomes small.\n",
    "\n",
    "This could mean 2 things. One, the total number of heads:\n",
    "\n",
    "\n",
    "P(2 heads) for 2 flips = P(HH) =  $\\dfrac{1}{4}$ = 0.25  \n",
    "P(2 heads) for 3 flips = P(HHT)+P(HTH)+P(THH) = $\\dfrac{1}{8} \\times 3$ = 0.375  \n",
    "P(2 heads) for 4 flips = P(HHTT)+P(HTHT)+P(HTTH) + P(THTH)+P(THHT)+P(TTHH) = $\\dfrac {1}{16} \\times 6$ = 0.375  \n",
    "P(2 heads) for 5 flips = $\\dfrac {1}{32} \\times 10$ = 0.3125  \n",
    "\n",
    "\n",
    "which gets smaller with the number of flips or, two, the number of heads in a sequence, like exactly 2 heads followed by tails, in which case we have:\n",
    "\n",
    "P(2 heads plus tails) for 2 flips = P(HH) = $\\dfrac {1}{4}$  \n",
    "P(2 heads plus tails) for 3 flips = P(HHT) = $\\dfrac {1}{8}$  \n",
    "P(2 heads plus tails) for 4 flips = P(HHTT) = $\\dfrac {1}{16}$  \n",
    "\n",
    "which also gets smaller with the number of flips\n",
    "\n",
    "\n",
    "### 3 - The probability of every proportion of heads becomes small.\n",
    "\n",
    "For example, I want half the flips (i.e., a proportion) to be heads\n",
    "\n",
    "P($\\frac {1}{2}$ of 2 flips are heads) = P(HT) + P(TH) = $\\dfrac {1}{4} + \\dfrac {1}{4}$ = $\\dfrac {1}{2}$  \n",
    "P($\\frac {1}{2}$ of 4 flips are heads) = P(HHTT) + P(HTHT) + P(THTH) + P(THHT)+ P(TTHH) + P(HTTH) = $6 \\times {\\dfrac {1}{2^4}}$  = $\\dfrac {3}{8}$\n",
    "\n",
    "\n",
    "### 4- The probability of every range of proportions becomes small.  \n",
    "\n",
    "ok.. there were several comments about my original explanation of points 4 and 5 being unclear and.. sure enough.. they were. I was not happy with the explanations either so I figured out a way to explain them in a different way without getting too much into combinatorics.\n",
    "\n",
    "\n",
    "First let's figure out the basics. If I flip a coin n times I generate one of $2^n$ sequences. How many of those possible sequences have k heads? One way to find the answer is to use Pascal's triangle, in which an entry in the triangle is the sum of the two entries immediately above it:\n",
    "\n",
    "\n",
    "![image 1](https://s22.postimg.cc/3opgra4qp/image.png)\n",
    "\n",
    "\n",
    "Image from [mathisfun.com](https://www.mathsisfun.com/pascals-triangle.html)\n",
    "\n",
    "\n",
    "The sum of the numbers in any of the rows of the triangle gives the powers of 2: 2, 4, 8, 16, 32, 64, 128.. etc. which correspond to the number of sequences generated by flipping a coin 1, 2, 3, 4, 5, 6, and 7 times, respectively. In other words, if you flip a coin n times, you have any of $2^n$ sequences which is also the sum of the numbers of the n-th row of Pascal's triangle (when the row at the top is the 0-th row).\n",
    "\n",
    "\n",
    "The entries in Pascal's triangle can be interpreted as the number of times that a coin will land in, say, heads. For example, if you flip a coin 4 times, you will get one of $2^4 = 16$ possible sequences. Looking at the 4th row of Pascal's triangle (the one whose entries add up to 16) we have the following correspondance:\n",
    "\n",
    "```\n",
    "1 = # of sequences with 0 heads = TTTT\n",
    "4 = # of sequences with 1 heads = TTTH, TTHT, THTT, HTTT\n",
    "6 = # of sequences with 2 heads = TTHH, THTH, HTTH, THHT, HTHT, HHTT\n",
    "4 = # of sequences with 3 heads = HHHT, HHTH, HTHH, HHHT\n",
    "1 = # of sequences with 4 heads = HHHH\n",
    "```\n",
    "\n",
    "Likewise, if we flip the coin 7 times we will have $2^7 = 128$ cases and, looking at Pascal's triangle,\n",
    "\n",
    "we find that 21 of these sequences have 2 heads, 35 of them have 3 heads, 6 of them have 7 heads, and so on.\n",
    "\n",
    "\n",
    "Another way to find any of the entries of Pascal's triangle is using the binomial coefficient:\n",
    "\n",
    "\n",
    "$$\\binom{n}{k} = \\frac{n!}{k!(n-k)!}$$\n",
    "\n",
    "\n",
    "or $C(n, k)$, for short, where $n!$ is the factorial of n, i.e.,\n",
    "\n",
    "\n",
    "$$ n! = n(n-1)(n-2)\\cdots 2\\cdot 1 $$\n",
    "\n",
    "\n",
    "So, for example, if we want to find how many of the $2^7=128$ sequences generated with 7 flips have 2 heads we have\n",
    "\n",
    "```\n",
    "C(7,2) = 7! / (2! (7-2)!)\n",
    "       = 7! / (2! 5!)\n",
    "       = 5040 / (2 * 120)\n",
    "       = 21\n",
    "```\n",
    "\n",
    "which agrees with the entry in Pascal's triangle.\n",
    "\n",
    "\n",
    "Now back to the question. We are going to consider all of sequences that have less than 50% heads (i.e., the proportion is a given percentage( e.g., 25% heads) while the range of proportions is from 0 to 50%). We'll consider only the odd number of flips that gives us a nice boundary for the 50% bound.\n",
    "\n",
    "```\n",
    "Flips    # sequences  # seqs with [0-50)% heads   P\n",
    "1        2^1 = 2      1 (i.e., H)                 1*(1/2) = 0.5\n",
    "3        2^3 = 8      1+3 = 4                     4*(1/8) = 0.5\n",
    "5        2^5 = 32     1+5+10 = 16                 16*(1/32) = 0.5\n",
    "7        2^7 = 128    1+7+21+35 = 64              64*(1/128) = 0.5\n",
    "etc.\n",
    "```\n",
    "\n",
    "Thus, the probability of the sequences of having less than 50% heads does not get smallerr but instead is constant and, hence, point 4 is False.\n",
    "\n",
    "\n",
    "### 5- The probablity of some ranges of proportions becomes small.  \n",
    "\n",
    "Consider the probability of having sequences in which the proportion of heads is anywhere between 0 and 33%. Here we will use a larger Pascal's triangle that includes the entries for 9 and 12 flips:\n",
    "\n",
    "\n",
    "![image 2](https://s22.postimg.cc/i7wlsr31d/image.png)\n",
    "\n",
    "\n",
    "from [3things.com](http://www.43things.com/people/progress/Surly_Gurl/5361661)\n",
    "\n",
    "\n",
    "So now, we consider sequences of n flips where flips is a multiple of 3, which gives us a nice boundary for the 33%, i.e., a third of the flips or less have to be heads:\n",
    "\n",
    "```\n",
    "Flips    # sequences     # seqs with [0-33]% heads       P\n",
    "3        2^3 = 8         1+3 = 4 (TTT, HTT, THT, TTH)    4/8 = 0.5\n",
    "6        2^6 = 64        1+6+15 = 22                     22/64 = 0.343\n",
    "9        2^9 = 512       1+9+36+84 = 130                 130/512 = 0.254\n",
    "12       2^12 = 4096     1+12+66+220+495 = 794           794/4096 = 0.1938\n",
    "etc.\n",
    "```\n",
    "\n",
    "where, for example, for 12 flips we have 1 flip with 0 heads, 12 with 1 head, 66 with 2 heads, 220 with 3 heads and 495 with 4 heads, i.e., up to 33% of the possible 12 flips.\n",
    "\n",
    "\n",
    "A way to visualize this is the following. Look at the numbers that correspond to the 33%: 3 in the 3rd row, 15 in the 6th, 84 in the 9th and 495 in the 12th. Now, notice that all these numbers lie along a line that passes through the apex of the Pascal triangle. You could imagine continuing this line downwards, as you add more and more flips. For all these rows, all the entries to the left of this line correspond to sequences that have between 0 and 33% heads. However, notice that the values of these entries is progressively smaller with respect to those that accumulate in the middle of the rows. Thus, the larger the flip, the smaller the percentage of sequences that will have between 0-33% heads.\n",
    "\n",
    "\n",
    "By the same token, the entries to the right of the line, which correspond fo the 33-100% heads case, have a number of heads that increases with the number of flips; this is expected as the 0-33% case is the complement of 33-100% case, i.e., if one becomes larger, the other one should become smaller.\n",
    "\n",
    "\n",
    "You can 'swing' this line to the right, about the apex, until it is vertical. Now the triangle is split in equal parts and the entries on the left and right have the same values. Hence, at this point, the number of sequences that have 0-50% heads is exactly the same as those that have 50-100% heads. This was the case used in point 4 to show that not all range of proportions becomes smaller.\n",
    "\n",
    "\n",
    "In summary, the probabiity of the sequences that have 33% or less heads (i.e., a range of proportions) grows smaller with the number of flips and point 5 is True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:Anaconda3]",
   "language": "python",
   "name": "conda-env-Anaconda3-py"
  },
  "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}