TMS081 Randomiserade Algoritmer

TMS081 Randomiserade Algoritmer


The course litterature is "Finite Markov Chains and Algorithmic Applications" by Olle Häggström. There should be some copies of this at Cremona, otherwise check Bokfynd for good deals (the best at the time of writing seems to be Bokus). Much of the course will follow last years program, so the curious can look at that.

Here is a paper about Metropolis-Hastings which I handed out in class.


The first lesson will be Tuesday, March 27th, at 13:15 in room MVF31 (This is correct and supercedes any information from elsewhere. We start the second week by Chalmers count.). Please spend the time before then reviewing your knowledge about basic probability (Chapter 1 in the book) as I will not go through this in class.

Times will be Tuesday, 13:15 in MVF31, and Fridays 10:00 in FL73. See the TMS schedule.

There will be no class on Tuesday, May 8th!

113Introduction, Markov Chains2
2More Markov Chains2,3
316Stationary Distributions5
4More stationarity and reversibility5,6
517Markov Chain Mote Carlo7
6Using MCMC for Bayesian Statistics
718Fast Convergence8
819No class
9Approximate Counting9
1020Simulated Annealing13
11Randomized Algorithms
1221Randomized Algorithms
13Randomized Algorithms

I will spend the final sessions discussing various examples of popular randomized algorithms and some of the analysis of them. This doesn't have too much to do with the earlier Markov-chain stuff that forms the core of the course, but is truer to the name. It also gives us flexibility.


There will be a written exam (that is, one taken alone in a single session) at the end of the course. The exact date has not been scheduled yet, but it will be during week 22. A homework project worth extra points on the exam will be assigned during the course.

UPDATE: The exam is on the 28th of May, 2007. In total, there will be 60 points worth for examination, with 20 from the project and 40 from the exam (thus to pass one need only do the project well and answer a single question on the exam).

Exam: Monday, 28th of May, 08:30-13:30, M-house. Write your email addresses on the exam, and I will notify you of the results by email.


Here are some suggested projects. If you have your own idea, feel free to approach me. Ideally there should only be one group doing each thing, if we can work out who does what the 28th of April that would be good.
  • Problem 7.4 in the book describes a generalization of the hard-core model. This model contains a parameter lambda, the value of which affects the behvior of the model: in particular, there is a critical value of lambda where the result changes from "mostly zeros" to "checkerboard like" on the square lattice. Simulate the model and estimate the critical value.
  • Somewhat similar: Example 11.1 in the book describes the Ising model, a very important model in statistical physics. Implement some MCMC simulation of the Ising model, and see if it agrees with the claim about the phase transition.
  • Generalize my example from class of the parents and children living in a square grid in some interesting ways (allow multiple children, let children get married and move in together, have several generations, etc.). Use MCMC to simulate realizations and see how far apart people with different relations (siblings, cousins, nephews, etc) live.
  • Implementing simulated annealing to the traveling salesman problem, and try it out on real world data (for example the 50 largest cities in Sweden, or anywhere else in the world, using physical distance in km or travel time by train, plane, etc.)
Direct any further questions to Oskar Sandberg.