09_Stochastic_Ex.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 9. Stochastic Methods: Exercise\n",
    "\n",
    "Name: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Integration\n",
    "\n",
    "When an explicit function like $x_n = g(x_1,...,x_{n-1})$ is not available, you can use a binary function that takes 1 within and 0 outside of a region to measure its volume.\n",
    "\n",
    "1) Measure the volume of an n-dimensional sphere using a binary function\n",
    "$$ f(x) = \\left\\{ \\begin{array}{ccc}\n",
    "    1 & \\mbox{if} & \\sum_{i=1}^n x_i^2 \\le 1 \\\\\n",
    "    0 & \\mbox{otherwise} & \\end{array}\\right. $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) Measure the area or volume of a shape of your interest by sampling method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Rejection Sampling\n",
    "Let us generate samples from Gamma distribution \n",
    "$$ p(x; k, \\theta) = \\frac{1}{\\Gamma(k)\\theta^k}x^{k-1}e^{-\\frac{x}{\\theta}} $$\n",
    "with the shape parameter $k>0$ and the scaling parameter $\\theta$ using the gamma function $\\Gamma(k)$ available in `scipy.special`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from scipy.special import gamma\n",
    "from scipy.special import factorial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is how the gamma function looks like, together with factorial at integer values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kmax = 5\n",
    "x = np.linspace(0, kmax, 50)\n",
    "plt.plot(x, gamma(x))\n",
    "plt.plot(range(1,kmax+1), [factorial(k-1) for k in range(1,kmax+1)], 'o')\n",
    "plt.xlabel(\"x\"); plt.ylabel(\"f(x)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1) Define the Gamma density function with arbitrary $k$ and $\\theta$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def p_gamma(x, k=1, theta=1):\n",
    "    \"\"\"density function of gamma distribution\"\"\"\n",
    "    \n",
    "    return "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the exponential distribution $q(x;\\mu)=\\frac{1}{\\mu}e^{-\\frac{x}{\\mu}}$ as the proposal distribution.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def p_exp(x, mu=1):\n",
    "    \"\"\"density function of exponential distribution\"\"\"\n",
    "    return \n",
    "\n",
    "def x_exp(n=1, mu=1):\n",
    "    \"\"\"sample from exponential distribution\"\"\"\n",
    "    y = np.random.random(n)  # uniform in [0,1]\n",
    "    return "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The ratio of the target and proposal distributions is\n",
    "$$ \\frac{p(x;k,\\theta)}{q(x;\\mu)} = \\frac{\\mu}{\\Gamma(k)\\theta^k}x^{k-1}e^{(\\frac{1}{\\mu}-\\frac{1}{\\theta})x}. $$\n",
    "By setting\n",
    "$$ \\frac{d}{dx}\\frac{p(x;k,\\theta)}{q(x;\\mu)} = 0 $$\n",
    "we have\n",
    "$$ \\{(k-1)x^{k-2}+(\\frac{1}{\\mu}-\\frac{1}{\\theta})x^{k-1}\\}e^{(\\frac{1}{\\mu}-\\frac{1}{\\theta})x} = 0. $$\n",
    "Thus at\n",
    "$$ x = \\frac{(k-1)\\mu\\theta}{\\mu-\\theta} $$\n",
    "the ratio $\\frac{p(x;k,\\theta)}{q(x;\\mu)}$ takes the maximum\n",
    "$$ \\frac{\\mu^k}{\\Gamma(k)\\theta}\\left(\\frac{k-1}{\\mu-\\theta}\\right)^{k-1}e^{1-k}. $$\n",
    "2) What is a good choice of $\\mu$ to satisfy  $p(x)\\le cq(x)$ and what is the value of $c$ for that?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By setting $\\mu=k\\theta$, we have $p(x)\\le cq(x)$ with\n",
    "$c=\\frac{k^k}{\\Gamma(k)}e^{1-k}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3) Verify that $cq(x)$ covers $p(x)$ by plotting them for some $k$ and $\\theta$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = 2\n",
    "theta = 2\n",
    "c = (k**k)/gamma(k)*np.exp(1-k)\n",
    "x = np.linspace(0, 10, 50)\n",
    "plt.plot(x, p_gamma(x, k, theta))\n",
    "plt.plot(x, c*p_exp(x, k*theta))\n",
    "plt.xlabel(\"x\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4) Implement a function to general samples from Gamma distribution with arbitorary $k$ and $\\theta$ using rejection sampling from exponential distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def x_gamma(n=1, k=1, theta=1):\n",
    "    \"\"\"sample from gamma distribution by rejection sampling\"\"\"\n",
    "    c = (k**k)/gamma(k)*np.exp(1-k)\n",
    "    #print(\"c =\", c)\n",
    "    xe = x_exp(n, k*theta)\n",
    "    paccept = \n",
    "    accept = np.random.random(n)<paccept\n",
    "    xg = xe[accept]  # rejection sampling\n",
    "    #print(\"accept rate =\", len(xg)/n)\n",
    "    return(xg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "k = 2\n",
    "theta = 2\n",
    "# sample histogram\n",
    "xs = x_gamma(1000, k, theta)\n",
    "plt.hist(xs, bins=20, density=True)\n",
    "# compare with the density function\n",
    "x = np.linspace(0, 10, 100)\n",
    "plt.plot(x, p_gamma(x, k, theta))\n",
    "plt.xlabel(\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Importance Sampling\n",
    "You have $m$ sample values $f(x_i)$ $(i=1,...m)$ at $x_i$ following a normal distribution \n",
    "$$ q(x;\\mu_0,\\sigma_0) = \\frac{1}{\\sqrt{2\\pi \\sigma_0^2}}e^{-\\frac{(x-\\mu_0)^2}{2\\sigma_0^2}}. $$\n",
    "\n",
    "Consider estimating the mean of $f(x)$ for samples with a different normal distribution $p(x;\\mu_1, \\sigma_1)$ by importance sampling\n",
    "$$ E_p[h(x)] = E_q\\left[\\frac{p(x)}{q(x)}h(x)\\right] $$\n",
    "\n",
    "1) What is the importance weight $\\frac{p(x)}{q(x)}$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) Let us consider the simplest case of $f(x)=x$. \n",
    "\n",
    "Generate $m=100$ samples with $\\mu_0=100$ and $\\sigma_0=20$ and take the sample mean $E_q[f(x)]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = 100\n",
    "mu0 = 100\n",
    "sig0 = 20\n",
    "xs = \n",
    "# show histogram\n",
    "plt.hist(xs, bins=20, density=True)\n",
    "plt.xlabel(\"x\")\n",
    "# check the sample mean\n",
    "np.mean(xs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3) Estimate the mean $E_p[f(x)]$ for $\\mu_1=120$ and $\\sigma_1=10$ by importance sampling."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mu1 = 120\n",
    "sig1 = 20\n",
    "importance = \n",
    "mean1 = np.dot(importance, xs)/m\n",
    "print(mean1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4) See how the result changes with different settings of $\\mu_1$, $\\sigma_1$ and sample size $m$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Optional) Try with a different function $f(x)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. MCMC\n",
    "\n",
    "Try applying Metropolis sampling to your own (unnormalized) distribution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}