Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T18:06:09.349Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing

Published online by Cambridge University Press:  27 July 2009

David Aldous
David Aldous
Affiliation:
Department of StatisticsUniversity of California Berkeley, California
Get access Rights & Permissions [Opens in a new window]

Abstract

Uniform distributions on complicated combinatorial sets can be simulated by the Markov chain method. A condition is given for the simulations to be accurate in polynomial time. Similar analysis of the simulated annealing algorithm remains an open problem. The argument relies on a recent eigenvalue estimate of Alon [4]; the only new mathematical ingredient is a careful analysis of how the accuracy of sample averages of a Markov chain is related to the second-largest eigenvalue.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 1 , Issue 1 , January 1987 , pp. 33 - 46
Copyright
Copyright © Cambridge University Press 1987

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. In: Séminaire de Probabilités XVII. Springer Lecture Notes in Mathematics 986, p. 243–297.Google Scholar
Aldous, D. (1986). Implications of relaxation times for 1-dimensional Markov chains. Technical Report No. 65, Statistics Dept., Berkeley, Calif.Google Scholar
Aldous, D. and Diaconis, P. (1986). Strong uniform times and finite random walks. Technical Report #59, Statistics Department, Berkeley, California. (To appear in Adv. Appl. Math.)Google Scholar
Alon, N. (1986). Eigenvalues and expanders. Combinatorica, to appear.CrossRefGoogle Scholar
Aragon, C. R., Johnson, D. S., McGeogh, L. A., and Schevon, C. (1986). Optimization by simulated annealing: an experimental evaluation. Preprint, Computer Science Dept., Berkeley, Calif.Google Scholar
Broder, A. Z. (1986). How hard is it to marry at random? (On the approximation of the permanent). STOC 86, Assoc. Computing Machinery, Baltimore, Md., p. 50–58.CrossRefGoogle Scholar
Freedman, D. (1971). Markov Chains. Holden-Day.Google Scholar
Hajek, B. (1986). Cooling schedules for optimal annealing. Coordinated Sci. Lab., University of Illinois, Urbana, Ill.Google Scholar
Hammersley, J. M. and Handscomb, D. C. (1964). Monte Carlo Methods. Methuen, London.CrossRefGoogle Scholar
Jerrum, M., Valiant, L., and Vazirani, V. (1985). Random generation of combinatorial structures from a uniform distribution. Department of Computer Science, University of Edinburgh.Google Scholar
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science 220: 671–680.CrossRefGoogle ScholarPubMed
Knuth, D. (1968, 1969, 1973). The Art of Computer Programming, Vols. 1–3. Addison-Wesley, Reading, Mass.Google Scholar
Mitra, D., Romeo, F., and Sangiovanni-Vincentelli, A. (1986). Convergence and finite-time behavior of simulated annealing. Adv. Appl. Prob., 18: 747–771.CrossRefGoogle Scholar
Ross, S.M. (1980). Introduction to Probability Models. Academic Press, New York.Google Scholar
Seneta, E. (1980). Non-negative Matrices and Markov Chains. Springer-Verlag, New York.Google Scholar
Sloane, N. J. A. (1983). Encrypting by random rotrations. In: Cryptography, ed. Beth, T.. Springer Lecture Notes in Computer Science 149.Google Scholar
Tsitsiklis, J. N. (1986). Markov chains with rare transitions and simulated annealing. Preprint, Electrical Eng. Dept., M.I.T.Google Scholar
Vanderbilt, D. and Louis, S. G. (1984). A Monte Carlo simulated annealing approach to optimization over continuous variables. J. Computational Phys. 56: 259–271.CrossRefGoogle Scholar