The Monte Carlo method is a widely used statistical technique that leverages the power of randomness to solve complex mathematical problems and simulate the behavior of various systems. It’s a method that has found applications across diverse fields, including physics, finance, engineering, and biology. In this blog post, we’ll dive deeper into the Monte Carlo method and explore the mathematics behind it, along with a discussion of random number generators like Linear Congruential Generators (LCGs) and the infamous RANDU.\n", "
\n", "\n", "\n", "### The Monte Carlo Method\n", "\n", "\n",
" The Monte Carlo method is based on the idea of using randomness to approximate solutions to problems that may be deterministic in nature but are too complex for analytical methods. The name \"Monte Carlo\" is a nod to the randomness associated with the famous casino in Monaco.
\n",
"
\n",
" The basic principle behind the Monte Carlo method is to simulate the behavior of a system by generating random samples and using them to estimate the desired quantities. Let’s consider a mathematical problem where we need to compute an integral that does not have a straightforward analytical solution:\n",
"
\n", " The Monte Carlo method approximates this integral by sampling random points $x_i$ uniformly from the interval $[a, b]$ and evaluating the function $f(x)$ at these points. The integral can then be approximated as:\n", "
\n", "\n", "\n", "\\begin{align*}\n", "I \\approx \\frac{b - a}{N} \\sum_{i=1}^{N} f(x_i)\n", "\\end{align*}\n", "\n", "\n",
" where $N$ is the number of random samples. As $N$ increases, the approximation becomes more accurate, thanks to the Law of Large Numbers.
\n",
"
\n",
" This approach is particularly useful for high-dimensional integrals, where traditional numerical integration methods become computationally expensive or infeasible.\n",
"
\n", " At the heart of the Monte Carlo method lies the generation of random numbers. In practice, most simulations do not use true random numbers but rather pseudorandom numbers generated by deterministic algorithms. These pseudorandom number generators (PRNGs) produce sequences that mimic the properties of true randomness.\n", "
\n", "\n", "#### Linear Congruential Generator (LCG)\n", "\n", "One of the most commonly used PRNGs is the **Linear Congruential Generator (LCG)**. The LCG generates a sequence of numbers $X_1, X_2, X_3, \\ldots$ using the recursive relation:\n", "\n", "\\begin{align*}\n", "X_{n+1} &= (aX_n + c) \\mod m\n", "\\end{align*} \n", "\n", "where: \n", "\n", "- $X_n$ is the $n$-th number in the sequence.\n", "- $a$ is the multiplier.\n", "- $c$ is the increment.\n", "- $m$ is the modulus.\n", "\n", "\n",
" The sequence starts with an initial value $X_0$, known as the seed, and the parameters $a$, $c$, and $m$ are carefully chosen to maximize the period and quality of the generated sequence.
\n",
"
\n",
" The quality of the LCG depends on the choice of these parameters. For instance, to achieve a full period (i.e., the sequence cycles through all possible values before repeating), the following conditions must be met:\n",
"
\n",
" Although RANDU was widely used in the 1960s and 1970s due to its simplicity, it was later discovered to produce sequences with significant correlations. For example, points generated using RANDU tend to lie on a small number of planes in three-dimensional space, which can severely impact the accuracy of Monte Carlo simulations.
\n",
"
\n",
" The generator's flaws arise from poor parameter selection. In RANDU, the modulus $m = 2^{31}$ and the multiplier $a = 65539$ result in a sequence with poor distribution properties. As a consequence, RANDU’s generated numbers do not pass modern statistical tests for randomness, rendering it unsuitable for serious applications.
\n",
"
\n",
" Let's solve some math problems and visualize randomness.\n",
"
\n", " The above relation tells us some interesting fact. If we uniformly create as many points as possible inside the square then the number of points inside the circle will be approximately 4 times the number of the points outside the circular region.\n", "
" ] }, { "cell_type": "code", "execution_count": 6, "id": "c2c1e1ff", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Monte Carlo estimated value of π from 10000 points = 3.136800\n" ] } ], "source": [ "#| code-fold: false\n", "\n", "def monte_carlo_pi(n):\n", " inside_circle = 0\n", "\n", " for _ in range(n):\n", " x = np.random.uniform(0, 1)\n", " y = np.random.uniform(0, 1)\n", " if x**2 + y**2 <= 1:\n", " inside_circle += 1\n", "\n", " pi_estimate = (inside_circle / n) * 4\n", " return pi_estimate\n", "\n", "# Number of points\n", "n = 10000\n", "print(f\"Monte Carlo estimated value of π from {n} points = {monte_carlo_pi(n):.6f}\")" ] }, { "cell_type": "markdown", "id": "73f897fd", "metadata": {}, "source": [ "That's all for this post. \n", "\n", "## Reference \n", "\n", "- [Okten, G. (1999). Contributions to the theory of Monte Carlo and quasi-Monte Carlo methods. Universal-Publishers.](https://www.amazon.com/Contributions-Theory-Monte-Quasi-Monte-Methods/dp/1581120419){target=\"_blank\"} \n", "\n", "\n", "**Share on** \n", "\n", "::::{.columns}\n", ":::{.column width=\"33%\"}\n", "\n", " \n", "{{< fa brands facebook size=3x >}}\n", "\n", " \n", ":::\n", " \n", ":::{.column width=\"33%\"}\n", "\n", " \n", "{{< fa brands linkedin size=3x >}}\n", "\n", " \n", ":::\n", " \n", ":::{.column width=\"33%\"}\n", "\n", " \n", "{{< fa brands twitter size=3x >}}\n", "\n", " \n", ":::\n", "::::\n", " \n", "\n", " \n", "\n", "\n", " \n", "\n", " **You may also like**\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3", "path": "/opt/hostedtoolcache/Python/3.10.18/x64/share/jupyter/kernels/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.10.18" } }, "nbformat": 4, "nbformat_minor": 5 }