The M-H algorithms can draw samples from any probability distribution p(x), requiring only that the density can be calculated at x. The algorithm generates a Markov chain in which each state x(t) depends only on the previous state x(t-1). The algorithm uses a proposal density Q(x', x(t)), which depends on the current state x(t), to generate a new proposed sample x(t). This proposal is 'accepted' as the next value (x(t+1)=x') if u drawn from U(0,1) is

The original Metropolis algorithm calls for the proposal density to be symmetric (Q(x;y)=Q(y;x)); generalization by Hastings lifts this restriction. It is allowed for Q(x', x(t)) not to depend on x' at all, in which case the algorithm is called "Independence Chain M-H" (as opposed to "Random Walk M-H"). Independence chain M-H algorithm with suitable proposal density function can offer higher accuracy than random walk version, but it requires some a priori knowledge of the distribution.

Now, we draw a new proposal state x' with probability Q(x'; x(t)) and then calculate a value

a = a1a2

wherea1 = P(x')/P(x(t))

is the likelihood ratio between the proposed sample x' and the previous sample x(t), and

a2 = Q(x(t); x')/Q(x'; x(t))

is the ratio of the proposal density in two directions (from x(t) to x' and vice versa). This is equal to 1 if the proposal density is symmetric. Then the new state x(t+1) is chosen with the rule

The Markov chain is started from a random initial value x(0) and the algorithm is run for many iterations until this initial state is "forgotten". These samples, which are discarded, are known as burn-in. The algorithm works best if the proposal density matches the shape of the target distribution p(x), that is Q(x'; x(t)) ~P(x'), but in most cases this is unknown. If a Gaussian proposal is used, the variance parameter has to be tuned during the burn-in period. This is usually done by calculating the acceptance rate, which is the fraction of proposed samples that is accepted in a window of the last N samples. This is usually be around 60%. If the proposal steps are too small the chain will mix slowly (i.e., it will move around the space slowly and converge slowly to P(x)). If the proposal steps are too large the acceptance rate will be very slow because the proposals are likely to land in regions of much lower probability density so a1 will be very small.
## No comments:

Post a Comment