Rejection sampling algorithm

If the node is a single parameter and its conditional distribution is log-concave, we can draw an observation from the conditional distribution using the adaptive rejection sampling algorithm described in Chapter 2. Generally it takes only a few steps before we get an accepted draw from the conditional distribution, since we are tightening the candidate density with every unaccepted draw. 

Figure 1 Flowchart of the classic Metropolis Monte Carlo algorithm for sampling in the canonical ensemble. Note that samples of the property function f(x) are always accumulated for averaging purposes, irrespective of whether a move is accepted or rejected.

The sampling from W(i) can be implemented in several ways. For example, a rejection sampling algorithm is outlined in Figure 1. An alternative is direct sampling a random number is chosen uniformly on [0,1], and molecule K is selected, where... 

Figure 1. Rejection sampling algorithm for sampling from Wfi. WjM.vfij is the largest element of Wfi).

The following simple Metropolis Monte Carlo example demonstrates how correlations between successive pairs of random numbers can give incorrect results. Suppose we sample the movement of a particle along the x axis confined in a potential well that is symmetric about the origin 7(x) = V( — x). The classic Metropolis algorithm is outlined in Figure 1. At each step in our calculations, the particle is moved to a trial position with the first random number (sprng()) and then that step is accepted or rejected with the second random number. 

The path distribution b[x(. )] can be sampled with algorithms nearly identical to those described in Section III. We simply replace the characteristic function hp xt) with the functional ffg[x(, ] in all expressions. In sampling this distribution, one may determine R t, t ) for all times t,t < at once. Also, in this case efficiency can be increased by growing the backward segments of a shooting move first, because only in this case early rejection can be exploited to reduce the computational cost of shooting moves. 

---