Target Motion with the Metropolis-Hastings Algorithm
This Demonstration shows how the Metropolis–Hastings algorithm can be used to create a random walk of target positions that corresponds to a target track as it moves through a region of interest. The overall likelihood that the target is at a location is assumed to be proportional to a likelihood function . Regions where is large correspond to regions of high target probability density and regions where is small correspond to regions of low target probability density. Specifically, the Metropolis–Hastings algorithm provides a computationally efficient method of generating a Markov chain Monte Carlo random walk that can then be interpreted as the track of a wandering target.
In this Demonstration, following , the likelihood function shown in the equation below is used to describe target position. In this equation, denotes target location and for denotes a collection of points of repulsion that correspond to unlikely target locations. In a nautical application, these points could correspond to land, shallow water, or regions where prior searching has verified that no target was present.
Because of the way in which the Metropolis–Hastings algorithm works, the function does not need to be normalized in any way. It only needs to be proportional to a quantity that could become a true probability distribution with appropriate normalization.
Points of repulsion in the Demonstration are shown in yellow. The lighter background areas in the Demonstration correspond to regions of high target probability density and the darker areas to regions of low target probability density. The target initial location is controlled by the parameters and . The distance of random stepping is controlled by the parameter distance of random stepping. If this parameter is too small then the target will not move over the entire background region. As the parameter number of Monte Carlo steps is increased, more and more of the region is covered by the target motion. Demonstration run time is proportional to number of Monte Carlo steps. The parameter random seed initializes the computation of pseudorandom numbers in the model. Simulated target locations are shown by the black points in the Demonstration and are plotted on top of a color-dependent representation of the likelihood . The initial target location is shown by the large light blue point in the Demonstration. The first 100 target locations are shown via the light blue line. These first 100 points are treated as burn in and should not be used to estimate target location statistics.
An excellent discussion of the Metropolis–Hastings algorithm can be found in . A discussion of Monte Carlo methods in , and specifically the figure 6.3.1, provided the initial seed idea for this Demonstration.
 P. Gregory, Bayesian Logical Data Analysis for the Physical Sciences, Cambridge: Cambridge University Press, 2005.
 C. P. Robert, The Bayesian Choice, 2nd ed., New York: Springer, 2007.