permute.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Permutation Tests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic idea: \n",
    "\n",
    "If, under the null hypothesis, the probability distribution of the data is invariant under the action of some group $\\mathcal{G}$, then once we observe the actual data, we know other possible data sets that are equally likely.\n",
    "\n",
    "In particular, every element of the _orbit_ of the observed data under $\\mathcal{G}$ was just as probable as the\n",
    "observed data.\n",
    "\n",
    "Test _conditionally_ on the orbit in which the observed data lie."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Groups\n",
    "<hr />\n",
    "### Definition\n",
    "A _group_ is an ordered pair $({\\mathcal G}, \\times)$, where ${\\mathcal G}$ is\n",
    "a collection of objects (the elements of the group) and $\\times$ is a mapping\n",
    "from ${\\mathcal G} \\bigotimes {\\mathcal G}$ onto ${\\mathcal G}$,\n",
    "$$\n",
    "\\times : {\\mathcal G} \\bigotimes {\\mathcal G} \\rightarrow {\\mathcal G} \\\\\n",
    "(a, b) \\mapsto a \\times b,\n",
    "$$\n",
    "satisfying the following axioms:\n",
    "\n",
    "+ $\\exists e \\in {\\mathcal G}$ s.t. $\\forall a \\in {\\mathcal G}$, $e \\times a = a$.\n",
    "The element $e$ is called the _identity_.\n",
    "+ For each $a \\in {\\mathcal G}$, $\\exists a^{-1} \\in {\\mathcal G}$ s.t. $a^{-1}\\times a = e$.\n",
    "(Every element has an inverse.)\n",
    "+ If $a, b, c \\in {\\mathcal G}$, then $a \\times (b \\times c) = (a \\times b)\\times c$.\n",
    "(The group operation is associative.)\n",
    "\n",
    "If, in addition, for every $a, b \\in {\\mathcal G}$,  $a \\times b = b \\times a$ (if the group\n",
    "operation commutes), we say that $({\\mathcal G}, \\times)$ is an _Abelian group_\n",
    "or _commutative group_.\n",
    "<hr />\n",
    "\n",
    "Examples of groups include the real numbers together with ordinary addition, $({\\mathbf R}, +)$;\n",
    "the real numbers other than zero together with ordinary multiplication,\n",
    "$(\\Re \\setminus \\{0\\}, \\times)$; the rational numbers together with ordinary addition,\n",
    "$({\\mathbf Q}, +)$; and the integers 0 to $p-1$, $p$ prime, together with addition modulo $p$,\n",
    "$( \\{0, 1, \\ldots, p-1\\}, +)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example: Effect of treatment in a randomized controlled experiment\n",
    "\n",
    "11 pairs of rats, each pair from the same litter.  \n",
    "\n",
    "Randomly---by coin tosses---put one of each pair into\n",
    "``enriched'' environment; other sib gets ''normal'' environment.\n",
    "\n",
    "After 65 days, measure cortical mass (mg).\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "<td> enriched </td><td> 689 </td><td> 656 </td><td> 668 </td><td> 660 </td><td> 679 </td><td> 663 </td><td> 664 </td><td> 647 </td><td> 694 </td><td> 633 </td><td>653 </td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td> impoverished </td><td> 657</td><td> 623</td><td> 652</td><td> 654</td><td> 658</td><td> 646</td><td> 600</td><td> 640</td><td> 605</td><td> 635</td><td> 642 </td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td> difference </td><td> 32</td><td>  33</td><td>  16</td><td>   6</td><td>  21</td><td>  17</td><td>  64</td><td>   7</td><td>  89</td><td>  -2</td><td>  11\n",
    "</tr>\n",
    "</table>\n",
    "\n",
    "**How should we analyze the data?**\n",
    "\n",
    "Cartoon of Rosenzweig, M.R., E.L. Bennet, and M.C. Diamond, 1972. Brain changes in response to experience, _Scientific American_, _226_, 22&ndash;29 report an experiment in which 11 triples of male rats, each triple from the same litter, were\n",
    "assigned at random to three different environments, \"enriched\" (E), standard, and \"impoverished.\"\n",
    "See also Bennett et al., 1969. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Informal Hypotheses\n",
    "\n",
    "Null hypothesis: treatment has \"no effect.\"\n",
    "\n",
    "Alternative hypothesis: treatment increases cortical mass.\n",
    "\n",
    "Suggests 1-sided test for an increase."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test contenders\n",
    "\n",
    "+ 2-sample Student $t$-test: \n",
    "$$ \n",
    "              \\frac{\\mbox{mean(treatment) - mean(control)}}\n",
    "                   {\\mbox{pooled estimate of SD of difference of means}}\n",
    "$$\n",
    "+ 1-sample Student $t$-test on the differences: \n",
    "$$\n",
    "\t      \\frac{\\mbox{mean(differences)}}{\\mbox{SD(differences)}/\\sqrt{11}}\n",
    "$$  \n",
    "Better, since littermates are presumably more homogeneous.\n",
    "              \n",
    "+ Permutation test using $t$-statistic of differences:\n",
    "same statistic, different way to calculate $P$-value.\n",
    "Even better?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Strong null hypothesis\n",
    "\n",
    "**Treatment has no effect whatsoever---as if cortical mass were \n",
    "assigned to each rat before the randomization.**\n",
    "\n",
    "Then equally likely that the rat with the heavier cortex will be assigned\n",
    "to treatment or to control, independently across littermate pairs.\n",
    "\n",
    "Gives $2^{11} = 2,048$ equally likely possibilities:\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "<td>difference </td><td> $\\pm$32 </td><td> $\\pm$33 </td><td> $\\pm$16 </td><td> $\\pm$6 </td><td> $\\pm$21 </td><td> $\\pm$17 </td><td> $\\pm$64 </td><td> $\\pm$7 </td><td> $\\pm$89 </td><td> $\\pm$2 </td><td> $\\pm$11 </td>\n",
    "</tr>\n",
    "</table>\n",
    "\n",
    "For example, just as likely to observe original differences as\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "\t<td>difference </td><td>-32 </td><td> -33 </td><td> -16 </td><td> -6 </td><td> -21 </td><td> -17 </td><td>\n",
    "    -64</td><td> -7 </td><td> -89 </td><td> -2 </td><td> -11</td>\n",
    "</tr>\n",
    "</table>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Weak null hypothesis\n",
    "\n",
    "On average across pairs, treatment makes no difference."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Alternatives\n",
    "\n",
    "1. Individual's response depends only on that individual's assignment\n",
    "    + Special cases: shift, scale, etc.\n",
    "\n",
    "1. Interactions/Interference: my response could depend on whether you are assigned to treatment or control."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Assumptions of the tests\n",
    "\n",
    "1. 2-sample $t$-test: \n",
    "    + masses are iid sample from normal distribution, same unknown variance, same unknown mean.\n",
    "\t+ Tests weak null hypothesis (plus normality, independence, non-interference, etc.).\n",
    "1. 1-sample $t$-test on the differences: \n",
    "\t+ mass differences are iid sample from normal distribution, unknown variance, zero mean.\n",
    "\t+ Tests weak null hypothesis (plus normality, independence, non-interference, etc.)\n",
    "1. Permutation test: \n",
    "\t+ Randomization fair, independent across pairs.\n",
    "\t+ Tests strong null hypothesis.\n",
    "\n",
    "Assumptions of the permutation test are true by design: That's how treatment\n",
    "was assigned."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What's the group?\n",
    "\n",
    "The data are elements of $\\Re^{11}$. The group operations reflect coordinates\n",
    "about the axes&mdash;they flip the signs of elements of the vectors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Ttest_1sampResult(statistic=3.2437214037805222, pvalue=0.0088136932072599358)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# boilerplate\n",
    "%matplotlib inline\n",
    "from __future__ import division\n",
    "import math\n",
    "import numpy as np\n",
    "import scipy as sp\n",
    "from scipy import stats  # distributions\n",
    "from scipy import special # special functions\n",
    "from scipy import random # random variables, distributions, etc.\n",
    "from scipy.optimize import brentq\n",
    "from scipy.stats import (binom, hypergeom)\n",
    "import matplotlib.pyplot as plt\n",
    "from ipywidgets import widgets\n",
    "\n",
    "treat = np.array([689, 656, 668, 660, 679, 663, 664, 647, 694, 633, 653])\n",
    "control = np.array([657, 623, 652, 654, 658, 646, 600, 640, 605, 635, 642])\n",
    "diffr = treat - control\n",
    "\n",
    "sp.stats.ttest_1samp(diffr, 0.0)  # two-sided one-sample t-test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Student $t$-test calculations\n",
    "\n",
    "Mean of differences:  26.73mg  \n",
    "Sample SD of differences:  27.33mg  \n",
    "$t$-statistic: $26.73/(27.33/\\sqrt{11}) = 3.244$. \n",
    "\n",
    "$P$-value for 2-sided $t$-test:  0.0088\n",
    "\n",
    "+ Why do cortical weights have normal distribution?\n",
    "+ Why is variance of the difference between treatment and control the same for different litters?\n",
    "+ Treatment and control are _dependent_ because assigning a rat to treatment excludes it from the control group, and vice versa.\n",
    "+ $P$-value depends on assuming differences are iid sample from a normal distribution.\n",
    "+ If we reject the null, is that because there is a treatment effect, or because the other assumptions are wrong?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Permutation $t$-test calculations\n",
    "\n",
    "Could enumerate all $2^{11} = 2,048$ equally likely possibilities.\n",
    "Calculate $t$-statistic for each.\n",
    "\n",
    "$P$-value is \n",
    "$$\n",
    "\tP = \\frac{\\mbox{number of possibilities with $t \\ge 3.244$}}{\\mbox{2,048}}\n",
    "$$\n",
    "(Using the mean as the test statistic instead of $t$-statistic\n",
    "would yield $P = 2/2048 =  0.00098$.)\n",
    "\n",
    "If there were many more pairs, it would be impractical to enumerate, but \n",
    "we can simulate:\n",
    "\n",
    "Assign a random sign to each difference. \\\\\n",
    "Compute $t$-statistic \\\\\n",
    "Repeat $N$ times\n",
    "$$\n",
    "\tP \\approx \\frac{\\mbox{number of simulations with $t \\ge 3.244$}}{N}\n",
    "$$\n",
    "Can invert Binomial tests to make an exact confidence interval for $P$ from the simulation results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.00175 175.0\n"
     ]
    }
   ],
   "source": [
    "np.random.RandomState(seed=20151013)  # set seed for reproducibility\n",
    "\n",
    "iter = 100000  # N\n",
    "def simPermuTP(z, iter):\n",
    "# P.B. Stark, statistics.berkeley.edu/~stark \n",
    "# simulated P-value for 2-sided 1-sample t-test under the \n",
    "# randomization model.\n",
    "    tsf = lambda(x): np.abs(np.mean(x)/(np.std(x, ddof=1)/math.sqrt(len(x))))\n",
    "    ts = tsf(z) \n",
    "    return np.mean([ (tsf(z*(2*np.random.random_integers(0, 1, size=len(z))-1)) >= ts) for i in range(iter)])\n",
    "    \n",
    "estP = simPermuTP(diffr, iter)\n",
    "print estP, estP*iter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.0015004985018112961, 0.0020290732328088075)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# confidence interval for the p-value\n",
    "# This function is in the _permute_ library; see http://statlab.github.io/permute/\n",
    "\n",
    "def binom_conf_interval(n, x, cl=0.975, alternative=\"two-sided\", p=None,\n",
    "                        **kwargs):\n",
    "    \"\"\"\n",
    "    Compute a confidence interval for a binomial p, the probability of success in each trial.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    n : int\n",
    "        The number of Bernoulli trials.\n",
    "    x : int\n",
    "        The number of successes.\n",
    "    cl : float in (0, 1)\n",
    "        The desired confidence level.\n",
    "    alternative : {\"two-sided\", \"lower\", \"upper\"}\n",
    "        Indicates the alternative hypothesis.\n",
    "    p : float in (0, 1)\n",
    "        Starting point in search for confidence bounds for probability of success in each trial.\n",
    "    kwargs : dict\n",
    "        Key word arguments\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    tuple\n",
    "        lower and upper confidence level with coverage (approximately)\n",
    "        1-alpha.\n",
    "\n",
    "    Notes\n",
    "    -----\n",
    "    xtol : float\n",
    "        Tolerance\n",
    "    rtol : float\n",
    "        Tolerance\n",
    "    maxiter : int\n",
    "        Maximum number of iterations.\n",
    "    \"\"\"\n",
    "    assert alternative in (\"two-sided\", \"lower\", \"upper\")\n",
    "\n",
    "    if p is None:\n",
    "        p = x / n\n",
    "    ci_low = 0.0\n",
    "    ci_upp = 1.0\n",
    "\n",
    "    if alternative == 'two-sided':\n",
    "        cl = 1 - (1-cl)/2\n",
    "\n",
    "    if alternative != \"upper\" and x > 0:\n",
    "        f = lambda q: cl - binom.cdf(x - 1, n, q)\n",
    "        ci_low = brentq(f, 0.0, p, *kwargs)\n",
    "    if alternative != \"lower\" and x < n:\n",
    "        f = lambda q: binom.cdf(x, n, q) - (1 - cl)\n",
    "        ci_upp = brentq(f, 1.0, p, *kwargs)\n",
    "\n",
    "    return ci_low, ci_upp\n",
    "\n",
    "binom_conf_interval(iter, math.ceil(estP*iter), cl=0.95, alternative=\"two-sided\", p=estP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Other tests: sign test, Wilcoxon signed-rank test\n",
    "\n",
    "#### Sign test:\n",
    "Count pairs where treated rat has heavier cortex, i.e., where\n",
    "difference is positive.\n",
    "\n",
    "Under strong null, distribution of the number of positive differences\n",
    "is Binomial(11, 1/2).  Like number of heads in 11 independent tosses\n",
    "of a fair coin.  (Assumes no ties w/i pairs.)\n",
    "\n",
    "$P$-value is chance of 10 or more heads in 11 tosses of a fair coin: 0.0059.\n",
    "\n",
    "Only uses signs of differences, not information that only the smallest absolute \n",
    "difference was negative.\n",
    "\n",
    "#### Wilcoxon signed-rank test\n",
    "uses information about the ordering of the\n",
    "differences: rank the absolute values of the differences, then give them\n",
    "the observed signs and sum them.  Null distribution: assign signs at random\n",
    "and sum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Still more tests, for other alternatives\n",
    "\n",
    "All the tests we've seen here are sensitive to _shifts_--the alternative\n",
    "hypothesis is that treatment increases response (cortical mass).\n",
    "\n",
    "There are also nonparametric tests that are sensitive to other\n",
    "treatment effects, e.g., treatment increases the variability of the \n",
    "response.\n",
    "\n",
    "And there are tests for whether treatment has any effect at all on\n",
    "the distribution of the responses.\n",
    "\n",
    "You can design a test statistic to be sensitive to any change that\n",
    "interests you, then use the permutation distribution to get a $P$-value\n",
    "(and simulation to approximate that $P$-value)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Silliness\n",
    "\n",
    "Treat ordinal data (e.g., Likert scale) as if measured on a linear scale; \n",
    "use Student $t$-test.\n",
    "\n",
    "Maybe not so silly for large samples$\\ldots$\n",
    "\n",
    "$t$-test asymptotically distribution-free.\n",
    "\n",
    "How big is big?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Back to Rosenzweig et al.\n",
    "\n",
    "Actually had 3 treatments:  enriched, standard, deprived.\n",
    "\n",
    "Randomized 3 rats per litter into the 3 treatments, independently across\n",
    "$n$ litters.\n",
    "\n",
    "**How should we analyze these data?**\n",
    "\n",
    "\n",
    "\n",
    "### Test contenders\n",
    "\n",
    "$n$ litters, $s$ treatments (sibs per litter).\n",
    "+ ANOVA--the $F$-test:\n",
    "$$ \n",
    "F = \\frac{\\mbox{BSS}/(s-1)}{\\mbox{WSS}/(n-s)}\n",
    "$$\n",
    "+ Permutation $F$-test: use permutation distribution instead of $F$ distribution to get $P$-value.\n",
    "+ Friedman test: Rank within litters. Mean rank for treatment $i$ is $\\bar{R}_i$.\n",
    "$$ \n",
    "Q = \\frac{12n}{s(s+1)} \\sum_{i=1}^s \\left ( \\bar{R}_i - \\frac{s+1}{2} \\right )^2.\n",
    "$$\n",
    "$P$-value from permutation distribution. \n",
    "\n",
    "### Strong null hypothesis\n",
    "\n",
    "**Treatment has no effect whatsoever&mdash;as if cortical mass were \n",
    "assigned to each rat before the randomization.**\n",
    "\n",
    "Then it's equally likely that each littermate is assigned to each treatment, \n",
    "independently across litters.\n",
    "\n",
    "There are $3! = 6$ assignments of each triple to treatments. Thus, there $6^n$ equally likely assignments across all litters.\n",
    "\n",
    "For 11 litters, that's 362,797,056 possibilities.\n",
    "\n",
    "(The group under which the distribution of the data is invariant is a subgroup of the permutation group: if you think of the data as an element of $\\Re^{33}$ (33 rats), the group consists of all permutations of the 33 elements that shuffle only adjacent sets of 3 components: components 1&ndash;3, components 4&ndash;6, &hellip; components 31&ndash;33.)\n",
    "\n",
    "\n",
    "### Weak null hypothesis\n",
    "\n",
    "**The average cortical weight for all three treatment groups are equal.\n",
    "On average across triples, treatment makes no difference.**\n",
    "\n",
    "### Assumptions of the tests\n",
    "\n",
    "+ $F$-test: masses are iid sample from normal distribution, same unknown variance, same unknown mean for all litters and treatments.  \n",
    "Tests weak null hypothesis.\n",
    "+ Permutation $F$-test: Randomization was as advertised: fair, independent across triples.  \n",
    "Tests strong null hypothesis.\n",
    "+ Friedman test: Ditto.\n",
    "\n",
    "Assumptions of the permutation test and Friedman test are true by design: \n",
    "that's how treatment was assigned.\n",
    "\n",
    "Friedman test statistic has  $\\chi^2$ distribution asymptotically.  Ties are a complication."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### $F$-test assumptions&mdash;reasonable?\n",
    "\n",
    "+ Why do cortical weights have normal distribution for each litter and for each treatment?\n",
    "+ Why is the variance of cortical weights the same for different litters?\n",
    "+ Why is the variance of cortical weights the same for different treatments?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is $F$ a good statistic for this alternative?\n",
    "\n",
    "$F$-test (and Friedman statistic) sensitive to differences among the \n",
    "mean responses for each treatment group, no matter what pattern the differences \n",
    "have.\n",
    "\n",
    "But the treatments and the responses can be ordered: we hypothesize that\n",
    "more stimulation produces greater cortical mass.\n",
    "\n",
    "deprived $\\Longrightarrow$  normal  $\\Longrightarrow$  enriched   \n",
    "low mass  $\\Longrightarrow$  medium mass  $\\Longrightarrow$  high mass\n",
    "\n",
    "_Can we use that to make a more sensitive test?_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A test against an ordered alternative\n",
    "\n",
    "Within each litter triple, count pairs of responses\n",
    "that are \"in order.\"  Sum across litters.\n",
    "\n",
    "E.g., if one triple had cortical masses\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "<td>deprived </td><td> 640 </td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>normal </td><td> 660 </td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>enriched </td><td>  650 </td>\n",
    "</table>\n",
    "\n",
    "that would contribute 2 to the sum: $660 \\ge 640$, $650 \\ge 640$, but $640 < 650$.\n",
    "\n",
    "Each litter triple contributes between 0 and 3 to the overall sum.\n",
    "\n",
    "\n",
    "Null distribution for the test based on the permutation distribution: 6\n",
    "equally likely assignments per litter, independent assignments across litters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A different test against an ordered alternative\n",
    "\n",
    "Within each litter triple, add differences\n",
    "that are \"in order.\"  Sum across litters.\n",
    "\n",
    "E.g., if one triple had cortical masses\n",
    "\n",
    "<table>\n",
    "<tr>\n",
    "<td>deprived </td><td> 640 </td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>normal </td><td> 660 </td>\n",
    "</tr>\n",
    "<tr>\n",
    "<td>enriched </td><td>  650 </td>\n",
    "</table>\n",
    "\n",
    "that would contribute 30 to the sum: $660 - 640 = 20$ and $650 - 640 = 10$, but $640 < 650$,\n",
    "so that pair contributes zero.\n",
    "\n",
    "Each litter triple contributes between 0 and $2\\times{\\mbox{ range }}$ to the sum.\n",
    "\n",
    "Null distribution for the test based on the permutation distribution: 6\n",
    "equally likely assignments per litter, independent across litters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The 2-sample problem \n",
    "\n",
    "Suppose we have a group of $N$ individuals who are randomized into two groups, a _treatment_ group of size $N_t$ and a _control_ group of size $N_c = N - N_t$.\n",
    "Label the individuals from $1$ to $N$.\n",
    "Let ${\\mathcal T}$ denote the labels of individuals assigned to treatment and ${\\mathcal C}$ denote \n",
    "the labels of those assigned to control.\n",
    "\n",
    "For each of the $N$ individuals, we measure a quantitative (real-valued) response.\n",
    "Each individual $i$ has two _potential responses_: the response $c_i $individual would have if assigned to \n",
    "the control group, and the response $t_i$ the individual would have if assigned to the treatment group.\n",
    "\n",
    "We assume that individual $i$'s response depends _only_ on that individual's assigment, and not on anyone else's assignment.\n",
    "This is the assumption of _non-interference_. \n",
    "In some cases, this assumption is reasonable; in others, it is not.\n",
    "\n",
    "For instance, imagine testing a vaccine for a communicable disease.\n",
    "If you and I have contact, whether you get the disease might depend on whether I am vaccinated&mdash;and _vice versa_&mdash;since if the vaccine protects me from illness, I won't infect you.\n",
    "Similarly, suppose we are testing the effectiveness of an advertisement for a product.\n",
    "If you and I are connected and you buy the product, I might be more likely to buy it, even if I don't\n",
    "see the advertisement.\n",
    "\n",
    "Conversely, suppose that \"treatment\" is exposure to a carcinogen, and the response whether the\n",
    "subject contracts cancer. \n",
    "On the assumption that cancer is not communicable, my exposure and your disease\n",
    "status have no connection.\n",
    "\n",
    "The _strong null hypothesis_ is that individual by individual, treatment makes no difference whatsoever: $c_i = t_i$ for all $i$.\n",
    "\n",
    "If so, any differences between statistics computed for the treatment and control groups are entirely due to the luck of the draw: which individuals happened to be assigned to treatment and which to control.\n",
    "\n",
    "We can find the _null distribution_ of any statistic computed from the responses of the two groups: if the strong null hypothesis is true, we know what individual $i$'s response would have been whether assigned to treatment or to control&mdash;namely, the same.\n",
    "\n",
    "For instance, suppose we suspect that treatment tends to increase response: in general, $t_i \\ge c_i$.\n",
    "Then we might expect $\\bar{c} = \\frac{1}{N_c} \\sum_{i \\in {\\mathcal C}} c_i$ to be less than\n",
    "$\\bar{t} = \\frac{1}{N_t} \\sum_{i \\in {\\mathcal T}} t_i$.\n",
    "How large a difference between $\\bar{c}$ and $\\bar{t}$ would be evidence that treatment increases the response,\n",
    "beyond what might happen by chance through the luck of the draw?\n",
    "\n",
    "This amounts to asking whether the observed difference in means between the two groups is a high percentile\n",
    "of the distribution of that difference in means, calculated on the assumption that the null hypothesis is true.\n",
    "\n",
    "Because of how subjects are assigned to treatment or to control, all allocations of $N_t$ subjects to\n",
    "treatment are equally likely.\n",
    "\n",
    "One way to partition the $N$ subjects randomly into a group of size $N_c$ and a group of size $N_t$ is\n",
    "to permute the $N$ subjects at random, then take the first $N_c$ in the permuted list to be the control\n",
    "group, and the remaining $N_t$ to be the treatment group."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aside: Random number generation and simulation\n",
    "\n",
    "Most computers cannot generate true random numbers (there are rare exceptions that have _hardware random\n",
    "number generators_).\n",
    "Instead, they generate _psdudo-random numbers_ using algorithms called _pseudo-random number generators_ (PRNGs).\n",
    "PRNGs are deterministic, but the sequence of numbers they generate can behave like random numbers for\n",
    "some purposes&mdash;depending on the PRNG and the purpose.\n",
    "\n",
    "Older languages, operating systems, and non-statistical software (including Excel) tend to use low-quality\n",
    "PRNGs that are not suitable for statistical inference.\n",
    "\n",
    "A _linear congruential generator_ makes sequences of the form\n",
    "\n",
    "$$ X_{n+1} = ( a X_n + c ) \\mbox{ mod } m,$$\n",
    "\n",
    "with $m > 0$, $0 \\le c < m$, $0 < a < m$, and \"seed\" $X_0$.\n",
    "This generator has the benefit of simplicity, but the quality is not adequate for statistics.\n",
    "Moreover, for some choices of $a$, $c$, and $m$, this can have especially poor behavior.\n",
    "One particularly bad generator, <span class=\"code\">RANDU</span>, was used on IBM mainframes in the 1960s.\n",
    "It has $m = 2^{31}$, $c=0$, and $a = 65539$.\n",
    "It generates sequences with a very strong correlation: if you plot triples of numbers it generates\n",
    "as points in $\\Re^3$, the numbers line up on 15 planes.\n",
    "Despite the fact that problems with this generator were already known in the early 1960s,\n",
    "it was implemented in the IBM/360 in the 1970s and widely promulgated.\n",
    "(See Marsaglia, G., 1968. Random numbers fall mainly in the planes. _PNAS_, _61_ 25-28. http://www.pnas.org/content/61/1/25.full.pdf)\n",
    "Many scientific \"results\" are now in question because they relied on <span class=\"code\">RANDU</span>.\n",
    "\n",
    "The Wichmann-Hill generator (published in 1982)\n",
    "was popular for a while; it combines three linear congruential generators.\n",
    "Excel purported to implement it, but at least through 2008, its implementation had bugs.\n",
    "(For instance,\n",
    "despite the fact that the Wichmann-Hill generator gives numbers between 0 and 1, the Excel\n",
    "PRNG occasionally gave negative numbers.\n",
    "See McCullough, B.D., 2008. Microsoft's 'Not the Wichmann-Hill' random number generator. _Computational Statistics and Data Analysis_, _52_, 4587&ndash;4593.)\n",
    "\n",
    "Current high-end statistics packages and programming languages (e.g., R, Python, SAS, MATLAB) use the Mersenne Twister\n",
    "PRNG.\n",
    "The Mersenne Twister has a very long period ($2^{19937}-1$) and passed the [DIEHARD tests](https://en.wikipedia.org/wiki/Diehard_tests) for equidistribution, etc.\n",
    "However, it is not adequate for cryptography (the _state space_ is so small that its future values can be predicted\n",
    "from a relatively small number of observations).\n",
    "_Linear congruential_ generators are generally not adequate for statistics.\n",
    "In particular, beware the algorithms in _Numerical Recipes_ and the Excel PRNG."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Random sampling\n",
    "\n",
    "One standard way to draw a (pseudo-)random sample from a list is to assign a pseudo-random number to each\n",
    "element of the list, then sort the list by those numbers.\n",
    "Thus, the first element of the sample is the element of the list that was assigned the smallest number,\n",
    "the second element of the sample is the list element assigned the second-smallest number, etc.\n",
    "This generates a random sample in the same way that shuffling cards well generates random \"hands\" of cards.\n",
    "\n",
    "Formally, this is fine, but PRNGs have limitations.\n",
    "Even the Mersenne Twister runs into trouble generating random permutations of long vectors using the naiive approach (assign a random number to each element of the vector, then sort by those numbers).\n",
    "The period of the Mersenne Twister is about $4 \\times 10^{6002}$. \n",
    "That's less than the number of\n",
    "permutations of 2081 objects.\n",
    "\n",
    "### The Knuth Shuffle\n",
    "\n",
    "Constructing a random permutation as described above is inefficient, in part because it requires sorting.\n",
    "The _Knuth Shuffle_ is more efficient and can generate a random permutation in place.\n",
    "The Knuth shuffle goes through the list, randomly swapping the current element\n",
    "with elements above it in the list (or leaving it in place).\n",
    "That is, item $i$ is swapped with item $j \\le i$ with probability $1/i$\n",
    "(swapping item $i$ with item $i$ leaves it in place, of course)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gender Bias in Teaching Evaluations\n",
    "MacNell, Driscoll, and Hunt (2014. [What's in a Name: Exposing Gender Bias in Student Ratings of Teaching](http://link.springer.com/article/10.1007%2Fs10755-014-9313-4), _Innovative Higher Education_) conducted a controlled, randomized experiment on\n",
    "the effect of students' perception of instructors' gender on teaching evaluations\n",
    "in an online course.\n",
    "Students in the class did not know the instructors' true genders.\n",
    "\n",
    "MacNell et al. randomized 47 students in an online course into four groups: two taught by a female\n",
    "instructor and two by a male instructor.\n",
    "One of the groups taught by each instructor was led to believe the instructor was male;\n",
    "the other was led to believe the instructor was female.\n",
    "Comparable instructor biographies were given to all students.\n",
    "Instructors treated the groups identically, including returning assignments at the same time.\n",
    "\n",
    "When students thought the instructor was female, the responding students rated the instructor lower, on average,\n",
    "in every regard.\n",
    "\n",
    "<table>\n",
    "<tr><th>Characteristic</th> <th>F - M</th></tr>\n",
    "<tr><td>Caring</td><td> -0.52</td></tr>\n",
    "<tr><td> Consistent</td><td> -0.47</td></tr>\n",
    "<tr><td> Enthusiastic</td><td> -0.57</td></tr>\n",
    "<tr><td> Fair </td><td>-0.76</td></tr>\n",
    "<tr><td> Feedback</td><td> -0.47</td></tr>\n",
    "<tr><td> Helpful</td><td> -0.46</td></tr>\n",
    "<tr><td> Knowledgeable</td><td> -0.35</td></tr>\n",
    "<tr><td> Praise</td><td> -0.67</td></tr>\n",
    "<tr><td> Professional</td><td> -0.61</td></tr>\n",
    "<tr><td> Prompt</td><td> -0.80</td></tr>\n",
    "<tr><td> Respectful</td><td> -0.61</td></tr>\n",
    "<tr><td> Responsive</td><td> -0.22</td></tr>\n",
    "</table>\n",
    "\n",
    "Those results are for a 5-point scale, so a difference of 0.8 (Promptness) is 16% of the entire scale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MacNell et al. graciously shared their data.\n",
    "The evaluation data are coded as follows:\n",
    "\n",
    "    Group\n",
    "          3 (12 students) - TA identified as male, true TA gender female \n",
    "\t      4 (11 students) - TA identified as male, true TA gender male\n",
    "\t      5 (11 students, 8 responders) - TA identified as female, true TA gender female\n",
    "\t      6 (13 students, 12 responders) - TA identified as female, true TA gender male\n",
    "    tagender - 1 if TA is actually male, 0 if actually female \n",
    "    taidgender - 1 if TA is identified as male, 0 if identified as female \n",
    "    gender - 1 if student is male, 0 if student is female\n",
    "\n",
    "There are grades for 47 students but evaluations for only 43 (4 did not respond: three in group 5 and one in group 6). \n",
    "The grades are not linked to the evaluations, per the IRB protocol.\n",
    "\n",
    "Our null hypothesis will include the assumption that whether a student responds does not depend on the identified gender of the TA: the 4 nonresponders would have remained nonresponders had they been in that instructor's other section, and no additional students would become nonresponders if they had been assigned to the same instructor's other section."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Interlude: partitioning sets into more than two subsets\n",
    "\n",
    "Recall that there are $n \\choose k$ ways of picking a subset of size $k$ from $n$ items;\n",
    "hence there are $n \\choose k$ ways of dividing a set into a subset of size $k$ and one of size $n-k$\n",
    "(once you select those that belong to the subset of size $k$, the rest must be in the complementary\n",
    "subset of size $n-k$.\n",
    "\n",
    "In this problem, we are partitioning 47 things into 4 subsets, two of size 11, one of size 12, and\n",
    "one of size 13.\n",
    "How many ways are there of doing that?\n",
    "\n",
    "\n",
    "Recall the [Fundamental Rule of Counting](http://www.stat.berkeley.edu/~stark/SticiGui/SticiGui/Text/counting.htm#fundamental_rule): \n",
    "If a set of choices, $T_1, T_2, \\ldots,  T_k$, could result, respectively, \n",
    "in $n_1, n_2, \\ldots, n_k$ possible outcomes, the entire set of $k$ choices has\n",
    "$\\prod_{i=1}^k n_k$ possible outcomes.\n",
    "\n",
    "We can think of the allocation of students to the four groups as choosing 11 of the 47\n",
    "students for the first group, then 11 of the remaining 36 for the second, \n",
    "then 12 of the remaining 25 for the third.\n",
    "The fourth group must contain the remaining 13.\n",
    "\n",
    "The number of ways of doing that is\n",
    "\n",
    "$$  \n",
    "   {47 \\choose 11}{36 \\choose 11}{25 \\choose 12} =\n",
    "   \\frac{47!}{11! 36!} \\frac{36!}{11! 25!} \\frac{25!}{12! 13!} = \\frac{47!}{11! 11! 12! 13!}.\n",
    "$$\n",
    "\n",
    "Does the number depend on the order in which we made the choices?\n",
    "Suppose we made the choices in a different order: first 12 students for one group, then\n",
    "11 for the second, then 13 for the third (the fourth gets the remaining 11 students).\n",
    "The number of ways of doing that is\n",
    "$$  \n",
    "   {47 \\choose 12}{35 \\choose 11}{24 \\choose 13} =\n",
    "   \\frac{47!}{12! 35!} \\frac{35!}{11! 24!} \\frac{24!}{13! 11!} = \\frac{47!}{12! 11! 13! 11!} = .\n",
    "$$\n",
    "The number does not depend on the order in which we make the choices.\n",
    "\n",
    "By the same reasoning, the number of ways of dividing a set of $n$ objects into\n",
    "$m$ subsets of sizes $k_1, \\ldots k_m$ is given by the _multinomial coefficient_\n",
    "$$\n",
    "   {n \\choose k_1, k_2, \\ldots, k_m} =\n",
    "   {n \\choose k_1}{n-k_1 \\choose k_2} {n-k_1-k_2 \\choose k_3} \\cdots {n - \\sum_{i=1}^{m-1} k_i \\choose k_{m-1}}\n",
    "$$\n",
    "\n",
    "$$ = \\frac{n! (n-k_1)! (n-k_1 - k_2)! \\cdots \n",
    "   (n - k_1 - \\cdots - k_{m-1}!}{k_1! (n-k_1)! k_2! (n-k_1-k_2)! \\cdots k_m!}\n",
    "   = \\frac{n!}{\\prod_{i=1}^m k_i!}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will check how surprising it would be for the means to be so much lower when the TA is identified as female, if in fact there is \"no real difference\" in how they were rated, and the apparent difference is just due to the luck of the draw: which students happened to end up in which section.\n",
    "\n",
    "In the actual randomization, all $47 \\choose 11, 11, 12, 13$ allocations\n",
    "were equally likely.\n",
    "But there might be real differences between the two instructors.\n",
    "Hence, we'd like to use each of them as his or her own \"control.\"\n",
    "\n",
    "Each student's potential responses are represented by a ticket with 4 numbers:\n",
    "\n",
    "+ the rating that the student would assign to instructor A if instructor A is identified as male\n",
    "+ the rating that the student would assign to instructor A if instructor A is identified as female\n",
    "+ the rating that the student would assign to instructor B if instructor B is identified as male\n",
    "+ the rating that the student would assign to instructor B if instructor B is identified as female\n",
    "\n",
    "The null hypothesis is that the first two numbers are equal and the second two numbers are equal,\n",
    "but the first two numbers might be different from the second two numbers.\n",
    "This corresponds to the hypohtesis that  \n",
    "students assigned to a given TA would rate him or her the same, whether that TA seemed to be male or female.\n",
    "For all students assigned instructor A, we know both of the first two numbers if the hull hypothesis\n",
    "is true; but we know neither of the second two numbers.\n",
    "Similarly, if the null hypothesis is true, we know both of the second two numbers for all students\n",
    "assigned to instructor B, but we know neither of the first two numbers for those students.\n",
    "\n",
    "Because of how the randomization was performed, all allocations \n",
    "of students to sections that keep the number of students in each section the same are equally likely, so\n",
    "in particular all allocations that keep the same students assigned to each actual instructor\n",
    "the same are equally likely.\n",
    "This is a subgroup of the full permutation group.\n",
    "\n",
    "Hence, all ${23 \\choose 12}$ ways of splitting the 23 students assigned to the female instructor into two groups, one with 11 students and one with 12, are equally likely. Similarly, all\n",
    "${24 \\choose 11}$ ways of splitting the 24 students assigned to the male instructor into two groups, one with 13 students and one with 11, are equally likely.\n",
    "We can thus imagine shuffling the female TA's students between her sections, and the male TA's students\n",
    "between his sections, and examine the distribution of the difference between the mean score for the sections where the\n",
    "TA was identified as male is larger than the mean score for the sections where the TA was identified as\n",
    "female.\n",
    "(The 4 nonresponders are also allocated at random between sections of the same \n",
    "instructor; they are not included in the averages.)\n",
    "\n",
    "If the difference is rarely as large as the observed mean difference, the observed mean difference gives\n",
    "evidence that being identified as female really does lower the scores."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.44175311066e+25\n"
     ]
    }
   ],
   "source": [
    "# Number of allocations to 11, 11, 12, 13\n",
    "print sp.special.binom(47,11)*sp.special.binom(36,11)*sp.special.binom(25,12)  # big number!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   group  professional  respect  caring  enthusiastic  communicate  helpful  \\\n",
      "0      3             5        5       4             4            4        3   \n",
      "1      3             4        4       4             4            5        5   \n",
      "2      3             5        5       5             5            5        5   \n",
      "3      3             5        5       5             5            5        3   \n",
      "4      3             5        5       5             5            5        5   \n",
      "\n",
      "   feedback  prompt  consistent  fair  responsive  praised  knowledgeable  \\\n",
      "0         4       4           4     4           4        4              3   \n",
      "1         5       5           3     4           5        5              5   \n",
      "2         5       5           5     5           5        5              5   \n",
      "3         5       5           5     5           3        5              5   \n",
      "4         5       3           4     5           5        5              5   \n",
      "\n",
      "   clear  overall  gender   age  tagender  taidgender  \n",
      "0      5        4       2  1990         0           1  \n",
      "1      5        4       1  1992         0           1  \n",
      "2      5        5       2  1991         0           1  \n",
      "3      5        5       2  1991         0           1  \n",
      "4      5        5       2  1992         0           1  \n",
      "           group  professional    respect     caring  enthusiastic  \\\n",
      "count  47.000000     43.000000  43.000000  43.000000     43.000000   \n",
      "mean    4.531915      4.325581   4.325581   3.930233      3.906977   \n",
      "std     1.158167      1.062811   1.062811   1.055492      1.019196   \n",
      "min     3.000000      1.000000   1.000000   1.000000      1.000000   \n",
      "25%     3.500000      4.000000   4.000000   3.500000      4.000000   \n",
      "50%     5.000000      5.000000   5.000000   4.000000      4.000000   \n",
      "75%     6.000000      5.000000   5.000000   5.000000      4.500000   \n",
      "max     6.000000      5.000000   5.000000   5.000000      5.000000   \n",
      "\n",
      "       communicate    helpful   feedback     prompt  consistent       fair  \\\n",
      "count    43.000000  43.000000  43.000000  43.000000   43.000000  43.000000   \n",
      "mean      3.953488   3.744186   3.953488   3.976744    3.744186   3.906977   \n",
      "std       1.068009   1.071115   1.132916   1.079867    1.156617   0.995560   \n",
      "min       1.000000   1.000000   1.000000   1.000000    1.000000   1.000000   \n",
      "25%       4.000000   3.000000   4.000000   4.000000    3.000000   3.500000   \n",
      "50%       4.000000   4.000000   4.000000   4.000000    4.000000   4.000000   \n",
      "75%       5.000000   5.000000   5.000000   5.000000    5.000000   5.000000   \n",
      "max       5.000000   5.000000   5.000000   5.000000    5.000000   5.000000   \n",
      "\n",
      "       responsive    praised  knowledgeable      clear    overall     gender  \\\n",
      "count   43.000000  43.000000      43.000000  43.000000  43.000000  43.000000   \n",
      "mean     3.767442   4.209302       4.139535   3.720930   3.953488   1.534884   \n",
      "std      0.996116   0.940064       0.989983   1.259735   1.022450   0.504685   \n",
      "min      1.000000   1.000000       1.000000   1.000000   1.000000   1.000000   \n",
      "25%      3.000000   4.000000       4.000000   3.000000   4.000000   1.000000   \n",
      "50%      4.000000   4.000000       4.000000   4.000000   4.000000   2.000000   \n",
      "75%      4.500000   5.000000       5.000000   5.000000   5.000000   2.000000   \n",
      "max      5.000000   5.000000       5.000000   5.000000   5.000000   2.000000   \n",
      "\n",
      "               age   tagender  taidgender  \n",
      "count    43.000000  47.000000   47.000000  \n",
      "mean   1990.325581   0.510638    0.489362  \n",
      "std       4.115713   0.505291    0.505291  \n",
      "min    1982.000000   0.000000    0.000000  \n",
      "25%    1990.000000   0.000000    0.000000  \n",
      "50%    1990.000000   1.000000    0.000000  \n",
      "75%    1991.000000   1.000000    1.000000  \n",
      "max    2012.000000   1.000000    1.000000  \n"
     ]
    }
   ],
   "source": [
    "# the data are in a .csv file called \"Macnell-RatingsData.csv\" in the directory Data\n",
    "import pandas as pd\n",
    "\n",
    "ratings = pd.read_csv(\"./Data/Macnell-RatingsData.csv\")\n",
    "categories = ratings.columns.values.tolist()[1:15]\n",
    "print ratings.head()\n",
    "print ratings.describe()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from permute.core import corr, two_sample, permute_within_groups\n",
    "from permute.utils import get_prng\n",
    "rs = np.random.RandomState(seed=1)  # set the seed of the PRNG, for reproducibility"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def stratified_two_sample(x, y, group_x, group_y, stat='mean', alternative=\"greater\", reps=10**4, \n",
    "                          keep_dist=False, seed=None):\n",
    "    \"\"\"\n",
    "    One-sided or two-sided, two-sample permutation test for equality of\n",
    "    two means, with p-value estimated by simulated random sampling with\n",
    "    reps replications.\n",
    "\n",
    "    Tests the hypothesis that x and y are a random partition of x,y\n",
    "    against the alternative that x comes from a population with mean\n",
    "\n",
    "    (a) greater than that of the population from which y comes,\n",
    "        if side = 'greater'\n",
    "    (b) less than that of the population from which y comes,\n",
    "        if side = 'less'\n",
    "    (c) different from that of the population from which y comes,\n",
    "        if side = 'two-sided'\n",
    "\n",
    "    Permutations are carried out within the given groups.  Under the null hypothesis,\n",
    "    observations within each group are exchangeable.\n",
    "\n",
    "    If ``keep_dist``, return the distribution of values of the test statistic;\n",
    "    otherwise, return only the number of permutations for which the value of\n",
    "    the test statistic and p-value.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    x : array-like\n",
    "        Sample 1\n",
    "    y : array-like\n",
    "        Sample 2\n",
    "    group_x : array-like\n",
    "        Group assignments for sample 1\n",
    "    group_y : array-like\n",
    "        Group assignments for sample 2\n",
    "    stat : {'mean', 't'}\n",
    "        The test statistic.\n",
    "\n",
    "        (a) If stat == 'mean', the test statistic is (mean(x) - mean(y))\n",
    "            (equivalently, sum(x), since those are monotonically related), omitting\n",
    "            NaNs, which therefore can be used to code non-responders\n",
    "        (b) If stat == 't', the test statistic is the two-sample t-statistic--\n",
    "            but the p-value is still estimated by the randomization,\n",
    "            approximating the permutation distribution.\n",
    "            The t-statistic is computed using scipy.stats.ttest_ind\n",
    "        (c) If stat is a function (a callable object), the test statistic is\n",
    "            that function.  The function should take a permutation of the pooled\n",
    "            data and compute the test function from it. For instance, if the\n",
    "            test statistic is the Kolmogorov-Smirnov distance between the\n",
    "            empirical distributions of the two samples, max_t |F_x(t) - F_y(t)|,\n",
    "            the test statistic could be written:\n",
    "\n",
    "            f = lambda u: np.max( \\\n",
    "                [abs(sum(u[:len(x)]<=v)/len(x)-sum(u[len(x):]<=v)/len(y)) for v in u]\\\n",
    "                )        \n",
    "    alternative : {'greater', 'less', 'two-sided'}\n",
    "        The alternative hypothesis to test\n",
    "    reps : int\n",
    "        Number of permutations\n",
    "    keep_dist : bool\n",
    "        flag for whether to store and return the array of values\n",
    "        of the irr test statistic\n",
    "    seed : RandomState instance or {None, int, RandomState instance}\n",
    "        If None, the pseudorandom number generator is the RandomState\n",
    "        instance used by `np.random`;\n",
    "        If int, seed is the seed used by the random number generator;\n",
    "        If RandomState instance, seed is the pseudorandom number generator.\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    float\n",
    "        the estimated p-value\n",
    "    float\n",
    "        the test statistic\n",
    "    list\n",
    "        The distribution of test statistics.\n",
    "        These values are only returned if `keep_dist` == True        \n",
    "    \"\"\"\n",
    "    \n",
    "    prng = get_prng(seed)\n",
    "    \n",
    "    z = np.concatenate([x, y])   # pooled responses\n",
    "    groups = np.concatenate([group_x, group_y])   # pooled group assignments\n",
    "    \n",
    "    # If stat is callable, use it as the test function. Otherwise, look in the dictionary\n",
    "    stats = {\n",
    "        'mean': lambda u: np.nanmean(u[:len(x)]) - np.nanmean(u[len(x):]),\n",
    "        't': lambda u: ttest_ind(\n",
    "            u[:len(y)][~np.isnan(u[:len(y)])], \n",
    "            u[len(y):][~np.isnan(u[len(y):])], \n",
    "            equal_var=True)[0]\n",
    "    }\n",
    "    if callable(stat):\n",
    "        tst_fun = stat\n",
    "    else:\n",
    "        tst_fun = stats[stat]\n",
    "\n",
    "    theStat = {\n",
    "        'greater': tst_fun,\n",
    "        'less': lambda u: -tst_fun(u),\n",
    "        'two-sided': lambda u: math.fabs(tst_fun(u))\n",
    "    }\n",
    "    tst = theStat[alternative](z)\n",
    "    observed_tst = tst_fun(z)\n",
    "    \n",
    "    if keep_dist:\n",
    "        dist = np.empty(reps)\n",
    "        for i in range(reps):\n",
    "            dist[i] = theStat[alternative](permute_within_groups(z, groups, seed=prng))\n",
    "        hits = np.sum(dist >= tst)\n",
    "        return hits/reps, tst, dist\n",
    "    else:\n",
    "        hits = np.sum([(theStat[alternative](permute_within_groups(z, groups, seed=prng)) >= tst)\n",
    "                       for i in range(reps)])\n",
    "        return hits/reps, tst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overall rating:\n",
      "Difference in means: 0.473913043478\n",
      "P-value (two-sided): 0.1187 \n",
      "\n",
      "\n",
      "\n",
      "Category                 Diff means P-value \n",
      "professional             0.61     0.06\n",
      "respect                  0.61     0.06\n",
      "caring                   0.52     0.09\n",
      "enthusiastic             0.57     0.06\n",
      "communicate              0.57     0.07\n",
      "helpful                  0.46     0.17\n",
      "feedback                 0.47     0.16\n",
      "prompt                   0.80     0.01\n",
      "consistent               0.46     0.21\n",
      "fair                     0.76     0.01\n",
      "responsive               0.22     0.48\n",
      "praised                  0.67     0.02\n",
      "knowledgeable            0.35     0.29\n",
      "clear                    0.41     0.30\n"
     ]
    }
   ],
   "source": [
    "(p, t) = stratified_two_sample(ratings['overall'][ratings.taidgender==1], ratings['overall'][ratings.taidgender==0], \n",
    "                               ratings['tagender'][ratings.taidgender == 1], \n",
    "                               ratings['tagender'][ratings.taidgender == 0],\n",
    "                               alternative = \"two-sided\", seed = rs)\n",
    "print 'Overall rating:'\n",
    "print 'Difference in means:', t\n",
    "print 'P-value (two-sided):', np.round(p, 5), \"\\n\"\n",
    "\n",
    "print ('\\n\\n{0:24} {1:8} {2:8}'.format('Category', 'Diff means', 'P-value'))\n",
    "for col in categories:\n",
    "    (p, t) = stratified_two_sample(ratings[col][ratings.taidgender==1], ratings[col][ratings.taidgender==0], \n",
    "                               ratings['tagender'][ratings.taidgender == 1],\n",
    "                               ratings['tagender'][ratings.taidgender == 0],\n",
    "                               alternative = \"two-sided\", seed = rs)\n",
    "    print ('{0:20} {1:8.2f} {2:8.2f}'.format(col, t, p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## General test based on group invariance\n",
    "\n",
    "References:\n",
    "\n",
    "+ Romano, J.P., 1988. A bootstrap revival of some nonparametric distance tests, _J. Amer. Stat. Assoc., 83_, 698&ndash;708\n",
    "+ Romano, J.P., 1989. Bootstrap and randomization tests of some nonparametric hypotheses, _Ann. Stat., 17_, 141&ndash;159\n",
    "\n",
    "Data $X \\sim P$ takes values in $\\mathcal X$.\n",
    "\n",
    "$\\mathcal G$ is a finite group of transformations from $\\mathcal X$ to $\\mathcal X$.\n",
    "$\\# \\mathcal G = G$.\n",
    "\n",
    "Want to test null hypothesis $H_0: P \\in \\Omega_0$.\n",
    "\n",
    "Suppose $H_0$ implies that $P$ is invariant under $\\mathcal G$:\n",
    "$$\n",
    "   \\forall g \\in \\mathcal{G}, \\;\\; X \\sim gX.\n",
    "$$\n",
    "\n",
    "The _orbit of $x$ (under $\\mathcal G$)_ is $\\{ gx : g \\in \\mathcal G \\}$.\n",
    "(Does the orbit of $x$ always contain $G$ points?)\n",
    "\n",
    "### Test statistic $T$\n",
    "\n",
    "Let $T: \\mathcal{X} \\rightarrow \\Re$ be a test statistic.\n",
    "\n",
    "We want to test $H_0$ at significance level $\\alpha$.\n",
    "\n",
    "For each fixed $x$, let $T^{(k)}(x)$ be the $k$th smallest \n",
    "element of the multiset\n",
    "$$\n",
    "    [ T(gx): g \\in \\mathcal G ].\n",
    "$$\n",
    "\n",
    "These are the $G$ (not necessarily distinct) values $T$ takes on the orbit of $x$.\n",
    "\n",
    "### Finding the rejection region\n",
    "\n",
    "Let\n",
    "$$\n",
    "     r \\equiv G - \\lfloor \\alpha G \\rfloor.\n",
    "$$\n",
    "\n",
    "Define\n",
    "$$\n",
    "     G^+(x) \\equiv \\# \\{ g \\in \\mathcal{G}: T(gx) > T^{(r)}(x) \\}\n",
    "$$\n",
    "and\n",
    "$$\n",
    "     G^r(x) \\equiv \\# \\{ g \\in \\mathcal{G}: T(gx) = T^{(r)}(x) \\}\n",
    "$$\n",
    "\n",
    "Let\n",
    "$$\n",
    "      a(x) \\equiv \\frac{\\alpha G - G^+(x)}{G^r(x)}.\n",
    "$$\n",
    "\n",
    "Define\n",
    "$$\n",
    "   \\phi(x) \\equiv \n",
    "        \\left \\{ \n",
    "            \\begin{array}{ll}\n",
    "                 1,      &  T(x) > T^{(r)}(x), \\cr\n",
    "                a(x),   &  T(x) = T^{(r)}(x), \\cr\n",
    "                 0,      &  T(x) < T^{(r)}(x)\n",
    "            \\end{array}\n",
    "         \\right .\n",
    "$$\n",
    "\n",
    "To test the hypothesis, generate $U \\sim U[0, 1]$ independent of $X$.\n",
    "\n",
    "Reject $H_0$ if $\\phi(x) \\ge U$.  (Randomized test.)\n",
    "\n",
    "\n",
    "### Test has level $\\alpha$ unconditionally\n",
    "\n",
    "For each $x \\in \\mathcal{X}$,\n",
    "\n",
    "$$\n",
    "    \\sum_{g \\in \\mathcal{G}} \\phi(gx) = G^+(x) + a(x) G^r(x) = \\alpha G.\n",
    "$$\n",
    "\n",
    "So if $X \\sim gX \\sim P$ for all $g \\in \\mathcal G$,\n",
    "$$\n",
    "\\alpha  =  \\mathbb{E}_P \\frac{1}{G}\\sum_{g \\in \\mathcal {G}} \\phi(gX) \n",
    "$$\n",
    "$$\n",
    " =  \\frac{1}{G}\\sum_{g \\in \\mathcal{G}} \\mathbb{E}_P \\phi(X) \n",
    "$$\n",
    "$$\n",
    " =  \\mathbb{E}_P \\phi(X).\n",
    "$$\n",
    "\n",
    "The unconditional chance of a Type I error is exactly $\\alpha$.\n",
    "\n",
    "\n",
    "### Tests for the mean of a symmetric distribution\n",
    "\n",
    "Data $X = (X_j )_{j=1}^N \\in \\mathcal{X} = \\Re^n$.\n",
    "\n",
    "$\\{ X_j \\}$ iid $P$; $\\mathbb{E} X_j = \\mu$.\n",
    "\n",
    "Suppose $P$ is symmetric.  Examples?\n",
    "\n",
    "\n",
    "### Reflection group\n",
    "\n",
    "Let $\\mathcal{G}_\\mu$ be the group of reflections of coordinates about $\\mu$.\n",
    "\n",
    "Let $x \\in \\Re^n$.\n",
    "Each $g \\in \\mathcal{G}_\\mu$ is of the form\n",
    "\n",
    "$$\n",
    "g(x) = (\\mu + (-1)^{\\gamma_j}(x_j - \\mu))_{j=1}^n\n",
    "$$\n",
    "\n",
    "for some $\\gamma = (\\gamma_j)_{j=1}^n \\in \\{0, 1\\}^n$.\n",
    "\n",
    "Is $\\mathcal{G}_\\mu$ really a group?\n",
    "\n",
    "What's the identity element?  \n",
    "What's the inverse of $g$?  \n",
    "What $\\gamma$ corresponds to $g_1g_2$?\n",
    "\n",
    "What is $G$, the number of elements of $\\mathcal{G}_\\mu$?\n",
    "\n",
    "What is the orbit of a point $x$ under $\\mathcal{G}_\\mu$?  \n",
    "Are there always $2^n$ distinct elements of the orbit?\n",
    "\n",
    "Test statistic:\n",
    "\n",
    "$$\n",
    "   T(X) = | \\bar{X} - \\mu_0 | = \\left | \\frac{1}{n} \\sum_{j=1}^n X_j - \\mu_0 \\right |.\n",
    "$$\n",
    "\n",
    "If $\\mathbb{E} X_j = \\mu_0$, this is expected to be small---but how \n",
    "large a value would be surprising?\n",
    "\n",
    "\n",
    "If the expected value of $X_j$ is $\\mu$ and $P$ is symmetric (i.e., if $H_0$\n",
    "is true), \n",
    "the $2^n$ potential data\n",
    "\n",
    "$$\n",
    "   \\{ gX : g \\in \\mathcal{G}_\\mu \\}\n",
    "$$\n",
    "\n",
    "in the orbit of $X$ under $\\mathcal{G}$ are equally likely.\n",
    "\n",
    "Hence, the values in the multiset\n",
    "\n",
    "$$\n",
    "   [ T(gx) : g \\in \\mathcal{G}_\\mu ]\n",
    "$$\n",
    "\n",
    "are equally likely, conditional on the event that $X$ is in the orbit of $x$.\n",
    "\n",
    "### How to test $H_0$: $\\mu = \\mu_0$?\n",
    "\n",
    "We observe $X = x$.\n",
    "\n",
    "If fewer than $\\alpha G$ values in $[T(gx) : g \\in \\mathcal{G}_{\\mu_0}]$ are greater than \n",
    "or equal to\n",
    "$T(x)$, reject.\n",
    "If more than $\\alpha G$ values are greater than $T(x)$, don't reject.\n",
    "Otherwise, randomize.\n",
    "\n",
    "\n",
    "### If $n$ is big &hellip;\n",
    "\n",
    "How can we sample at random from the orbit?\n",
    "\n",
    "Toss fair coin $n$ times in sequence, independently.\n",
    "Take $\\gamma_j = 1$ if the $j$th toss gives heads; $\\gamma_j = 0$ if tails.\n",
    "\n",
    "Amounts to sampling with replacement from the orbit of $x$.\n",
    "\n",
    "### Other test statistics?\n",
    "\n",
    "Could use $t$-statistic, but calibrate critical value using the permutation distribution.\n",
    "\n",
    "Could use a measure of dispersion around the hypothesized mean (the\n",
    "true mean minimizes expected RMS difference, assuming variance is finite).\n",
    "\n",
    "What about counting the number of values that are above $\\mu_0$?\n",
    "\n",
    "Define \n",
    "$$\n",
    "T(x) \\equiv \\sum_{j=1}^n 1_{x \\ge \\mu_0}.\n",
    "$$\n",
    "\n",
    "### Sign test for the median\n",
    "\n",
    "We are assuming $P$ is symmetric, so the expected value and median are equal.\n",
    "\n",
    "To avoid unhelpful complexity, suppose $P$ is continuous.\n",
    "\n",
    "Then \n",
    "\n",
    "$$\n",
    "\\Pr \\{ X_j \\ge \\mu \\} = 1/2, \n",
    "$$\n",
    "\n",
    "$$\n",
    "   \\{ 1_{X_j \\ge \\mu} \\}_{j=1}^n \\mbox{ are iid Bernoulli}(1/2),\n",
    "$$\n",
    "\n",
    "and \n",
    "\n",
    "$$\n",
    "    T(X) \\sim \\mbox{Binomial}(n, 1/2).\n",
    "$$\n",
    "\n",
    "This leads to the sign test:  Reject the hypothesis that the median is $\\mu_0$\n",
    "if $T(X)$ is too large or too small.\n",
    "Thresholds set to get level $\\alpha$ test, using the fact that $T(X)\\sim \\mbox{Binomial}(n, 1/2)$.\n",
    "\n",
    "\n",
    "### Is the sign test equivalent to the permutation test for the same test statistic?\n",
    "\n",
    "Suppose we are using the test statistic $T(x) = \\sum_{j=1}^n 1_{x \\ge \\mu_0}$.\n",
    "Do the permutation test and the sign test reject for the same values of $x \\in \\mathcal{X}$?\n",
    "\n",
    "Suppose no component of $x$ is equal to $\\mu_0$.\n",
    "According to the sign test, the chance that $T(x) = k$ is\n",
    "${{n}\\choose{k}} 2^{-n}$ if the null is true.\n",
    "\n",
    "What's the chance that $T(x) = k$ according to the permutation test?\n",
    "There are $G = 2^n$ points in the orbit of $x$ under $\\mathcal G$.\n",
    "If the null is true, all have equal probability $2^{-n}$.\n",
    "Of these points, ${{n}\\choose{k}}$ have $k$ components with positive deviations from $\\mu_0$.\n",
    "Hence, for the permutation test, the chance that $T(x) = k$ is also \n",
    "${{n} \\choose {k}} 2^{-n}$:  The two tests are equivalent.\n",
    "\n",
    "\n",
    "### Abstract setting using VC classes\n",
    "\n",
    "The distribution $P \\in \\Omega$, where $\\Omega$ is a known collection of\n",
    "distributions on $\\mathcal{X}$.\n",
    "The null hypothesis is that $P \\in \\Omega_0 \\subset \\Omega$.  We assume that\n",
    "$\\Omega_0$ can be characterized as a set of distributions that are invariant under\n",
    "a transformation on $\\Omega$: let $\\tau: \\Omega \\rightarrow \\Omega_0$; we assume\n",
    "that $\\tau(P) = P$ for all $P \\in \\Omega_0$.\n",
    "\n",
    "Let $\\mathcal{V}$ be a collection of subsets of a set $\\mathcal{X}$.\n",
    "For a finite set $D \\subset \\mathcal{X}$, let $\\Delta^\\mathcal{V}(D)$ be the number of distinct sets\n",
    "$\\{ V \\cap D: V \\in \\mathcal{V} \\}$.\n",
    "For positive integers $n$, let\n",
    "$$\n",
    "    m^\\mathcal{V}(n) = \\max_{D \\subset \\mathcal{X}: \\#D = n } \\Delta^\\mathcal{V}(D).\n",
    "$$\n",
    "\n",
    "Let\n",
    "$$\n",
    "    c(\\mathcal{V}) \\equiv \\inf \\{ n : m^\\mathcal{V}(n) < 2^n \\}.\n",
    "$$\n",
    "\n",
    "If $c(\\mathcal{V}) < \\infty$, $\\mathcal{V}$ is a Vapnik-Cervonenkis (V-C) class.\n",
    "That is, $\\mathcal{V}$ is a V-C class\n",
    "if the maximum number of distinct intersections of sets in $\\mathcal{V}$\n",
    "with sets containing $n$ points grows sub-exponentially with $n$.\n",
    "Intersections, finite unions, and Cartesian products of V-C classes are V-C classes.\n",
    "In $\\Re^n$, the set of all ellipsoids, the set of all half-spaces, the set of all\n",
    "lower-left quadrants, and the set of all convex sets with at most $p$ extreme\n",
    "points are all V-C classes.\n",
    "\n",
    "An alternative, equivalent definition of a V-C class is based on the following definition:\n",
    "\n",
    "_Suppose $\\mathcal{V}$ is a collection of subsets of a set $\\mathcal{X}$, and that $D$ is a finite subset of $\\mathcal{X}$.\n",
    "We say $D$ is _shattered_ by $\\mathcal{V}$ if every subset $d \\subset D$\n",
    "can be written $d = V \\cap D$ for some $V \\in \\mathcal{V}$._\n",
    "\n",
    "Suppose $D$ has $n$ elements.\n",
    "Because there are $2^n$ subsets of a set with $n$ elements, this is equivalent to saying\n",
    "that there are $2^n$ different subsets of the form $D \\cap V$ as $V$ ranges over $\\mathcal{V}$.\n",
    "\n",
    "A collection $\\mathcal{V}$ is a V-C class if for some finite integer $n$, there exists a set\n",
    "$D \\subset \\mathcal{X}$ with $n$ elements that is not shattered by $\\mathcal{V}$.\n",
    "\n",
    "__Example__. Half lines on $\\Re$.\n",
    "Consider a set $D = \\{x_j\\}_{j=1}^n$ of points on the real line.\n",
    "Let $\\mathcal{V} = \\{ (-\\infty, y] : y \\in \\Re \\}$.\n",
    "How many sets are there  of the form $V \\cap D$, for $V \\in \\mathcal{V}$?\n",
    "Just $n+1$.\n",
    "Suppose the points are in increasing order, so that $x_1 < x_2 < \\cdots < x_n$.\n",
    "Then the possibilities for $V \\cap D$ are $\\{ \\}$,\n",
    "$\\{ x_1 \\}$, $\\{ x_1, x_2 \\}$, $\\ldots$, $\\{x_j \\}_{j=1}^n$.\n",
    "Thus $m^{\\mathcal{V}}(n) = n+1$, and $c(\\mathcal{V}) \\equiv \\inf \\{ n : m^\\mathcal{V}(n) < 2^n \\} = 2$\n",
    "(for $n=0$, we have $0+1 = 2^0$, and for $n=1$,\n",
    "we have $1+1 = 2^1$, but for $n=2$, we have $2+1 < 2^2$).\n",
    "\n",
    "__Example__. Closed intervals $\\{[y, z]$: $y < z\\}$ on $\\Re$.\n",
    "For finite sets $D$ as discussed above,\n",
    "the possibilities for $V \\cap D$ include all sets of adjacent values, such as\n",
    "$\\{x_1\\}$, $\\{x_2\\}$, $\\{x_3\\}$, $\\{x_1, x_2\\}$, $\\{x_2, x_3\\}$, and $\\{x_1, x_2, x_3\\}$, but not,\n",
    "for example, $\\{ x_1, x_3 \\}$.\n",
    "Clearly, $m^{\\mathcal{V}}(2) = 4$ but $m^{\\mathcal{V}}(3) = 7$, so $c(\\mathcal{V}) = 3$.\n",
    "(The general rule is $m^{\\mathcal{V}}(n) = 1 + n + {n}\\choose{2}$. Why?)\n",
    "\n",
    "Suppose that $\\mathcal{V}$ and $\\mathcal{W}$ are V-C classes on a common set $\\mathcal{X}$.\n",
    "Then $\\mathcal{V} \\cup \\mathcal{W}$ is also a V-C class, as is $\\mathcal{V} \\cap \\mathcal{W}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "+ Show that intersections and finite unions of V-C classes are V-C classes.\n",
    "\n",
    "+ Show by example that a countable union of V-C classes need not be a V-C class."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $\\mathcal{V}$ be a VC\n",
    "class of subsets of $\\mathcal{S}$.\n",
    "Define the pseudo-metric\n",
    "$$\n",
    "\\delta: \\Omega \\times \\Omega \\rightarrow \\Re^+\n",
    "$$\n",
    "$$\n",
    "(P, Q)  \\rightarrow  \\sup_{V \\in \\mathcal{V}} | P(V) - Q(V) | .\n",
    "$$\n",
    "\n",
    "This is a generalization of the Kolmogorov-Smirnov distance for distributions on the\n",
    "line.\n",
    "In that case, the sets in $\\mathcal{V}$ are the half-lines $\\{(-\\infty, y] : y \\in \\Re\\}$\n",
    "(which comprise a\n",
    "V-C class).\n",
    "\n",
    "Assume that $\\mathcal{V}$ and $\\tau$ have been selected such that\n",
    "$\\delta(P, \\tau P) = 0$ iff\n",
    "$P \\in \\Omega_0$.\n",
    "Romano proposes using the test statistic\n",
    "$$\n",
    "    T_n = n^{1/2} \\delta(\\hat{P}_n, \\tau \\hat{P}_n ),\n",
    "$$\n",
    "where $\\hat{P}_n$ is the empirical measure of $\\{X_j \\}_{j=1}^n$.\n",
    "One rejects the hypothesis when  $\\tau\\hat{P}_n$ is far from $\\hat{P}_n$; i.e.,\n",
    "when $T_n$ is sufficiently large.\n",
    "\n",
    "But how large?\n",
    "One way to obtain a critical value for the test is with the bootstrap:\n",
    "resample from $\\tau(\\hat{P}_n)$, tabulate the distribution of the distance\n",
    "between the empirical distribution of the bootstrap samples and $\\tau$ applied to them,\n",
    "use the $1-\\alpha$ quantile of that distribution as the critical value for an\n",
    "approximate level $\\alpha$ test.\n",
    "(We have to resample from $\\tau(\\hat{P}_n)$ rather than $\\hat{P}_n$ because the\n",
    "significance level is computed under the assumption that the null hypothesis is _true_.\n",
    "The null hypothesis is true for $\\tau(\\hat{P}_n)$ but not necessarily for $\\hat{P}_n$.)\n",
    "\n",
    "Suppose that there is a (known) group $\\mathcal{G}_n$ of transformations of the sample space\n",
    "$\\mathcal{S}_n$\n",
    "such that under the null hypothesis, $P$ is invariant under $\\mathcal{G}_n$.\n",
    "Then we can also construct a _randomization test_ of the hypothesis $H_0$.\n",
    "For simplicity, suppose that $\\mathcal{G}_n$ is finite, with $M_n$ elements\n",
    "$\\{ g_{nj} \\}_{j=1}^{M_n}$.\n",
    "Under the null hypothesis, conditional on $X = x$, the values $\\{ g_{nj}x \\}_{j=1}^{M_n}$\n",
    "are equally likely.\n",
    "(The _orbit_ of an point $x$ in a space $S$ acted on by a group $\\mathcal{G}$ is the set of\n",
    "all elements of $S$ that can be obtained by applying elements of $\\mathcal{G}$ to $x$.\n",
    "That is, it is the set $\\{ g(x): g \\in \\mathcal{G}\\}$.\n",
    "For example, consider points in the plane and the group of rotations about the\n",
    "origin.\n",
    "Then the orbit of a point $x$ is the circle with radius $\\|x\\|$.)\n",
    "\n",
    "Compute the  test statistic for each $ g_{nj}x$ in the orbit of $x$.\n",
    "Reject the null hypothesis if the statistic for $x$ exceeds the $1-\\alpha$ quantile of\n",
    "the test statistic for the set of values obtained from the orbit;\n",
    "do not reject if it is less; reject with a given probability if the statistic equals\n",
    "the $1-\\alpha$ quantile, in such a way as to get a level $\\alpha$ test.\n",
    "This is a randomization test.\n",
    "Because the level of the randomization test is $\\alpha$, conditional on the data,\n",
    "integrating\n",
    "over the distribution of the data shows that it is $\\alpha$ unconditionally.\n",
    "\n",
    "### Examples of hypotheses and functions $\\tau$\n",
    "\n",
    "Examples Romano gives include testing for independence of the components of each $X_j$,\n",
    "testing for exchangeability of the components of each $X_j$, testing for spherical\n",
    "symmetry of the distribution of $X_j$, testing for homogeneity among the $X_j$, and\n",
    "testing for a change point.\n",
    "\n",
    "In the example of testing for independence, the mapping $\\tau$ takes the marginal\n",
    "distributions of the joint distribution, then constructs a joint distribution that\n",
    "is the product of the marginals.  For distributions with independent components,\n",
    "this is the identity; otherwise, it maps a distribution into one with the same\n",
    "marginals, but whose components are independent.\n",
    "For testing for spherical symmetry, $\\tau$ maps a distribution into one with the same  mass\n",
    "at every distance from the origin, but that is uniform on spherical shells.\n",
    "For testing for exchangability, Romano proposes looking at the largest difference between\n",
    "$P$ and a permutation of the coordinates of $P$, over all permutations of the coordinates.\n",
    "See his paper for more details.\n",
    "\n",
    "Romano shows that these tests are consistent against all alternatives, and that\n",
    "the critical values given by the bootstrap and by randomization are asymptotically\n",
    "equal with probability one.  Because the randomization tests are exact level $\\alpha$\n",
    "tests, they might be preferred.  Romano also briefly discusses how to implement the tests\n",
    "computationally.\n",
    "\n",
    "Let's consider the implementation in more detail, for two hypotheses:\n",
    "independence of the components of a $k$-variate distribution, and\n",
    "rotational invariance of a bivariate distribution.\n",
    "\n",
    "### Independence\n",
    "We observe $\\{X_j\\}_{j=1}^n$ iid $P$, where each $X_j = (X_{ij})_{i=1}^k$ takes values in $\\Re^k$.\n",
    "Under the null hypothesis, $P$ is invariant under the mapping $\\tau$ that takes the $k$\n",
    "marginal distributions of $P$ and multiplies them together to give a probability on\n",
    "$\\Re^k$ with independent components.\n",
    "Let $\\hat{P}_n$ be the empirical measure; let the V-C class $\\mathcal{V}$ be the set of\n",
    "lower left quadrants $\\{ Q(x) : x \\in \\Re^k \\}$ where\n",
    "$$\n",
    "    Q(x) \\equiv \\{ y \\in \\Re^k : y_i \\le x_i, \\;\\; i = 1, \\ldots, k\\}.\n",
    "$$\n",
    "Then\n",
    "$$\n",
    "    \\hat{P}_n(Q(x)) = \\frac{1}{n} \\# \\{ X_j : X_{ij} \\le x_i, \\;\\; i = 1, \\ldots, k \\},\n",
    "$$\n",
    "and\n",
    "$$\n",
    "    \\tau \\hat{P}_n (Q(x)) = \\prod_{i=1}^k \\frac{1}{n} \\# \\{ X_j : X_{ij} \\le x_i \\}.\n",
    "$$\n",
    "The maximum difference in the probability of a lower left quadrant $Q(x)$ occurs when\n",
    "$x$ is one of the points of support of $\\tau \\hat{P}_n$:\n",
    "$$\n",
    "\\sup_{V \\in \\mathcal{V}} | \\hat{P}_n (V) - \\tau \\hat{P}_n(V) |\n",
    "= \\sup_{x \\in \\Re^k} | \\hat{P}_n (Q(x)) - \\tau \\hat{P}_n(Q(x)) |\n",
    "$$\n",
    "$$\n",
    "= \\max_{x \\in \\Re^k : x_i \\in \\{X_{ij}\\}_{j=1}^n, \\;\\; i = 1, \\ldots, k }\n",
    "| \\hat{P}_n (Q(x)) - \\tau \\hat{P}_n(Q(x)) |.\n",
    "$$\n",
    "\n",
    "To test the null hypothesis of independence, we would compute\n",
    "$$\n",
    "    T(X) = \\max_{x \\in \\Re^k : x_i \\in \\{X_{ij}\\}_{j=1}^n, \\;\\; i = 1, \\ldots, k }\n",
    "    | \\hat{P}_n (Q(x)) - \\tau \\hat{P}_n(Q(x)) |\n",
    "$$\n",
    "from the data $X$, then repeatedly draw iid samples $X^*$ of size $n$ from $\\tau \\hat{P}_n$,\n",
    "computing\n",
    "$$\n",
    "    T(X^*) = \\max_{x \\in \\Re^k : x_i \\in \\{X_{ij}^*\\}_{j=1}^n, \\;\\; i = 1, \\ldots, k }\n",
    "    | \\hat{P}_n^* (Q(x)) - \\tau \\hat{P}_n^*(Q(x)) |\n",
    "$$\n",
    "for each.\n",
    "We would reject the null hypothesis\n",
    "that the components of $P$ are independent (at approximate significance level $\\alpha$) if\n",
    "$T(X)$ exceeds the $1-\\alpha$ quantile of the simulated distribution of $T(X^*)$.\n",
    "\n",
    "### Rotational invariance in $\\Re^2$\n",
    "\n",
    "We observe $\\{X_j\\}_{j=1}^n$ iid $P$, where each $X_j = (X_{1j}, X_{2j})$ takes values in $\\Re^2$.\n",
    "\n",
    "For $y \\in \\Re^2$, define $|y| \\equiv \\sqrt{y_1^2 + y_2^2}$ to be the distance from $y$ to\n",
    "the origin.\n",
    "\n",
    "Except at the origin, the mapping from Cartesian coordinates $(x_1, x_2)$ to polar coordinates\n",
    "$(r, \\theta)$ is one-to-one; identify\n",
    "the origin with the polar coordinates $(0, 0)$.\n",
    "Under the null hypothesis, $P$ is invariant under the mapping $\\tau$ that produces\n",
    "a distribution with the same marginal distribution of $|X|$ but that is uniform on\n",
    "$\\theta$ for each possible value of $|X|$.\n",
    "\n",
    "As before, let $\\hat{P}_n$ be the empirical measure; let the V-C class $\\mathcal{V}$ be the set of\n",
    "lower left quadrants $\\{ Q(x) : x \\in \\Re^2 \\}$ where\n",
    "$$\n",
    "    Q(x) \\equiv \\{ y \\in \\Re^k : y_i \\le x_i, \\;\\; i = 1, 2\\}.\n",
    "$$\n",
    "\n",
    "Then\n",
    "$$\n",
    "    \\hat{P}_n(Q(x)) = \\frac{1}{n} \\# \\{ X_j : X_{ij} \\le x_i, \\;\\; i = 1, 2 \\}.\n",
    "$$\n",
    "\n",
    "To proceed, we need to find the probability of lower left quadrants $Q(x)$ for the\n",
    "distribution $\\tau \\hat{P}_n$.\n",
    "Consider the contribution from each $X_j$ separately.\n",
    "Let $R_j = |X_j| = \\sqrt{X_{1j}^2 + X_{2j}^2}$.\n",
    "The contribution of $X_j$ to $\\tau \\hat{P}_n (Q(x))$ is $1/n$ times the fraction of\n",
    "the circle $\\{ y \\in \\Re^2 : |y| = R_j\\}$ that is in the quadrant $Q(x)$.\n",
    "There are eight cases to consider:\n",
    "\n",
    "1. $x_1^2 + x_2^2 > R_j^2$, $x_1, \\; x_2 < 0$ or $x_1 < -R_j$ or $x_2 < -R_j$.  \n",
    "The contribution is 0: the quadrant does not intersect the circle $|y| = R_j$.\n",
    "1. $x_1, x_2 > R_j$.  \n",
    "The contribution is $1/n$: the quadrant contains the entire circle $|y| = R_j$.\n",
    "1. $x_1^2 + x_2^2 \\le R_j^2$.  \n",
    "The quadrant includes an arc that is at most half the circle.  \n",
    "Let the points at which the quadrant boundary intersects\n",
    "the circle be $(x_1', x_2)$ and $(x_1, x_2')$.  Then $x_1'$ is the negative\n",
    "root of $x_1^{'2} = R_j^2 - x_2^2$ and $x_2'$ is the negative root\n",
    "of $x_2^{'2} = R_j^2 - x_1^2$.\n",
    "The fraction of the circle included in $Q(x)$ is\n",
    "$$\n",
    "\\frac{1}{\\pi} \\sin^{-1} \\frac{1}{\\sqrt{2}} \\left ( 1 + \\frac{x_1}{R_j} \\sqrt{1 - \\frac{x_2^2}{R_j^2}}\n",
    "+ \\frac{x_2}{R_j} \\sqrt{1 - \\frac{x_1^2}{R_j^2}} \\right )^{1/2}.\n",
    "$$\n",
    "1. $x_1^2 + x_2^2 > R_j^2$, $-R_j < x_1 \\le 0$, $x_2 \\ge 0$.  \n",
    "The fraction of the circle within $Q(x)$ is\n",
    "$$\n",
    "q(x_1) \\equiv \\frac{1}{\\pi} \\sin^{-1} \\frac{1}{\\sqrt{2}} \\left ( 1 - \\frac{x_1^2}{R_j^2} \\right )^{1/2}.\n",
    "$$\n",
    "1. $x_1^2 + x_2^2 > R_j^2$, $0 \\le x_1 < R_j$, $x_2 \\ge R_j$.  \n",
    "The fraction of the circle within $Q(x)$ is $1 - q(x_1)$.\n",
    "1. $x_1^2 + x_2^2 > R_j^2$, $x_1 \\ge 0$, $-R_j < x_2 < 0$.  \n",
    "The fraction of the circle within $Q(x)$ is $q(x_2)$.\n",
    "1. $x_1^2 + x_2^2 > R_j^2$, $x_1 \\ge R_j$, $0 \\le x_2 < R_j$.  \n",
    "The fraction of the circle within $Q(x)$ is $1-q(x_2)$.\n",
    "1. $x_1^2 + x_2^2 > R_j^2$, $0 \\le x_1 < R_j$, $0 \\le x_2 < R_j$.  \n",
    "The fraction of the circle within $Q(x)$ is $1 - q(x_1) - q(x_2)$.\n",
    "\n",
    "At which points $x$ should we evaluate the discrepancy \n",
    "$ D(x) = |\\hat{P}_n(Q(x)) - \\tau \\hat{P}_n (Q(x))|$?\n",
    "\n",
    "Let $R = \\max_j R_j$.  Then for $x_1, x_2 > R$, $D(x) = 0$.\n",
    "Similarly, for $x_1, x_2 < -R$, $D(x) = 0$.\n",
    "\n",
    "We might take $x$ on a fine grid in the square $[-R, R] \\times [-R, R]$, but this is wasteful.\n",
    "\n",
    "Some thought shows that the maximum discrepancy occurs when some datum is just included\n",
    "in $Q(x)$, which makes $\\hat{P}_n$ relatively large compared with $\\tau \\hat{P}_n$, or when\n",
    "some datum is just excluded from $Q(x)$,\n",
    "which makes $\\tau \\hat{P}_n$ relatively large compared with $\\hat{P}_n$.\n",
    "\n",
    "The possible points of maximum discrepancy are $x$ of the form $(X_{1j}-s\\epsilon, X_{2k}-s\\epsilon)$ with\n",
    "$1 \\le j, k \\le n$, $s \\in \\{0, 1\\}$, and $\\epsilon$ small, together with the points\n",
    "$(X_{1j}-s\\epsilon, R)$ and $(R, X_{2j}-s\\epsilon)$.\n",
    "\n",
    "This is a large ($2n^2 + 4n$) but finite number of points.\n",
    "Denote this set by $\\mathcal{X} (\\{X_j\\}, \\epsilon)$.\n",
    "\n",
    "To draw an iid sample of size $n$ from $\\tau \\hat{P}_n$, we draw $n$ values\n",
    "iid uniform on $\\{r_j\\}_{j=1}^n$ and draw $n$ iid $U[0, 2\\pi]$ random variables,\n",
    "and treat these as the polar coordinates $(r, \\theta)$ of $n$ points in $\\Re^2$.\n",
    "\n",
    "To test the null hypothesis of rotational invariance, we would compute\n",
    "$$\n",
    "    T(X) = \\max_{x \\in \\Re^k : x \\in \\mathcal{X} (\\{X_j\\}, \\epsilon)}\n",
    "    | \\hat{P}_n (Q(x)) - \\tau \\hat{P}_n(Q(x)) |\n",
    "$$\n",
    "from the data $X$, then repeatedly draw iid samples $\\{X_j^*\\}$ of size $n$ from $\\tau \\hat{P}_n$,\n",
    "computing\n",
    "$$\n",
    "    T(X^*) = \\max_{x \\in \\Re^k : x \\in \\mathcal{X} (\\{X_j^*\\}, \\epsilon) }\n",
    "    | \\hat{P}_n^* (Q(x)) - \\tau \\hat{P}_n^*(Q(x)) |\n",
    "$$\n",
    "for each.\n",
    "\n",
    "We would reject the null hypothesis\n",
    "that $P$ is rotationally invariant (at approximate significance level $\\alpha$) if\n",
    "$T(X)$ exceeds the $1-\\alpha$ quantile of the simulated distribution of $T(X^*)$.\n",
    "\n",
    "Under the null hypothesis, the distribution of the data is invariant under the action\n",
    "of the rotation group.  \n",
    "\n",
    "This is not a finite group, so we cannot exhaust the\n",
    "set of transformations on a computer.  \n",
    "\n",
    "However, we might consider the subgroup of\n",
    "rotations by multiples of $2\\pi/M$ for some large integer $M$.\n",
    "We could get an alternative approximate level $\\alpha$ test of the hypothesis\n",
    "of rotational invariance by comparing $T(X)$ with the $1-\\alpha$ quantile of\n",
    "$T$ over all such rotations of the data&mdash;the orbit of the data under this finite\n",
    "subgroup."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Application: testing whether seismicity follows a spatially heterogeneous, temporally homogeneous Poisson Process\n",
    "\n",
    "Reference: Luen and Stark, 2012. http://onlinelibrary.wiley.com/doi/10.1111/j.1365-246X.2012.05400.x/pdf\n",
    "\n",
    "Poisson process: condition on number of events. Given the number of events, temporal distribution uniform, times exchangeable.\n",
    "\n",
    "What's the \"projection\" operation?\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<link href='http://fonts.googleapis.com/css?family=Lora|Open+Sans' rel='stylesheet' type='text/css'>\n",
       "<style>\n",
       "\n",
       "font-family: 'Lora', serif;\n",
       "\n",
       ".MathJax_Display {\n",
       "  padding: 10px;\n",
       "}\n",
       "\n",
       "div.callout {\n",
       "  color: #000000;\n",
       "  background-color: #DDDDDD;\n",
       "  margin: 20px 20px 20px 20px;\n",
       "  border-style: solid;\n",
       "  border-width: 2px;\n",
       "  padding: 10px 10px;\n",
       "}\n",
       "\n",
       ".rendered_html {\n",
       "  color: #2C5494;\n",
       "  font-family: 'Lora', serif;\n",
       "  font-size: 140%;\n",
       "  line-height: 1.1;\n",
       "  margin: 0.5em 0;\n",
       "}\n",
       "\n",
       "div.cell {\n",
       "    width:900px;\n",
       "    margin-left:auto;\n",
       "    margin-right:auto;\n",
       "}\n",
       "\n",
       "div.text_cell_render {\n",
       "    width:800px;\n",
       "    margin-left:auto;\n",
       "    margin-right:auto;\n",
       "}\n",
       "\n",
       "\n",
       ".title {\n",
       "  font-family: 'Open Sans', sans-serif;\n",
       "  color: #4773D1;\n",
       "  font-size: 250%;\n",
       "  font-weight:bold;\n",
       "  line-height: 1.2;\n",
       "  margin: 0.5em 0;\n",
       "}\n",
       "\n",
       ".subtitle {\n",
       "  font-family: 'Open Sans', sans-serif;\n",
       "  color: #386BBC;\n",
       "  font-size: 180%;\n",
       "  font-weight:bold;\n",
       "  line-height: 1.2;\n",
       "  margin: 0.5em 0;\n",
       "}\n",
       "\n",
       ".slide-header, p.slide-header {\n",
       "  color: #4773D1;\n",
       "  font-size: 200%;\n",
       "  font-weight:bold;\n",
       "  margin: 0px 20px 10px;\n",
       "  page-break-before: always;\n",
       "  text-align: center;\n",
       "}\n",
       "\n",
       ".rendered_html .code {\n",
       "  background-color: #FFFFFF;\n",
       "  font-family: Consolas;\n",
       "}\n",
       "\n",
       ".rendered_html h1 {\n",
       "  color: #7898DD;\n",
       "  font-family: 'Open Sans', sans-serif;\n",
       "  line-height: 1.2;\n",
       "  margin: 0.15em 0em 0.5em;\n",
       "  page-break-before: always;\n",
       "}\n",
       "\n",
       "\n",
       ".rendered_html h2 {\n",
       "  color: #4773D1;\n",
       "  line-height: 1.2;\n",
       "  margin: 1.1em 0em 0.5em;\n",
       "}\n",
       "\n",
       ".rendered_html h3 {\n",
       "  font-size: 100%;\n",
       "  line-height: 1.2;\n",
       "  margin: 1.1em 0em 0.5em;\n",
       "}\n",
       "\n",
       ".rendered_html .definition, .proposition, .proof, .theorem {\n",
       "    padding-top: 20px;\n",
       "    color: #222299;\n",
       "    font-size: 120%;\n",
       "    font-style: italic;\n",
       "}\n",
       "\n",
       ".definition, .proposition, .theorem {\n",
       "  background-color: #EEEEEE;\n",
       "  border-style: solid;\n",
       "  border-width: 2px;\n",
       "  padding-left: 20px;\n",
       "  padding-right: 20px;\n",
       "}\n",
       "\n",
       ".rendered_html .definition::before{\n",
       "    content: \"Definition:\";\n",
       "    background-color: #DDDDDD;\n",
       "    color: #222299;\n",
       "    font-size: 110%;\n",
       "    font-weight: bold;\n",
       "    font-style: normal;\n",
       "}\n",
       "\n",
       ".rendered_html .proposition::before{\n",
       "    content: \"Proposition:\";\n",
       "    background-color: #DDDDDD;\n",
       "    color: #222299;\n",
       "    font-size: 110%;\n",
       "    font-weight: bold;\n",
       "    font-style: normal;\n",
       "}\n",
       "\n",
       ".rendered_html .proof::before{\n",
       "    content: \"Proof:\";\n",
       "    background-color: #DDDDDD;\n",
       "    color: #222299;\n",
       "    font-size: 110%;\n",
       "    font-weight: bold;\n",
       "    font-style: normal;\n",
       "}\n",
       "\n",
       ".rendered_html .theorem::before{\n",
       "    content: \"Theorem:\";\n",
       "    background-color: #DDDDDD;\n",
       "    color: #222299;\n",
       "    font-size: 110%;\n",
       "    font-weight: bold;\n",
       "    font-style: normal;\n",
       "}\n",
       "\n",
       "\n",
       ".rendered_html ol li {\n",
       "  padding-top: 20px;\n",
       "  padding-bottom: -20px;\n",
       "  line-height: 1.5;\n",
       "}\n",
       "\n",
       ".rendered_html ul li {\n",
       "  padding-top: 0px;\n",
       "  padding-bottom: 0px;\n",
       "  line-height: 1.2;\n",
       "}\n",
       "\n",
       "li:first-of-type {\n",
       "  padding-top: -100px;\n",
       "}\n",
       "\n",
       ".input_prompt, .CodeMirror-lines, .output_area {\n",
       "  font-family: Consolas;\n",
       "  font-size: 120%;\n",
       "}\n",
       "\n",
       ".gap-above {\n",
       "  padding-top: 200px;\n",
       "}\n",
       "\n",
       ".gap01 {\n",
       "  padding-top: 10px;\n",
       "}\n",
       "\n",
       ".gap05 {\n",
       "  padding-top: 50px;\n",
       "}\n",
       "\n",
       ".gap1 {\n",
       "  padding-top: 100px;\n",
       "}\n",
       "\n",
       ".gap2 {\n",
       "  padding-top: 200px;\n",
       "}\n",
       "\n",
       ".gap3 {\n",
       "  padding-top: 300px;\n",
       "}\n",
       "\n",
       ".emph {\n",
       "  color: #386BBC;\n",
       "}\n",
       "\n",
       ".warn {\n",
       "  color: red;\n",
       "}\n",
       "\n",
       ".center {\n",
       "  text-align: center;\n",
       "}\n",
       "\n",
       ".nb_link {\n",
       "    padding-bottom: 0.5em;\n",
       "}\n",
       "\n",
       "body {\n",
       "    background-color: #ffffff;\n",
       "    counter-reset: fncounter;\n",
       "    counter-reset: h1counter;\n",
       "}\n",
       "\n",
       "h1,h2 {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    text-align: center;\n",
       "    margin-top: 2em;\n",
       "}\n",
       "\n",
       "h1.compact {\n",
       "    margin-top: 0;\n",
       "}\n",
       "\n",
       "h3,h4,h5,h6 {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    text-align: left;\n",
       "    margin-left: 5%;\n",
       "    margin-top: 2em;\n",
       "    margin-right:  0em;\n",
       "    padding-right: 0em;\n",
       "}\n",
       "\n",
       "blockquote {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    margin-left: 10%;\n",
       "    margin-right: 10%;\n",
       "}\n",
       "\n",
       "p,table,li,dl,address {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    margin-left: 0%;\n",
       "    margin-right: 0%;\n",
       "}\n",
       "\n",
       "dd {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    margin-left: 5%;\n",
       "    margin-right: 0%;\n",
       "    font-size: 80%;\n",
       "}\n",
       "\n",
       "fieldset.narrow {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    margin-left: 5%;\n",
       "    margin-right: 5%;\n",
       "}\n",
       "\n",
       "legend {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 80%;\n",
       "}\n",
       "\n",
       "ul.noBullet {\n",
       "    list-style-type: none;\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    margin-left: -3em;\n",
       "    margin-right: 0em;\n",
       "    font-size: 90%;\n",
       "}\n",
       "\n",
       "ul.noBulletExtraSpace {\n",
       "    list-style-type: none;\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    margin-left: -3em;\n",
       "    margin-right: 0em;\n",
       "    margin-bottom: 1em;\n",
       "    font-size: 100%;\n",
       "}\n",
       "\n",
       "ul.noBulletExtraSpace li {\n",
       "    margin-bottom: 1em;\n",
       "}\n",
       "\n",
       "p,li,th,td {\n",
       "    font-size: 100%;\n",
       "}\n",
       "\n",
       "p.inline {\n",
       "    display: inline;\n",
       "    margin-left: 0;\n",
       "    margin-right: 0;\n",
       "}\n",
       "\n",
       "div.boxContents {\n",
       "    text-align: center;\n",
       "    line-height: 2em;\n",
       "    margin-left: auto;\n",
       "    margin-right: auto;\n",
       "    margin-bottom: 5%;\n",
       "    margin-top: 5%;\n",
       "    padding-bottom: 10px;\n",
       "}\n",
       "\n",
       "p.boxTickets {\n",
       "    text-align: center;\n",
       "    display: inline;\n",
       "    padding: 10px 10px 10px 10px;\n",
       "    color: #000000;\n",
       "    background: #888888;\n",
       "    border: solid #888888;\n",
       "    border-width: thick;\n",
       "    border-style: outset;\n",
       "    line-height: 4em;\n",
       "}\n",
       "\n",
       "p.boxLabel {\n",
       "    text-align: center;\n",
       "    font-variant: small-caps;\n",
       "    padding-top: 10%;\n",
       "    color: #000055;\n",
       "}\n",
       "\n",
       "p.math {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    color: #000000;\n",
       "    text-align: center;\n",
       "    font-style: italic;\n",
       "}\n",
       "\n",
       "p.inlineMath {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    text-align: center;\n",
       "    font-style: italic;\n",
       "    display: inline;\n",
       "}\n",
       "\n",
       "p.figure {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    text-align: center;\n",
       "}\n",
       "\n",
       "p.center {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    text-align: center;\n",
       "}\n",
       "\n",
       "p.big {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    text-align: left;\n",
       "    font-size: 130%;\n",
       "}\n",
       "\n",
       "p.bigCenter {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    text-align: center;\n",
       "    font-size: 130%;\n",
       "}\n",
       "\n",
       "p.example {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    margin-left: 10%;\n",
       "    margin-right: 10%;\n",
       "    font-style: italic;\n",
       "}\n",
       "\n",
       "table.dataTable {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 80%;\n",
       "    margin-left: 3%;\n",
       "    margin-right: 3%;\n",
       "    border: solid #555555;\n",
       "}\n",
       "\n",
       "table.dataTable th {\n",
       "    border-right: 1px solid #999999;\n",
       "    border-bottom: 1px solid #999999;\n",
       "}\n",
       "\n",
       "table.dataTable td {\n",
       "    border-right: 1px solid #999999;\n",
       "    border-bottom: 1px solid #999999;\n",
       "}\n",
       "\n",
       "table.truthTable {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    margin-left: 3%;\n",
       "    margin-right: 3%;\n",
       "    border: solid #0000FF;\n",
       "}\n",
       "\n",
       "table.truthTable th {\n",
       "    border-right: 1px solid #999999;\n",
       "    border-bottom: 1px solid #999999;\n",
       "}\n",
       "\n",
       "table.truthTable td {\n",
       "    border-right: 1px solid #999999;\n",
       "    border-bottom: 1px solid #999999;\n",
       "}\n",
       "\n",
       "table.truthTable caption {\n",
       "    font-weight: bold;\n",
       "}\n",
       "\n",
       "div.boxModel {\n",
       "    display: block;\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 120%;\n",
       "    min-height: 6em;\n",
       "    margin-top: 1.5em;\n",
       "    margin-left: 35%;\n",
       "    margin-right: 35%;\n",
       "    margin-bottom: 2em;\n",
       "    border-width: thick;\n",
       "    border-top: none;\n",
       "    border-left: solid #000000;\n",
       "    border-right: solid #000000;\n",
       "    border-bottom: solid #000000;\n",
       "    background: #dedeff;\n",
       "}\n",
       "\n",
       "div.problem {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    margin-top: 1.5em;\n",
       "    margin-left: 10%;\n",
       "    margin-right: 10%;\n",
       "    border: solid #009900;\n",
       "    background: #eeffee;\n",
       "}\n",
       "\n",
       "div.indent {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    margin-top: 1.5em;\n",
       "    margin-bottom: 1em;\n",
       "    margin-left: 5%;\n",
       "    margin-right: 5%;\n",
       "}\n",
       "\n",
       "div.code {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    margin-top: 1.5em;\n",
       "    margin-left: 10%;\n",
       "    margin-right: 10%;\n",
       "    border: solid #0066ff;\n",
       "    background: #eeeedd;\n",
       "}\n",
       "\n",
       "\n",
       "div.table {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    margin-left: 5%;\n",
       "    margin-right: 5%;\n",
       "    margin-bottom: 2em;\n",
       "    margin-top: 2em;\n",
       "    border: solid #000099;\n",
       "    background: #ccccff;\n",
       "}\n",
       "\n",
       "div.plainTable {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    margin-left: 5%;\n",
       "    margin-right: 5%;\n",
       "    margin-bottom: 2em;\n",
       "    margin-top: 2em;\n",
       "}\n",
       "\n",
       "div.example {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    margin-top: 1.5em;\n",
       "    margin-left: 10%;\n",
       "    margin-right: 10%;\n",
       "    border: solid #0000ff;\n",
       "    background: #eeeeff;\n",
       "}\n",
       "\n",
       "div.caption {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 120%;\n",
       "    font-weight: bold;\n",
       "    color: #000099;\n",
       "    margin-left: 0%;\n",
       "    margin-right: 5%;\n",
       "    text-align: left;\n",
       "}\n",
       "\n",
       "div.figure {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    border: solid #808080;\n",
       "    margin-left: 5%;\n",
       "    margin-right: 5%;\n",
       "    text-align: center;\n",
       "}\n",
       "\n",
       "div.solution {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 100%;\n",
       "    color: #000099;\n",
       "    margin-left: 5%;\n",
       "    margin-right: 5%;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       "div.callout {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 105%;\n",
       "    font-weight: bold;\n",
       "    border: solid #ff0000;\n",
       "    background: #ffeeee;\n",
       "    margin-left: 10%;\n",
       "    margin-right: 10%;\n",
       "    padding:     2% 0% 2% 0%;\n",
       "    text-align: left;\n",
       "}\n",
       "\n",
       "div.solution {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 85%;\n",
       "    color: #000099;\n",
       "    margin-left: 0%;\n",
       "    margin-right: 0%;\n",
       "    display: none;\n",
       "}\n",
       "\n",
       "\n",
       "h1,h2,h3{\n",
       "    color:#000000;\n",
       "}\n",
       "\n",
       "hr {\n",
       "    height: 3px;\n",
       "    color:#000000;\n",
       "    width: 90%;\n",
       "    text-align:center;\n",
       "}\n",
       "\n",
       "\n",
       "a:link    {\n",
       "    color:#0000ff;\n",
       "    text-decoration: none;\n",
       "}\n",
       "\n",
       "a:visited {color:#000fff}\n",
       "a:active  {color:#ff0033}\n",
       "a:hover   {\n",
       "    color: #000000;\n",
       "    background:silver;\n",
       "}\n",
       "a.glossRef:visited {color:#107080}\n",
       "\n",
       "a.fnLink:link {color:#800080}\n",
       "\n",
       "span.defSpan {\n",
       "     font-size: 100%;\n",
       "}\n",
       "\n",
       "span.appCtrlName {\n",
       "     font-stretch: wider;\n",
       "     color:  #800000;\n",
       "     font-size: 100%;\n",
       "     margin-left: 0%;\n",
       "}\n",
       "\n",
       "span.calloutCaption {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-size: 120%;\n",
       "    font-weight: bold;\n",
       "    color: #000000;\n",
       "}\n",
       "\n",
       "/*\n",
       "span.math {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    color:  #000085;\n",
       "    text-align: center;\n",
       "    font-style: italic;\n",
       "}\n",
       "*/\n",
       "\n",
       "span.example {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    font-style: italic;\n",
       "}\n",
       "\n",
       "span.qSpan {\n",
       "    font-family: helvetica, arial, 'sans serif';\n",
       "    color: #009900;\n",
       "}\n",
       "\n",
       "span.termOfArt {\n",
       "    font-weight: bold;\n",
       "    font-variant: small-caps;\n",
       "    font-size: 105%;\n",
       "    font-stretch: wider;\n",
       "}\n",
       "\n",
       "\n",
       "pre {\n",
       "    font-family: monospace;\n",
       "}\n",
       "\n",
       "span.big {\n",
       "   font-size:        120%;\n",
       "}\n",
       "\n",
       "\n",
       "/*   CSS for drawing charts   */\n",
       "\n",
       "div.chart {\n",
       "    position:         relative;\n",
       "    clear:            both;\n",
       "    display:          block;\n",
       "    width:            90%;\n",
       "    min-height:       25em;\n",
       "    height:           auto !important;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    font-size:        100%;\n",
       "    text-align:       center;\n",
       "    margin:           auto;\n",
       "}\n",
       "\n",
       "div.chartCaption {\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    font-size:        120%;\n",
       "    font-weight:      bold;\n",
       "    text-align:       center;\n",
       "    margin:           auto;\n",
       "    margin-bottom:    2em;\n",
       "}\n",
       "\n",
       "div.horizontalPipe {\n",
       "    z-index:          0;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    font-size:        60%;\n",
       "    color:            #ffffff;\n",
       "    background-color: #000099;\n",
       "    border:           none;\n",
       "    margin:           auto;\n",
       "    text-align:       center;\n",
       "}\n",
       "\n",
       "div.verticalPipe {\n",
       "    z-index:          0;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    font-size:        60%;\n",
       "    color:            #ffffff;\n",
       "    background-color: #000099;\n",
       "    border:           none;\n",
       "    margin:           auto;\n",
       "    text-align:       center;\n",
       "}\n",
       "\n",
       "a.chart {\n",
       "    display:          block;\n",
       "    color:            #000000;\n",
       "    background-color: #f0f0ff;\n",
       "    text-decoration:  none;\n",
       "}\n",
       "\n",
       "a.chart:hover {\n",
       "    color:            #900000;\n",
       "    background-color: #f0f0ff;\n",
       "    text-decoration:  none;\n",
       "}\n",
       "\n",
       "div.venn {\n",
       "    position:         relative;\n",
       "    clear:            right;\n",
       "    display:          block;\n",
       "    width:            25%;\n",
       "    min-height:       14em;\n",
       "    height:           auto !important;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    font-size:        100%;\n",
       "    text-align:       center;\n",
       "    margin:           auto;\n",
       "}\n",
       "\n",
       "div.vennCaption {\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    font-size:        120%;\n",
       "    font-weight:      bold;\n",
       "    text-align:       center;\n",
       "    margin:           auto;\n",
       "    margin-bottom:    2em;\n",
       "}\n",
       "\n",
       "div.vennUniverse {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            90%;\n",
       "    min-height:       10em;\n",
       "    height:           10em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           2%;\n",
       "    left:             2%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect40x30_left_high {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            40%;\n",
       "    min-height:       3em;\n",
       "    height:           3em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           13%;\n",
       "    left:             20%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect40x50_left {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            40%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           10%;\n",
       "    left:             4%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect70x70_left {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            70%;\n",
       "    min-height:       7em;\n",
       "    height:           7em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           10%;\n",
       "    left:             4%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect40x50_left_high {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            40%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           13%;\n",
       "    left:             4%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect11x50_left_high {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            11%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           13%;\n",
       "    left:             4%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect30x40_left {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            30%;\n",
       "    min-height:       4em;\n",
       "    height:           4em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           10%;\n",
       "    left:             4%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect20x30_left {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            20%;\n",
       "    min-height:       3em;\n",
       "    height:           3em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           18%;\n",
       "    left:             5%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect15x30_left {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            15%;\n",
       "    min-height:       3em;\n",
       "    height:           3em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           18%;\n",
       "    left:             7%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "\n",
       "div.rect20x30_center {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            20%;\n",
       "    min-height:       3em;\n",
       "    height:           3em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           18%;\n",
       "    left:             38%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect20x30_center_left {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            20%;\n",
       "    min-height:       3em;\n",
       "    height:           3em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           18%;\n",
       "    left:             22%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect40x50_center {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            40%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           10%;\n",
       "    left:             28%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect40x50_center_high {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            40%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           15%;\n",
       "    left:             28%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect30x60_center {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            30%;\n",
       "    min-height:       6em;\n",
       "    height:           6em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           12%;\n",
       "    left:             33%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect60x70_center {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            60%;\n",
       "    min-height:       7em;\n",
       "    height:           7em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           10%;\n",
       "    left:             18%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect85x80_center {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            85%;\n",
       "    min-height:       8em;\n",
       "    height:           8em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           5%;\n",
       "    left:             4%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect45x50_right_high {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            45%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           15%;\n",
       "    left :            42%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect40x50_right {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            40%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           10%;\n",
       "    left :            50%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect40x50_right_high {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            40%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           15%;\n",
       "    left:             50%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect30x30_right {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            30%;\n",
       "    min-height:       3em;\n",
       "    height:           3em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    text-align:       right;\n",
       "    bottom:           15%;\n",
       "    left :            60%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect30x30_right_high {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            30%;\n",
       "    min-height:       3em;\n",
       "    height:           3em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           18%;\n",
       "    left:             55%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect30x40_right {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            30%;\n",
       "    min-height:       4em;\n",
       "    height:           4em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    font-size:        100%;\n",
       "    bottom:           13%;\n",
       "    left:             60%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect25x35_right {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            25%;\n",
       "    min-height:       3.5em;\n",
       "    height:           3.5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           13.5%;\n",
       "    left:             55%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect28x50_right {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            28%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           15%;\n",
       "    left:             50%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect24x50_right {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            24%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           15%;\n",
       "    left:             50%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "\n",
       "div.rect18x40_right {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            18%;\n",
       "    min-height:       4em;\n",
       "    height:           4em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           13%;\n",
       "    left:             60%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect12x50_right {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            12%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           15%;\n",
       "    left:             66%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect10x30_left {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            10%;\n",
       "    min-height:       3em;\n",
       "    height:           3em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           18%;\n",
       "    left:             5%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       "div.rect6x50_right {\n",
       "    position:         absolute;\n",
       "    padding:          0.2em;\n",
       "    display:          block;\n",
       "    width:            6%;\n",
       "    min-height:       5em;\n",
       "    height:           5em;\n",
       "    font-family:      helvetica, arial, 'sans serif';\n",
       "    bottom:           15%;\n",
       "    left:             57%;\n",
       "    border-color:     #000000;\n",
       "    border-style:     solid;\n",
       "    border-width:     3px;\n",
       "}\n",
       "\n",
       ".left {\n",
       "    text-align:       left;\n",
       "}\n",
       "\n",
       ".center {\n",
       "    text-align:       center;\n",
       "}\n",
       "\n",
       ".right {\n",
       "    text-align:       right;\n",
       "}\n",
       "\n",
       "\n",
       "\n",
       ".blue {\n",
       "    background-color: #4444ff;\n",
       "}\n",
       "\n",
       ".yellow {\n",
       "    background-color: #cccc00;\n",
       "}\n",
       "\n",
       ".gray {\n",
       "    background-color: #cccccc;\n",
       "}\n",
       "\n",
       ".green {\n",
       "    background-color: #44ff44;\n",
       "}\n",
       "\n",
       ".white {\n",
       "    background-color: #ffffff;\n",
       "}\n",
       "\n",
       "\n",
       "</style>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%run talkTools.py"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}