TMS081 Randomiserade Algoritmer

Litterature

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.

Schedule

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!

Lesson	Week	Subject	Chapter
1	13	Introduction, Markov Chains	2
2	13	More Markov Chains	2,3
3	16	Stationary Distributions	5
4	16	More stationarity and reversibility	5,6
5	17	Markov Chain Mote Carlo	7
6	17	Using MCMC for Bayesian Statistics
7	18	Fast Convergence	8
8	19	No class
9	19	Approximate Counting	9
10	20	Simulated Annealing	13
11	20	Randomized Algorithms
12	21	Randomized Algorithms
13	21	Randomized 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.

Exam

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.

Projects

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.