6  Further Topics

6.1 Partial Differential Equations

How can we solve Partial Differential Equations numerically?

We have seen how to approximate solutions to systems of Ordinary Differential Equations (ODEs) using various timestepping schemes. Many Partial Differential Equations (PDEs) can also be reduced to large systems of ODEs using the method of lines. In this section, we will illustrate this idea for one of the simplest PDEs: the one-dimensional heat equation.

As in the last Chapter, this topic is also vast. Entire fields of science, such as numerical General Relativity, Computational Fluid Mechanics, and Finite Element Analysis, are essentially subfields within the broad topic of Numerical PDEs. Each of those topics has dozens or hundreds of textbooks written on particular aspects of it. We will therefore be extremely cursory, giving a flavour of some ideas that underlie VisualPDE.com and many standard numerical PDE tools, but leaving a “deep” exploration for future study.

6.1.1 The heat equation and boundary conditions

The one-dimensional heat equation describes the diffusion of temperature \(u(x,t)\) in a homogeneous medium: \[ \frac{\partial u}{\partial t} = \alpha \frac{\partial^2 u}{\partial x^2}, \quad x \in [0,L], \quad t > 0, \] where \(\alpha > 0\) is the diffusivity constant. To fully specify the problem, we must also prescribe initial and boundary conditions.

We will use an initial condition: \[ u(x,0) = u_0(x), \] and homogeneous Neumann boundary conditions: \[ \frac{\partial}{\partial x}u(0,t) = \frac{\partial}{\partial x}u(L,t) = 0, \] which correspond physically to an insulated domain where no heat flows in or out through the boundaries.


6.1.2 Spatial discretisation: finite differences

To apply the method of lines, we first discretise the spatial variable \(x\) using a uniform grid of \(N\) nodes. Let: \[ x_j = (j-1) \Delta x, \quad j = 1, 2, \dots, N, \quad \Delta x = L / (N-1), \] so that \(x_1 = 0\) and \(x_N = L\), and define: \[ u_j(t) \approx u(x_j, t). \] The spatial derivatives in the heat equation can be approximated using finite differences. For the second derivative, a centred difference gives: \[ \frac{\partial^2}{\partial x^2}u(x_j,t) \approx \frac{u_{j-1}(t) - 2u_j(t) + u_{j+1}(t)}{(\Delta x)^2}. \]

For the Neumann boundary conditions, we use the concept of ghost nodes, introducing extra nodes \(x_0 = -\Delta x\) and \(x_{N+1} = L + \Delta x\) just outside the domain, with values \(u_0\) and \(u_{N+1}\). To determine these, we approximate the first derivative at the endpoints using forward and backward differences: \[ \frac{u_1 - u_0}{\Delta x} = 0 \quad \Rightarrow \quad u_1 = u_0, \] \[ \frac{u_{N+1} - u_{N}}{\Delta x} = 0 \quad \Rightarrow \quad u_{N+1} = u_{N}. \]


6.1.3 The method of lines formulation

Plugging the finite difference approximation into the heat equation leads to the large system of ODEs for the approximate solution at each gridpoint, \(u_j(t)\): \[ \frac{d}{dt} u_j(t) = \alpha\frac{u_{j-1}(t) - 2u_j(t) + u_{j+1}(t)}{(\Delta x)^2}, \quad j = 1,2,\dots N, \] where we recall that \(u_0=u_1\) and \(u_{N+1} = u_N\), so that two of these equations have a slightly different form.

We can also write this system for the vector: \[ \mathbf{u}(t) = (u_1(t), u_2(t), \dots, u_N(t))^\top. \] We obtain: \[ \frac{d}{dt}\mathbf{u}(t) = \alpha \mathbf{A} \mathbf{u}(t), \] where \(\mathbf{A}\) is the \(N\times N\) matrix defined by: \[ \mathbf{A} = \frac{1}{(\Delta x)^2} \begin{pmatrix} -1 & 1 & 0 & 0 & \cdots & 0\\ 1 & -2 & 1 & 0 & \cdots & 0\\ 0 & 1 & -2 & 1 & \cdots & 0\\ \vdots & & \ddots & \ddots & \ddots & \vdots\\ 0 & \cdots & 0 & 1 & -2 & 1\\ 0 & \cdots & 0 & 0 & 1 & -1 \end{pmatrix}. \] This matrix represents the discrete Laplacian operator with Neumann boundary conditions.


6.1.4 Time discretisation and stability

For example, applying the forward Euler method gives: \[ \mathbf{u}_{n+1} = \mathbf{u}_n + \Delta t \, \alpha \mathbf{A} \mathbf{u}_n. \] This scheme is simple to implement, but its stability depends strongly on the size of \(\Delta t\). For the one-dimensional heat equation, it can be shown that stability requires: \[ \Delta t \leq \frac{(\Delta x)^2}{2\alpha}. \] Violating this condition leads to rapidly growing (unphysical) numerical oscillations.

