next up previous
Next: Remarks Up: Sampling algorithms Previous: The independent sampler

The random walk

The idea of a random walk is to explore locally the space in the neighborhood of the current state z. The proposal transition kernel is symmetric:
equation157
The acceptance probability a of equation 16 reduces to:
equation161
A frequent choice consists in taking tex2html_wrap_inline556 equal to a centered Gaussian distribution. The behaviour of the algorithm is then dependent on the variance. When this one is too low, the transitions are often accepted, but consecutive states are strongly correlated, resulting in a poor mixing within the chain. On the opposite, if it is too high, transitions are often rejected and the chain remains stuck in high tex2html_wrap_inline432 probability states.

  figure167
Figure 2: Transition in a bidimensional state space generated by a random walk. The target distribution tex2html_wrap_inline432 is represented as black level lines, the proposal transition kernel tex2html_wrap_inline574 in blue. The red transition is accepted (because tex2html_wrap_inline592), while the green one is likely to be rejected.

Figure 2 represents the transition of a Markov chain generated by a random walk.



Bob Fisher
Fri Jul 26 09:56:32 BST 2002