Convergence of adaptive direction sampling (Q1328357)

We investigate a method of dynamically choosing directions in which to sample, known as adaptive direction sampling (ADS), concentrating here on the convergence properties of the algorithm with an emphasis on a number of important special cases. Recent advances in sampling from one- dimensional distributions have made algorithms with wider choices of sampling directions computationally feasible. Therefore methods such as ADS are naturally suggested. An important special case of ADS, the snooker algorithm, tries to sample in directions which contain more variability more often. At each iteration of the method two points are chosen from a collection of stored points (the current set), and one of these points is replaced by a point along the straight line through the two points, according to a suitable one-dimensional conditional distribution. Another special case of ADS, which is motivated by similar considerations, is parallel ADS. At each iteration, the new point is produced by replacing one point with a point along a straight line through this point and parallel to the line through two other points from the current set. There are many other interesting special cases of ADS including various random direction schemes, and the Gibbs sampler itself. The snooker algorithm is especially of interest from a theoretical point of view due to its irreducibility properties which distinguish it from (for example) the Gibbs sampler and parallel ADS. Applicability of ADS is limited to continuous distributions where the idea of random directions makes sense. Moreover, technical problems can occur in discrete state spaces, caused by the possibility of coincident points.