Alternatively, we can use the backward Euler scheme, which gives: \[ \mathbf{u}_{n+1} = \mathbf{u}_n + \Delta t \, \alpha \mathbf{A} \mathbf{u}_{n+1}. \] This is an implicit system, requiring the solution of a linear system at each timestep: \[ (\mathbf{I} - \Delta t \alpha \mathbf{A})\mathbf{u}_{n+1} = \mathbf{u}_n. \] However, the backward Euler method is A-stable, and therefore unconditionally stable for the heat equation. This means that we can take arbitrarily large timesteps without introducing instability, though accuracy may still require small \(\Delta t\).


6.1.5 Summary

The method of lines converts a PDE into a large system of ODEs by discretising only in space. The resulting ODE system can then be integrated using any of the timestepping methods from Chapter 5. The stability and accuracy of the full PDE scheme are determined by both the spatial discretisation and the ODE integrator used in time.

The same approach applies to reaction–diffusion systems, in which several chemical or biological species \(u, v, \ldots\) diffuse and react, for example \[ \frac{\partial u}{\partial t} = D_u\frac{\partial^2 u}{\partial x^2} + f(u,v), \qquad \frac{\partial v}{\partial t} = D_v\frac{\partial^2 v}{\partial x^2} + g(u,v). \] Discretising in space gives \(\mathbf{u}' = D_u\mathbf{A}\mathbf{u} + f(\mathbf{u},\mathbf{v})\) and \(\mathbf{v}' = D_v\mathbf{A}\mathbf{v} + g(\mathbf{u},\mathbf{v})\), where \(f\) and \(g\) act componentwise. The eigenvalues of \(\mathbf{A}\) are as large as \(4/(\Delta x)^2\) in magnitude, so the diffusion terms force an explicit method to take \(\Delta t = O\big((\Delta x)^2\big)\), even when the solution itself changes slowly. Such systems are therefore stiff (Chapter 5), and are usually integrated with implicit, adaptive solvers designed for stiff problems, such as MATLAB’s ode15s. Despite their simple form, reaction–diffusion systems can produce remarkably rich behaviour, including spatial patterns, travelling waves and spatiotemporal chaos, which you can explore on VisualPDE.com.

On the Blackboard page are several code demos for the Heat equation, using both the matrix approach and a for-loop approach to discretising this equation. A demo is also provided for the Schnakenberg system of reaction-diffusion equations.

6.2 Monte Carlo Methods

How can random numbers compute things that are not random?

Many quantities in applied mathematics are averages: the expected payoff of a financial contract, the mean energy of a magnet in statistical physics, the probability that a structure fails under random loads. Each of these is an integral, and often an integral over a space of very high dimension. The Monte Carlo method estimates such integrals by averaging the integrand at randomly chosen points. It was developed by Stan Ulam, John von Neumann and Nicholas Metropolis at Los Alamos in the 1940s to simulate neutron transport, and is named after the casinos of Monte Carlo.

In this section we will see how computers produce random numbers, how to turn an average of random samples into an estimate with an error bar, and, most importantly, why this apparently crude method is the method of choice for integrals in high dimensions.

6.2.1 Pseudorandom numbers

A computer executes deterministic instructions, so it cannot compute truly random numbers. Instead it produces pseudorandom numbers: a deterministic sequence \(u_1, u_2, \ldots \in (0,1)\) designed to be statistically indistinguishable from independent samples of the uniform distribution on \([0,1]\). Most generators have the form \[ s_{i+1} = g(s_i), \qquad u_i = h(s_i), \] where \(s_i\) is the internal state of the generator, \(g\) updates the state, and \(h\) converts the state into a number in \((0,1)\). The initial state \(s_0\) is called the seed. Since the state can take only finitely many values, the sequence must eventually repeat, and the length of the cycle is called the period.

Determinism is a feature rather than a bug: running the same code with the same seed reproduces exactly the same “random” numbers, which makes simulations repeatable and much easier to debug. This is why the noisy-data demonstration in Chapter 4 begins with rng(1).

What should we ask of the sequence? Each \(u_i\) should look uniformly distributed, but this is the easy part: the sequence \(0.01, 0.02, \ldots, 0.99\) has a perfect histogram and is not random at all. The essential property is independence: knowing \(u_1, \ldots, u_{i-1}\) should tell us nothing about \(u_i\). In particular, pairs \((u_i, u_{i+1})\) should fill the unit square uniformly, triples \((u_i, u_{i+1}, u_{i+2})\) should fill the unit cube uniformly, and so on.

Definition 6.1
A linear congruential generator (LCG) is an iteration of the form \[ x_{i+1} = (a x_i + c) \bmod m, \qquad u_{i+1} = \frac{x_{i+1}}{m}, \] where the multiplier \(a\), the increment \(c\) and the modulus \(m\) are integers, and \(y \bmod m\) denotes the remainder when \(y\) is divided by \(m\).

Example 6.1
With \(a=6\), \(c=0\), \(m=11\) and seed \(x_0=1\) we obtain \[ 1, 6, 3, 7, 9, 10, 5, 8, 4, 2, 1, 6, \ldots, \] which visits every nonzero remainder before repeating (period \(10\)). With \(a=3\) instead we obtain \(1, 3, 9, 5, 4, 1, \ldots\), which has period only \(5\).

The period of an LCG is at most \(m\), and number theory tells us how to choose \(a\), \(c\) and \(m\) to achieve this maximum (see Knuth, The Art of Computer Programming, Volume 2). But a long period is not enough, as the following cautionary tale shows.

