# Instructor:

A. Taylan Cemgil
For contact details and further information see the web: http://www.cmpe.boun.edu.tr/~cemgil/

# TA

Ilker Gundogdu, Serhan Danis

# Course Description

Monte Carlo methods are stochastic simulation based algorithms designed to compute answers to problems where exact solutions are intractable and take exponential time to compute.

While these techniques provide an exact answer only asymptotically, they perform remarkably well in practice and are now used extensively in science and engineering, including statistics, machine learning, aerospace, computer vision, network analysis, speech recognition, robotics, physics and bioinformatics.

The scope of this course is to review the following fundamental aspects in Monte Carlo computations:

1. Model construction

2. Design of strategies for inference

3. Theoretical aspects (convergence proofs, performance analysis)

Our exposure will be primarily slanted towards inference strategies.

In particular, we will study Markov Chain Monte Carlo methods and Sequential Monte Carlo. Our ultimate aim is to provide a basic understanding of computational techniques based on Monte Carlo simulations and associated concepts such that the students can orient themselves in the relevant literature and understand the current state of the art.

## Notebooks

Some Class notes can be found as iPython notebooks

# Submissions

• We will use the grader system we have developed based on git.

# Computer Usage

We will use Python, ipython notebooks and occasionally Octave. See:

Starting Octave
octave --force-gui


Octave is a popular matlab clone. So, most (but not all) matlab material is useful

## Alternative Computing environments

• Written Exam 40

• Homeworks 20

• Final Project and Presentation 40

# Slides

1. Lecture 0 Introduction, Course structure, Motivating Examples

2. Lecture 1 History of the MC method, Law of Large numbers, Central Limit Theorem

3. Lecture 2 Random Number generation, Rejection sampling, Importance Sampling

4. Lecture 3 Discrete state space Markov Chains, MCMC, Metropolis-Hastings Algorithm

5. Lecture 4 Gibbs sampler, Applications

6. Lecture 5 Model Selection

7. Lecture 6 Model Selection (older version)

8. Lecture 8 Sequential Monte Carlo

1. Lecture 7 Reversible Jump

# Assignments

1. Uniform sampling on the circle

2. Uniform sampling of permutations

3. Code Breaking

4. Solitair

5. Hit and Run, Uniform sampling on convex sets

6. Simulated Annealing, LP Solver, Convex Optimization

7. Variable Selection in Linear Regression

8. Change Point, Multiple Change Point

9. Slice Sampling

10. HMC Hybrid Monte Carlo

11. Reversible Jump MCMC

12. Stan

13. Nonparametric Bayesian method

# Reference Books

• Jun S. Liu, Monte Carlo Strategies in Scientific Computing, 2001, Springer.

• Adam M. Johansen and Ludger Evers (edited by Nick Whiteley), Monte Carlo Methods, Lecture notes, University of Bristol
Available online

# References

## Probability Theory

• Geoffrey Grimmet and David Stirzaker, Probability and Random Processes, (3rd Ed), Oxford, 2006

• Companion book containing 1000 exercises and solutions

• Grinstead and Snell, Introduction to probability, available online!

• Dimitri P. Bertsekas and John N. Tsitsiklis. Introduction to Probability. Athena Scientific, 2002

## Random Variate Generation

• L. Devroye. Non-Uniform Random Variate Generation. Springer, 1986. Freely available online.

• Stack Overflow

# Applications

## HMM's and Parameter Estimation

• T. Ryden, EM versus Markov chain Monte Carlo for Estimation of Hidden Markov Models: A Computational Perspective, Bayesian Analysis (2008), 3(4), p.p. 659-688