{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true, "jupyter": { "outputs_hidden": true } }, "outputs": [ { "data": { "text/plain": [ "R version 4.2.2 (2022-10-31)\n", "Platform: x86_64-apple-darwin17.0 (64-bit)\n", "Running under: macOS Catalina 10.15.7\n", "\n", "Matrix products: default\n", "BLAS: /Library/Frameworks/R.framework/Versions/4.2/Resources/lib/libRblas.0.dylib\n", "LAPACK: /Library/Frameworks/R.framework/Versions/4.2/Resources/lib/libRlapack.dylib\n", "\n", "locale:\n", "[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8\n", "\n", "attached base packages:\n", "[1] stats graphics grDevices utils datasets methods base \n", "\n", "loaded via a namespace (and not attached):\n", " [1] fansi_1.0.4 crayon_1.5.2 digest_0.6.31 utf8_1.2.2 \n", " [5] IRdisplay_1.1 repr_1.1.5 lifecycle_1.0.3 jsonlite_1.8.4 \n", " [9] evaluate_0.20 pillar_1.8.1 rlang_1.0.6 cli_3.6.0 \n", "[13] uuid_1.1-0 vctrs_0.5.2 IRkernel_1.3.2 tools_4.2.2 \n", "[17] glue_1.6.2 fastmap_1.1.0 compiler_4.2.2 base64enc_0.1-3\n", "[21] pbdZMQ_0.3-9 htmltools_0.5.4" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "sessionInfo()" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true, "jupyter": { "outputs_hidden": true } }, "outputs": [], "source": [ "library(plot3D)\n", "library(ggplot2)\n", "#library(magick)\n", "library(animation)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Random number generation\n", "\n", "## Uniform random number generation\n", "\n", "### Goal\n", "\n", "To generate $U_i \\stackrel{iid}{\\sim} \\text{unif}(0, 1)$.\n", "\n", "* Basis for all other random number generation\n", "* **Fact: NO RANDOM NUMBER IN COMPUTER** --- only look random (PSEUDO-RANDOM)\n", "\n", "### Congruential generator\n", "\n", "\\begin{align*}\n", " x_{i+1} &= a x_i \\mod m, \\quad i=1, 2, \\dotsc \\\\\n", " u_i &= x_i / m.\n", "\\end{align*}\n", "\n", "* Modulus $m$ is a large prime number.\n", "* Multiplier $a$ is a positive integer between 2 and $m-1$.\n", "* Map $f: x \\mapsto ax \\mod m$ maps $\\{1, \\dotsc, m-1\\}$ onto itself and is one-to-one:\n", " - Suppose $x\\in\\{1, \\dotsc, m-1\\}$. Then $f(x) \\neq 0$ since $a$ and $m$ are relatively prime hence $ax$ is not a multiple of $m$. Thus $f$ maps $\\{1, , \\dotsc, m-1\\}$ to $\\{1, , \\dotsc, m-1\\}$.\n", " - If $ay = ax \\mod m$, then $a(y - x) = m k$ for some integer $k$. Since $a$ and $m$ are relatively prime, $y - x = m l$ for some interger $l$. That is, $x = y \\mod m$. Hence map $f$ is one-to-one.\n", " - Since $f$ maps $\\{1, , \\dotsc, m-1\\}$ to $\\{1, , \\dotsc, m-1\\}$ and one-to-one, $f$ is also onto.\n", " \n", "* Note\n", "\\begin{align*}\n", " x_1 &= a x_0 \\mod m \\\\\n", " x_2 &= a x_1 \\mod m = a^2 x_0 \\mod m \\\\\n", " x_3 &= a x_2 \\mod m = a^3 x_0 \\mod m \\\\\n", " & \\vdots \\\\\n", " x_n &= a x_{n-1} \\mod m = a^n x_0 \\mod m\n", "\\end{align*}\n", "Hence if $a^n = 1 \\mod m$ for some $n$, then \n", "$$\n", " x_n = x_0 \\mod m\n", "$$\n", "and the (pseudo)random number generator repeats the sequence. The number $n$ is called the **period** of the RNG, and $x_0$ is called the **seed**.\n", " " ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": true, "jupyter": { "outputs_hidden": true } }, "outputs": [ { "data": { "text/html": [ "\n", "