Example 6.2: RANDU

The LCG with \(a = 65539 = 2^{16}+3\), \(c=0\) and \(m=2^{31}\), known as RANDU, was supplied with IBM mainframes in the 1960s and was very widely used for scientific simulation. Its output passes a casual inspection: the histogram of the \(u_i\) looks uniform, and so does a 3D scatter plot of consecutive triples \((u_i, u_{i+1}, u_{i+2})\). But if we rotate the cube, all of the triples turn out to lie on just \(15\) parallel planes!

RANDU output: histogram of \(3\times 10^4\) values (left), consecutive triples (middle), and the same triples viewed from a different angle (right).

To see why, note that \(a^2 = 2^{32} + 6\cdot 2^{16} + 9 = 2^{32} + 6a - 9\). Since \(2^{32}\) is a multiple of \(2^{31}\), \[ x_{i+2} = a^2 x_i \bmod 2^{31} = (6 a x_i - 9 x_i) \bmod 2^{31} = (6x_{i+1} - 9x_i) \bmod 2^{31}. \] Hence \(9x_i - 6x_{i+1} + x_{i+2}\) is an integer multiple of \(2^{31}\), and dividing by \(2^{31}\) gives \[ 9u_i - 6u_{i+1} + u_{i+2} = k \in \mathbb{Z}. \] Since each \(u_i\in(0,1)\), the left-hand side lies in \((-6, 10)\), so \(k \in \{-5, -4, \ldots, 9\}\). Every triple lies on one of these \(15\) planes, and any simulation that uses three consecutive numbers (for example, to place a random point in 3D) only ever explores those planes.

n = 3e4;
x = zeros(n, 1);  x(1) = 1;              % seed
for i = 1:n-1
    x(i+1) = mod(65539*x(i), 2^31);      % exact: 65539*x(i) < 2^53 (Chapter 1)
end
u = x/2^31;
plot3(u(1:end-2), u(2:end-1), u(3:end), '.', 'MarkerSize', 2)
view([2 3 0])                            % look along the planes

RANDU is a particularly bad choice of parameters, but the defect is shared by every LCG: Marsaglia showed in 1968 that consecutive \(d\)-tuples from an LCG always lie on at most \((d!\,m)^{1/d}\) parallel hyperplanes.

6.2.2 Testing generators: the chi-squared test

How can we tell whether a generator is any good? We use statistical hypothesis tests of the null hypothesis

\(H_0\): the numbers \(u_1, \ldots, u_n\) are independent samples from the uniform distribution on \([0,1]\).

A test can never show that \(H_0\) is true (we know that the numbers are not random!), but a generator that fails a test has a detectable non-random pattern. The simplest such test is the chi-squared goodness-of-fit test.

Definition 6.2
Let \(Z_1, \ldots, Z_\nu\) be independent standard normal random variables. The distribution of \(Z_1^2 + \cdots + Z_\nu^2\) is called the chi-squared distribution with \(\nu\) degrees of freedom, written \(\chi^2_\nu\).

To test for uniformity, partition \([0,1]\) into \(k\) equal bins \([0,\tfrac1k), [\tfrac1k,\tfrac2k), \ldots, [\tfrac{k-1}{k},1]\) and let \(n_j\) be the number of samples in bin \(j\). Under \(H_0\), each bin has expected count \(n/k\), and the chi-squared test statistic measures how far the observed counts are from this: \[ T = \sum_{j=1}^k \frac{(n_j - n/k)^2}{n/k} = \frac{k}{n}\sum_{j=1}^k \left(n_j - \frac{n}{k}\right)^2. \]

Theorem 6.1
Under \(H_0\), \(T\) converges in distribution to \(\chi^2_{k-1}\) as \(n\to\infty\).

We will not prove this, but here is the intuition. For large \(n\), each count \(n_j\) is approximately normal with mean \(n/k\) and variance approximately \(n/k\), so each term in \(T\) is approximately the square of a standard normal. The terms are not independent, since \(n_1 + \cdots + n_k = n\), and this single constraint removes one degree of freedom.

The test is carried out at a chosen significance level \(\alpha\), typically \(\alpha = 0.05\). Let \(c\) be the \((1-\alpha)\)-quantile of \(\chi^2_{k-1}\), computed in MATLAB as chi2inv(1 - alpha, k - 1). If \(T > c\) we reject \(H_0\) (the sample fails the test), and otherwise the sample passes. If \(H_0\) is true, the sample wrongly fails with probability approximately \(\alpha\). The limiting distribution is a good approximation when every expected count \(n/k\) is at least about \(5\).

Example 6.3: Chi-squared test with ten bins
A generator produces \(n = 1000\) numbers, which we sort into \(k = 10\) bins, each with expected count \(100\). Suppose the observed counts are:

Bin \(j\) 1 2 3 4 5 6 7 8 9 10
\(n_j\) 98 104 112 107 94 95 108 97 96 89

