The hit-and-run sampler: a globally reaching Markov chain sampler for generating arbitrary multivariate distributions

ABSTRACT

The problem of efficiently generating general multivariate densities via a Monte Carlo procedure has experienced dramatic progress in recent years through the device of a Markov chain sampler. This procedure produces a sequence of random deviates corresponding to a random walk over the support of the target distribution. Under certain regularity conditions, the corresponding Markov chain converges in distribution to the target distribution. Thus the sample of points so generated can serve as a statistical sample of points drawn from the target distribution. A random walk that can globally reach across the support of the distribution in one step is called a Hit-and-Run sampler. Hit-and-Run Markov chain samplers offer the promise of faster convergence to the target distribution than conventional small step random walks. Applications to optimization are considered.

REFERENCES

• 1: Claude J. P. Bélisle , H. Edwin Romeijn , Robert L. Smith, Hit-and-run algorithms for generating multivariate distributions, Mathematics of Operations Research, v.18 n.2, p.255-266, May 1993 [doi>10.1287/moor.18.2.255]
• 2: H. C. P. Berbee , C. G. E. Boender , A. H. G. Rinnooy Kan , C. L. Scheffer , R. L. Smith, Hit-and run algorithms for the identification of nonredundant linear inequalities, Mathematical Programming: Series A and B, v.37 n.2, p.184-207, March 2, 1987 [doi>10.1007/BF02591694]
• 3: C. G. E. Boender , R. J. Caron , J. F. McDonald , A. H. G. Rinnooy Kan , H. E. Romeijn , R. L. Smith , J. Telgen , A. C. F. Vorst, Shake-and-bake algorithms for generating uniform points on the boundary of bounded polyhedra, Operations Research, v.39 n.6, p.945-954, Nov.-Dec. 1991 [doi>10.1287/opre.39.6.945]
• 4: Boneh, A., and A. Golan, "Constraints' Redundancy and Feasible Region Boundedness by Random Feasible Point Generator (RFPG)," Third European Congress on Operations Research (EURO III), Amsterdam, 1979.
• 5: R. J. Caron , J. F. McDonald, A new approach to the analysis of random methods for detecting necessary linear inequality constraints, Mathematical Programming: Series A and B, v.43 n.1, p.97-102, Jan. 1989 [doi>10.1007/BF01582281]
• 6: R. J. Caron , M. Hlynka , J. F. McDonald, On the best case performance of hit and run methods for detecting necessary constraints, Mathematical Programming: Series A and B, v.54 n.2, p.233-249, March 2, 1992 [doi>10.1007/BF01586052]
• 7: Chen, M. and B. Schmeiser, "Performance of the Gibbs, Hit-and-Run and Metropolis Samplers," Journal of Computational and Graphical Statistics 2, pp. 251-272, 1993.
• 8: Dyer, M and Frieze, A., "Computing the Volume of Convex Bodies: A Case Where Randomness Provably Helps." Probabilistic combinatorics and its applications, San Francisco, pp. 123-169, 1991.
• 9: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 10: Hammersley, J.M. and Handscomb, D.C., Monte Carlo Methods, John Wiley and Sons, NY, 1964.
• 11: David E. Kaufman , Robert L. Smith, Direction Choice for Accelerated Convergence in Hit-And-Run Sampling, Operations Research, v.46 n.1, p.84-95, January 1998 [doi>10.1287/opre.46.1.84]
• 12: Lovasz, L. and Simonovits, M., "Random Walks in a Convex Body and an Improved Volume Algorithm," Random Stuctures and Al#orit~ms 4, pp. 359-412, 1993.
• 13: Metropolis, N., A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller and E. Teller, "Equations of State Calculations by Fast Computing Machines," The Journal of Chemical Physics 21, pp. 1087-1092, 1953.
• 14: Romeijn, E. and R.L. Smith, "Simulated Annealing for Constrained Global Optimization," Journal of Global Optimization 5, pp. 101-126, 1994a.
• 15: Romeijn, E. and R.L. Smith, "Simulated Annealing and Adaptive Search in Global Optimization," Probability in the Engineering and injbrmational Sciences 8, pp. 571-590, 1994b.
• 16: Rubinstein, R.Y., "Generating Random Vectors Uniformly Distributed Inside and on the Surface of Different Regions," European Journal of Operations Research 10, pp. 205-209, 1982.
• 17: Schmeiser, B.W., "Random Variate Generation: A Survey". Simulation with Discrete Models: State of the Art View, T. I. Oren, C.M. Shub, P. F. Roth (eds), IEEE, pp. 79-104, 1980.
• 18: Smith, R.L., "Monte Carlo Procedures for Generating Random Feasible Solutions to Mathematical Programs," ORSA/TIMS Conference, Washington, May, 1980.
• 19: Smith, R.L. Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions. Operations Research 32, pp. 1296-1308,1984.
• 20: Zabinsky, Z.B., R.L. Smith, J.F. McDonald~ H.E. Romeijn, and D.E. Kaufman, "Improving Hit and Run for Global Optimization," Journal of Global Optimization 3, pp. 171-192, 1993.