The Metropolis Algorithm: Theory and Examples

The Metropolis algorithm is a Markov Chain Monte Carlo optimization technique of stunningly broad applicability.

This short monograph quickly develops the underlying theory of ergodic Markov chains, explains the algorithm in general terms, and presents eight specific applications ranging from a Sudoku puzzle solver to the Traveling Salesman Problem:

Four Puzzling Applications:

• Sudoku Solver
• Creating Sudoku Puzzles
• Generating Random Crossword Puzzles
• KenKen Solver

Four Serious Applications:

• Reconstructing Degraded Images
• The Traveling Salesman Problem
• Portfolio Optimization
• Data Clustering

All the applications are implemented with accompanying source code hosted freely downloadable on GitHub at
https://github.com/CDouglasHoward13/Metropolis

Douglas Howard is the coordinator of the Bachelor of Science major in Financial Mathematics at Baruch College, City University of New York. He is the co-founder of the Financial Engineering Masters Program at Baruch College and was its first Director. Doug has a decade of Wall Street experience involving the application of probabilistic models to the financial markets.