Then \[ T = \frac{10}{1000}\left[(-2)^2 + 4^2 + 12^2 + 7^2 + (-6)^2 + (-5)^2 + 8^2 + (-3)^2 + (-4)^2 + (-11)^2\right] = \frac{484}{100} = 4.84. \] The critical value at significance level \(\alpha = 0.05\) is chi2inv(0.95, 9) \(\approx 16.92\). Since \(4.84 < 16.92\), the sample passes the test.

Example 6.4: Catching RANDU
Take \(n = 3\times 10^5\) numbers \(u_1, \ldots, u_n\) from RANDU with seed \(x_0 = 1\). With \(k = 10\) bins, the chi-squared test gives \(T \approx 4.3\), well below the critical value \(16.92\), so RANDU passes. The individual numbers really do look uniform.

The same idea applies to triples. Group the numbers into \(10^5\) non-overlapping triples \((u_1,u_2,u_3), (u_4,u_5,u_6), \ldots\), divide the unit cube into \(k^3 = 1000\) small cubes of side \(0.1\), and count the triples in each. Under \(H_0\), each small cube has expected count \(100\), and \(T\) is approximately \(\chi^2_{999}\), with critical value chi2inv(0.95, 999) \(\approx 1074\). For RANDU the counts range from \(68\) to \(145\) and \(T \approx 1593\), so RANDU fails decisively. The Mersenne Twister gives \(T \approx 1043\) on the same test and passes.

The lesson is that tests must probe independence, not just the histogram of single values.

Modern generators

MATLAB’s default generator is the Mersenne Twister (Matsumoto and Nishimura, 1998), which has period \(2^{19937}-1\) and is equidistributed in up to \(623\) dimensions. Newer families include PCG (the default in Python’s NumPy) and xoshiro (the default in Julia). Large simulations now run on thousands of GPU cores at once, which favours counter-based generators such as Philox (rng(seed, 'philox') in MATLAB). In these generators \(u_i = h(\text{key}, i)\) is a scrambled version of the counter \(i\), so each core can jump directly to its own part of the sequence.

Generators are vetted by large batteries of statistical tests, such as the TestU01 suite, which apply hypothesis tests like the one above (and many others, such as the Kolmogorov–Smirnov test) to hundreds of different features of the output. The practical lessons are: never write your own generator, always record your seed, and make sure that parallel computations use independent streams of random numbers.

6.2.3 Sampling from other distributions

