9.1 Introduction to numerical methods

9.1.1 Monte Carlo methods

Bayesian statistics proceeds smoothly and easily as long as we stick to well-known distributions and use conjugate priors. But in real life, it is often difficult to model the situations which arise in practice in that way; instead, we often arrive at a posterior

but have no easy way of finding the constant multiple and have to have recourse to some numerical technique. This is even more true when we come to evaluate the marginal density of a single component of . A simple example was given earlier in Section 3.9 on ‘The circular normal distribution’, but the purpose of this chapter is to discuss more advanced numerical techniques and the Gibbs sampler in particular.

There are, of course, many techniques available for numerical integration, good discussions of which can be found in, for example, Davis and Rabinowitz (1984), Evans (1993) or Evans and Swartz (2000). Most of the methods we shall discuss are related to the idea of ‘Monte Carlo’ integration as a method of finding an expectation. In the simplest version of this, we write

where the points x1, x2, … , xn are chosen as independent ‘pseudo-random’ numbers with density p(x) on the interval (a, b), which in the simplest case is the uniform distribution U(a, b). Although the results of this technique get better in higher dimensions, ‘In all [dimensions], crude Monte Carlo exists as a last resort, especially for integrals defined over nonstandard regions and for integrands of low-order continuity. It is usually quite reliable but very expensive and not very accurate’ (Davis and Rabinowitz, op. cit., Section 5.10). We shall not, however, use crude Monte Carlo as such, but rather certain refinements of it.

An extension of crude Monte Carlo is provided by importance sampling. This method is useful when we want to find a parameter θ which is defined as the expectation of a function f(x) with respect to a density q(x) but we cannot easily generate random variables with that density although we can generate variates xi with a density p(x) which is such that p(x) roughly approximates |f(x)|q(x) over the range of integration. Then

The function p(x) is called an importance function.

9.1.2 Markov chains

Another key notion is that of a Markov chain, which can be thought of as a model for a system which moves randomly through series of ‘states’ without having any memory of where it has been – where it jumps to next depends solely on where it is now. Another way of putting this is to say that given the present, the past and the future are independent. We thus have a probability density, called the transition probability density representing the chance of taking the state y at time t given that its state at time t–1 is x. In the cases, we are most interested in, this density will not depend on t and so takes the form p(y|x). If the probability density of its state at time 0 is p(0)(x), then clearly the density of its state at time 1 is given by the generalized addition law as

A similar result with the sum replaced by an integral holds when the state space, that is, the set of possible states, is continuous. Iterating this process we can clearly find the distribution of the state at any time t in terms of p(0)(x) and p(y|x). The key point for our purposes is that in many cases this density converges to a limit p(y) which does not depend on p(0)(x) but rather is uniquely determined by p(y|x). The limiting distribution is known as the stationary distribution or the invariant distribution. Properties of Markov chains which can take only a finite or countable number of values are discussed in Feller (1968, Volume 1; Chapter XV) and an indication of the general theory is given in Breiman (1968, Section 7.4). A more detailed account can be found in Meyn and Tweedie (1993) and a more applied one in Norris (1997).

It transpires that some densities which we are interested in turn up as stationary distributions for Markov chains.