Recall that a real-valued random variable \(X\) has cumulative distribution function (CDF) \(F(x) = \mathbb{P}[X\le x]\) and, if \(X\) is continuous, probability density function (PDF) \(f = F'\). Generators produce uniform samples, and samples from other distributions are obtained by transforming these.

Theorem 6.2: Inverse transform method
Let \(U\) be uniformly distributed on \([0,1]\) and let \(F\) be a continuous, strictly increasing CDF. Then \(X = F^{-1}(U)\) has CDF \(F\).

Proof. Since \(F\) is increasing, \(F^{-1}(U)\le x\) if and only if \(U \le F(x)\). Hence \[ \mathbb{P}[X \le x] = \mathbb{P}[U \le F(x)] = F(x), \] because \(\mathbb{P}[U\le y] = y\) for \(y \in[0,1]\).

Example 6.5: Exponential distribution
If \(X\sim\text{Exp}(\lambda)\), then \(F(x) = 1 - e^{-\lambda x}\) for \(x\ge0\). Solving \(F(x) = u\) gives \(F^{-1}(u) = -\log(1-u)/\lambda\). Since \(1-U\) is also uniform on \([0,1]\), the command X = -log(rand(n, 1))/lambda generates \(n\) independent samples of \(X\).

Exercise 6.1
The Pareto distribution with parameters \(x_m, \alpha > 0\) has PDF \(f(x) = \alpha x_m^\alpha/x^{\alpha+1}\) for \(x\ge x_m\). Find its CDF and show that \(x_m (1-U)^{-1/\alpha}\) is Pareto distributed. Generate \(10^5\) samples in MATLAB and compare a normalised histogram (histogram(X, 'Normalization', 'pdf')) with \(f\).

When \(F^{-1}\) has no closed form, other transformations are used. For example, the Box–Muller transform turns two independent uniform samples \(U_1, U_2\) into two independent standard normal samples \(\sqrt{-2\log U_1}\cos(2\pi U_2)\) and \(\sqrt{-2\log U_1}\sin(2\pi U_2)\). In practice, built-in functions such as randn should be used.

6.2.4 The Monte Carlo estimator

Example 6.6: Estimating \(\pi\)
Suppose \((X_i, Y_i)\) are independent and uniformly distributed on the square \([-1,1]^2\). The probability that a point lands in the unit disc is the ratio of the areas, \(\pi/4\). So \(4\times\) (fraction of points in the disc) estimates \(\pi\). In the left panel below, \(8\) of \(10\) points fall in the disc, giving the estimate \(3.2\). With \(1000\) points (right panel) the estimate improves to about \(3.15\). In other words, we are estimating the integral \[ \pi = \int_{-1}^1 \int_{-1}^1 \mathbb{1}\{x^2+y^2\le 1\}\,dy\,dx \] by averaging the integrand at random points.

More generally, suppose that we want to compute \[ \mu = \mathbb{E}[A(X)] = \int_{\mathbb{R}^d} A(x) f(x)\,dx, \] where \(X\) is a random variable in \(\mathbb{R}^d\) with PDF \(f\). In particular, any integral over the unit cube is an expectation: if \(U\) is uniformly distributed on \([0,1]^d\) (so \(f\equiv 1\) there), then \[ \int_{[0,1]^d} g(x)\,dx = \mathbb{E}[g(U)]. \] Similarly, if \(U\) is uniformly distributed on an interval \([a,b]\), it has density \(1/(b-a)\) there, so \[ \frac{1}{b-a}\int_a^b g(x)\,dx = \mathbb{E}[g(U)], \] and samples of \(U\) are given by \(a + (b-a)\,\)rand.

Definition 6.3
Let \(X_1, \ldots, X_n\) be independent random variables with the same distribution as \(X\). The Monte Carlo estimator of \(\mu = \mathbb{E}[A(X)]\) is the sample average \[ \hat{\mu}_n = \frac{1}{n}\sum_{i=1}^n A(X_i). \]

Theorem 6.3: Properties of the Monte Carlo estimator

Suppose \(\mathbb{E}|A(X)| < \infty\). Then:

  1. \(\hat\mu_n\) is unbiased: \(\mathbb{E}[\hat{\mu}_n] = \mu\).
  2. \(\hat\mu_n\) is consistent: \(\hat{\mu}_n \to \mu\) almost surely as \(n\to\infty\) (the strong law of large numbers).
  3. If also \(\sigma^2 = \text{Var}[A(X)] < \infty\), then \(\text{Var}[\hat\mu_n] = \sigma^2/n\), and by the central limit theorem \[ \frac{\sqrt{n}}{\sigma}(\hat{\mu}_n-\mu) \to \mathcal{N}(0,1) \quad \text{in distribution as } n \to\infty. \]

Part 1 follows from linearity of expectation, and the variance formula in part 3 holds because the variance of a sum of independent random variables is the sum of their variances. Part 3 is what gives us an error bar. For \(0 < \alpha < 1\), let \(z_{1-\alpha/2}\) be the \((1-\alpha/2)\)-quantile of the standard normal distribution, so that \(\mathbb{P}[|Z| \le z_{1-\alpha/2}] = 1-\alpha\) for \(Z\sim\mathcal{N}(0,1)\). Then \[ \mathbb{P}\left[ |\hat\mu_n - \mu| \le z_{1-\alpha/2}\frac{\sigma}{\sqrt{n}} \right] \approx 1-\alpha \quad\text{for large } n. \] The most common choices are \(z_{0.975} \approx 1.96\) (for \(\alpha = 0.05\)) and \(z_{0.995} \approx 2.576\) (for \(\alpha = 0.01\)). In MATLAB, \(z_{1-\alpha/2}\) is norminv(1 - alpha/2).

We don’t usually know \(\sigma\) (if we can’t compute \(\mu\), we probably can’t compute \(\sigma\) either), so in practice we replace it by the sample standard deviation \(\hat\sigma_n\) of the same samples, where \[ \hat\sigma_n^2 = \frac{1}{n-1}\sum_{i=1}^n \big(A(X_i) - \hat\mu_n\big)^2. \] The quantity \(\hat\sigma_n/\sqrt{n}\), which estimates the standard deviation of \(\hat\mu_n\), is called the standard error, and \[ \hat\mu_n \pm z_{1-\alpha/2}\,\frac{\hat\sigma_n}{\sqrt{n}} \] is an approximate \(100(1-\alpha)\%\) confidence interval for \(\mu\). For example, \(\hat\mu_n \pm 1.96\,\hat\sigma_n/\sqrt{n}\) is an approximate \(95\%\) confidence interval. Unlike the quadrature rules of Chapter 4, Monte Carlo provides an estimate of its own error at no extra cost.

Almost sure convergence means that, with probability one, the sequence of estimates \(\hat\mu_1, \hat\mu_2, \ldots\) produced by a single run converges to \(\mu\). It is one of several modes of convergence for random variables that you will meet in probability courses.

The error therefore decreases like \(n^{-1/2}\). This is slow: to gain one more correct digit we need \(100\) times as many samples.

Example 6.7: A one-dimensional integral
Let \(U\) be uniform on \([0,1]\) and \(\mu = \mathbb{E}[U^2] = \int_0^1 x^2\,dx = \tfrac13\). Here \[ \sigma^2 = \mathbb{E}[U^4] - \mu^2 = \frac15 - \frac19 = \frac{4}{45}, \] so the \(95\%\) confidence interval has half-width \(1.96\sqrt{4/45}/\sqrt{n} \approx 0.58/\sqrt{n}\).

n = 1e4;
gU = rand(n, 1).^2;                      % samples of A(U) = U^2
muHat = mean(gU);
SE = std(gU)/sqrt(n);                    % standard error
fprintf('%.4f +/- %.4f\n', muHat, 1.96*SE)

With \(n = 10^4\) samples the error is around \(6\times 10^{-3}\). By comparison, the composite trapezium rule with \(10^4\) points has error \(h^2/6 \approx 2\times10^{-9}\) for this integral. In one dimension, Monte Carlo is a terrible method!

6.2.5 Why Monte Carlo? The curse of dimensionality

So why bother with Monte Carlo at all? Consider an integral over the \(d\)-dimensional unit cube, \[ I = \int_{[0,1]^d} g(x)\,dx. \] The quadrature rules of Chapter 4 extend to \(d\) dimensions by applying them in each coordinate direction in turn (a tensor-product rule). With \(m\) points in each direction, the composite trapezium rule uses a grid of \(n = m^d\) points and, for smooth \(g\), has error \(O(h^2) = O(m^{-2})\). In terms of the total number of function evaluations, this is \[ \text{trapezium: } O(n^{-2/d}), \qquad \text{Simpson: } O(n^{-4/d}), \qquad \text{Monte Carlo: } O(n^{-1/2}). \] The Monte Carlo rate does not depend on the dimension (although the constant \(\sigma\) does depend on \(g\)). It overtakes the trapezium rule when \(d > 4\) and Simpson’s rule when \(d > 8\). Worse still for grids, even the crudest grid with \(2\) points per direction needs \(2^d\) evaluations. For \(d=100\), this is about \(10^{30}\) evaluations, which would take more than \(10^{13}\) years at a billion evaluations per second. This exponential growth of cost with dimension is called the curse of dimensionality.

Example 6.8: Monte Carlo versus the trapezium rule in higher dimensions
The integrand \(g(x) = e^{-|x|^2}\) on \([0,1]^d\) has exact integral \(I_d = \big(\int_0^1 e^{-s^2}\,ds\big)^d = \big(\tfrac{\sqrt\pi}{2}\,\text{erf}(1)\big)^d\). The Monte Carlo estimate takes a few lines in any dimension:

d = 10;  n = 1e6;
gX = exp(-sum(rand(n, d).^2, 2));        % g at n uniform points in [0,1]^d
muHat = mean(gX);  SE = std(gX)/sqrt(n);
Iexact = (sqrt(pi)/2*erf(1))^d;
fprintf('%.6f +/- %.6f (exact %.6f)\n', muHat, 1.96*SE, Iexact)

Error against the number of evaluations of \(g\) for the tensor-product trapezium rule and for a single Monte Carlo run, in dimensions \(d=1,4,10\). The dashed line is the \(95\%\) error bar \(1.96\sigma/\sqrt{n}\).

In one dimension the trapezium rule wins by many orders of magnitude. In four dimensions the two methods are comparable. In ten dimensions, the trapezium rule with only \(3\) points per direction already needs \(3^{10} = 59049\) evaluations and is accurate to just \(10^{-2}\), while a million Monte Carlo samples (fewer than a grid with \(4\) points per direction) give an error of order \(10^{-4}\), as predicted by the dashed line, together with an error bar.

Summary: Monte Carlo is a poor method in one dimension and often the only practical method in a hundred.

Where high-dimensional integrals arise
  • Statistical physics: averages over all configurations of a system of \(N\) particles or spins, such as the Ising model, are integrals or sums in dimension proportional to \(N\). These are computed with Markov chain Monte Carlo methods such as the Metropolis algorithm.
  • Finance: the price of an option on a basket of many assets is an expectation over all of their future paths.
  • Bayesian statistics and machine learning: posterior means are integrals over all unknown parameters.
  • Computer graphics: in modern animated films, the colour of each pixel is an integral over all paths that light can take through the scene, computed by Monte Carlo path tracing. The grainy “noise” in a render with too few samples is exactly the \(n^{-1/2}\) Monte Carlo error.

6.2.6 Variance reduction: importance sampling

The rate \(n^{-1/2}\) is fixed, but the constant \(\sigma\) is not. The same quantity \(\mu\) can be written as the expectation of many different random variables, some with much smaller variance than others. Methods that exploit this are called variance reduction techniques, and one of the most important is importance sampling.

Its main use is for rare events. Suppose we want \(p = \mathbb{P}[Z > 4] \approx 3.17\times 10^{-5}\) for \(Z\sim\mathcal{N}(0,1)\). The plain Monte Carlo estimator averages \(A(Z) = \mathbb{1}\{Z > 4\}\), which has \(\sigma^2 = p(1-p)\), so the error relative to \(p\) is about \[ \frac{\sigma}{p\sqrt{n}} \approx \frac{1}{\sqrt{pn}}. \] With \(n = 10^4\) samples we expect fewer than one sample to exceed \(4\), and we need \(n \approx 100/p \approx 3\times 10^6\) for \(10\%\) relative accuracy. Almost every sample lands where \(A = 0\) and is wasted.

The idea of importance sampling is to draw samples from a different density \(g\) that puts more of them where they matter, and then correct for this with a weight. If \(g(x) > 0\) wherever \(A(x)f(x) \neq 0\), then \[ \mu = \int A(x) f(x)\,dx = \int A(x)\frac{f(x)}{g(x)}\, g(x)\,dx = \mathbb{E}\big[A(Y)\,w(Y)\big], \qquad Y\sim g, \] where \(w = f/g\) is called the likelihood ratio or weight.

Theorem 6.4: Importance sampling
Let \(Y_1, \ldots, Y_n\) be independent with density \(g\), and let \[ \hat\mu_n^{\rm IS} = \frac{1}{n}\sum_{i=1}^n A(Y_i)\,w(Y_i), \qquad w = \frac{f}{g}. \] Then \(\hat\mu_n^{\rm IS}\) is an unbiased estimator of \(\mu\), with variance \(\sigma_g^2/n\), where \[ \sigma_g^2 = \int \frac{A(x)^2 f(x)^2}{g(x)}\,dx - \mu^2. \] If \(A \ge 0\) and \(\mu > 0\), the choice \(g^* = Af/\mu\) gives \(\sigma_{g^*}^2 = 0\).

Proof. Unbiasedness follows from the identity above. For the variance, \[ \text{Var}[A(Y)w(Y)] = \mathbb{E}\big[A(Y)^2w(Y)^2\big] - \mu^2 = \int A^2\frac{f^2}{g^2}\,g\,dx - \mu^2 = \int \frac{A^2f^2}{g}\,dx - \mu^2, \] and the variance of the average of \(n\) independent copies is this divided by \(n\). With \(g = g^*\), we have \(A^2f^2/g^* = \mu A f\) wherever \(A > 0\) (and both sides vanish where \(A = 0\)), so \(\sigma_{g^*}^2 = \mu\int Af\,dx - \mu^2 = 0\).

The optimal density \(g^*\) cannot be used in practice, since it requires knowing \(\mu\). But it tells us what to aim for: \(g\) should be roughly proportional to \(|A|f\), so that samples are concentrated where the integrand is large. A poor choice of \(g\), for example one with much lighter tails than \(Af\), can instead make the variance much larger, or even infinite.

Example 6.9: Importance sampling for a rare event
To estimate \(p = \mathbb{P}[Z > 4]\), we shift the samples into the rare region by taking \(g\) to be the \(\mathcal{N}(4,1)\) density. The weight is \[ w(y) = \frac{f(y)}{g(y)} = \frac{e^{-y^2/2}}{e^{-(y-4)^2/2}} = e^{8 - 4y}. \]

rng(2)
n = 1e4;
Z = randn(n, 1);  A = (Z > 4);              % plain Monte Carlo
Y = 4 + randn(n, 1);                        % samples from g = N(4,1)
AW = (Y > 4).*exp(8 - 4*Y);                 % A(Y) w(Y)
fprintf('plain: %.2e +/- %.1e\n', mean(A), 1.96*std(A)/sqrt(n))
fprintf('IS:    %.3e +/- %.1e\n', mean(AW), 1.96*std(AW)/sqrt(n))

Plain Monte Carlo gives \((1.0 \pm 2.0)\times 10^{-4}\), based on the single sample that exceeded \(4\), which is useless. Importance sampling gives \((3.23 \pm 0.13)\times 10^{-5}\), consistent with the exact value \(3.167\times 10^{-5}\). For this choice of \(g\), the variance is about \(7000\) times smaller than for plain Monte Carlo, so we would need about \(7000\) times as many plain samples for the same accuracy.

Exercise 6.2
Estimate \(\mathbb{P}[Z > 6]\) for \(Z\sim\mathcal{N}(0,1)\) by importance sampling with \(g\) the \(\mathcal{N}(6,1)\) density, and compare with the exact value 0.5*erfc(6/sqrt(2)). Roughly how many plain Monte Carlo samples would be needed for the same accuracy?

Other ways to beat plain Monte Carlo

Other variance reduction techniques include control variates, which subtract a correlated quantity with known mean, and antithetic variables, which pair each sample \(U\) with \(1-U\). Quasi-Monte Carlo methods go further, replacing random points by carefully constructed low-discrepancy sequences (e.g. sobolset in MATLAB), and achieve errors close to \(O(n^{-1})\) for smooth integrands.

6.2.7 Application: random walkers solve the heat equation

We can now connect this section to the heat equation from earlier in the chapter. Recall the method-of-lines system with Neumann boundary conditions, and apply forward Euler with the largest stable timestep, \(\Delta t = (\Delta x)^2/(2\alpha)\). Writing \(u_j^k \approx u(x_j, t_k)\), the scheme becomes \[ u_j^{k+1} = u_j^k + \frac{\alpha\Delta t}{(\Delta x)^2}\left(u_{j-1}^k - 2u_j^k + u_{j+1}^k\right) = \frac12 u_{j-1}^k + \frac12 u_{j+1}^k, \qquad j = 1, \ldots, N, \] with ghost nodes \(u_0^k = u_1^k\) and \(u_{N+1}^k = u_N^k\). Each new value is simply the average of the two neighbouring values.

This has a probabilistic interpretation. Consider a random walker on the nodes \(1, \ldots, N\) that, at each timestep, moves one node left or right with probability \(\tfrac12\) each. If a step would take the walker onto a ghost node, it stays where it is instead (it is reflected). Let \(J_k\) be the walker’s node after \(k\) steps, and define \[ v_j^k = \mathbb{E}\big[\, u(x_{J_k}, 0) \;\big|\; J_0 = j \,\big], \] the expected initial temperature at the walker’s position after \(k\) steps, starting from node \(j\).

Theorem 6.5
For all \(j\) and \(k\), \(v_j^k = u_j^k\): the forward Euler solution is the expected value of the initial data at the end of a random walk.

Proof. For \(k=0\) the walker has not moved, so \(v_j^0 = u(x_j,0) = u_j^0\). For \(k \ge 0\), condition on the walker’s first step. With probability \(\tfrac12\) it moves to node \(j-1\), after which it performs a \(k\)-step walk from there; similarly for \(j+1\). Hence \[ v_j^{k+1} = \tfrac12 v_{j-1}^k + \tfrac12 v_{j+1}^k, \] where a step onto a ghost node is replaced by staying at the boundary node, i.e. \(v_0^k = v_1^k\) and \(v_{N+1}^k = v_N^k\). This is exactly the recursion satisfied by \(u_j^k\), with the same initial values, so \(v_j^k = u_j^k\) by induction on \(k\).

So we can estimate the solution at a single point by Monte Carlo: release \(M\) independent walkers from node \(j\), run each for \(K = t/\Delta t\) steps, and average the initial data at their final positions. As \(\Delta x \to 0\), the random walk converges to Brownian motion, and we obtain \(u(x,t) = \mathbb{E}[u(X_t, 0)]\), where \(X_t\) is a (reflected) Brownian motion started at \(x\). This is a special case of the Feynman–Kac formula, which links a large class of PDEs to expectations over random paths.

Example 6.10: MATLAB demonstration: random walkers for the heat equation
We take \(L = \alpha = 1\), \(u(x,0) = \cos(\pi x)\) and \(t = 0.1\); the exact solution is \(u(x,t) = e^{-\pi^2 t}\cos(\pi x)\). The following function estimates \(u(x_{j_0}, t)\) using \(M\) walkers on a grid of \(N\) nodes:

function [uHat, SE] = walkers(j0, M, N, K, u0)
x = linspace(0, 1, N);
j = j0*ones(M, 1);                         % every walker starts at node j0
for k = 1:K
    j = j + 2*(rand(M, 1) < 0.5) - 1;      % step left or right
    j = min(max(j, 1), N);                 % a step off the grid stays put
end
vals = u0(x(j));                           % initial data at final positions
uHat = mean(vals);
SE = std(vals)/sqrt(M);
end

With \(N = 51\) we have \(\Delta x = 0.02\), \(\Delta t = 2\times 10^{-4}\) and \(K = 500\) steps. Running walkers(j0, 1e4, 51, 500, @(x) cos(pi*x)) for every fifth node gives the estimates below. They agree with the method-of-lines solution to within their error bars (as the theorem predicts), and that solution in turn approximates the exact solution.

Why would we ever do this, when the method of lines gives the whole solution at once? A grid method must compute the solution everywhere, on a grid of \(m^d\) points in \(d\) dimensions. A walker estimates the solution at just the points we care about, and its cost per step barely depends on dimension: in \(d\) dimensions it simply chooses among \(2d\) neighbours. This is the curse of dimensionality again, and it is why random-walk methods are used for high-dimensional PDEs such as those arising in finance and quantum mechanics. They also handle complicated geometries easily, since the walker only needs to know whether it has hit a boundary. Other boundary conditions and equations correspond to other walker rules: for example, Dirichlet boundary conditions correspond to walkers that are absorbed when they reach the boundary, and the expected time for a walker to hit a target region (such as a foraging animal searching for food) satisfies a Poisson equation.

Exercise 6.3
Extend walkers to the heat equation on the unit square \([0,1]^2\) with Neumann boundary conditions, where each walker moves to one of its four neighbours with equal probability. Take \(u(x,y,0) = \cos(\pi x)\cos(\pi y)\), for which \(u = e^{-2\pi^2\alpha t}\cos(\pi x)\cos(\pi y)\). What timestep does forward Euler need to make the scheme an average over neighbours? How does the standard error change as you increase \(M\)?

Knowledge checklist

Key topics:

  1. The method of lines for the heat equation: finite-difference discretisation in space, ghost nodes for Neumann boundary conditions, and the stability of forward and backward Euler.

  2. Pseudorandom number generators: seeds, periods, linear congruential generators and their lattice structure.

  3. The chi-squared test for uniformity, and why tests must probe independence as well as the distribution of single values.

  4. Sampling from other distributions by the inverse transform method.

  5. The Monte Carlo estimator: unbiasedness, the law of large numbers, the \(n^{-1/2}\) error from the central limit theorem, standard errors and confidence intervals.

  6. The curse of dimensionality: grid-based quadrature errors of \(O(n^{-2/d})\) compared with the dimension-independent \(O(n^{-1/2})\) for Monte Carlo.

  7. Variance reduction by importance sampling, and the optimal sampling density.

  8. The random-walk representation of the forward Euler scheme for the heat equation.

Key skills:

  • Implementing the method of lines with explicit and implicit timestepping, and choosing a stable timestep.

  • Implementing a linear congruential generator and testing its output with the chi-squared test.

  • Generating samples from a given distribution by the inverse transform method.

  • Writing integrals as expectations, and computing Monte Carlo estimates with confidence intervals at a given level.

  • Deciding when Monte Carlo is preferable to quadrature.

  • Choosing an importance sampling density and computing the corresponding weights.

  • Simulating random walks and using them to estimate expectations.