Algorithms and Complexity - Main page Algorithms and Complexity

Seminar: Discrete Random Walks: Theory and Applications

Dozentin: Dr. Mihyun Kang

Termine

SE Dienstag 11:00 - 13:00 (RUD 25, 3.101)
Sprechzeit Dienstag 13:00 - 14:00
Das Seminar wird in englischer Sprache durchgeführt.

Zuordnung

  • Hauptstudium, Seminar

Inhalte und Lernziele

Random walks are topics and methods in graph theory, combinatorics, randomized algorithms, computational biology, probability and pysical statistics. Random walks defined on discrete structures yield Monte Carlo methods which sample a random element according to a given probability distribution. The running time of a Monte Carlo simulation depends on the mixing time, namely the convergence rate of a random walk to the stationary distribution. This course will provide a gentle introduction to random walks, several techniques to bound the mixing time, and the applications such as to card shufflings, graph colorings, SAT problems. All participants of the course should give a talk, and the language of the course is English.

Vortragsthemen

21.10.03 Introduction to the course and the assignment of the talks
28.10.03 Introduction to Discrete Random Walks
04.11.03 No seminar
11.11.03 Dirk Schubert Card shuffling
18.11.03 Mike Löffler Triangulation walk
25.11.03 Hiep Han Graph coloring
02.12.03 Christian Rothe SAT
09.12.03 Matthias Beick Rejection sampling
16.12.03 Hernan Alperin Coupling from the past
06.01.04 Stefan Vigerske Random planar graphs
13.01.04 Wei Tang Spanning trees
20.01.04 David Salz Random walks on the cube
27.01.04 Melanie Sell Matching
03.02.04 Sascha Bauer Volume estimation

Empfohlene Literatur

Introduction

  • D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs, Monograph in preparation.
  • P. Diaconis, Group Representations in Probability and Statistics, Inst. Math. Stat., Hayward, 1988
  • M. Dyer and C. Greenhill, Random walks on combinatorial objects, in Surveys in Combinatorics (J. D. Lamb and D A. Preece, eds.), London Mathematical Society Lecture Note Series 267, 101-136, Cambridge University Press, Cambridge, 1999.
  • M. Jerrum, Mathematical foundations of the Markov chain Monte Carlo method, in Probabilistic Methods for Algorithmic Discrete Mathematics (M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed eds.), Algorithms and combinatorics 16, 116-165, Springer, 1998
  • M. Jerrum and A. Sinclair, The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration, in Approximation Algorithms (D. Hochbaum), PWS Publishing Company, Boston, 1997.

Card shuffling

  • D. Aldous and P. Diaconis, Shuffling cards and stopping times, Am. Math. Mon. 93 (1986), 333-348.
  • P. Diaconis, Group Representations in Probability and Statistics, Inst. Math. Stat., Hayward, 1988.

Triangulation walk

  • L. McShine and P. Tetali, On the mixing time of the triangulation walk and other Catalan structures, DIMACS Series in Disc. Math. and Theoret. Comput. Sci. 43 (1999), 147-159.
  • M. Molloy, B. Reed, and W. Steiger, On the mixing rate of the triangulation walk, DIMACS Series in Disc. Math. and Theoret. Comput. Sci. 43 (1999), 179-190.

Graph coloring

  • R. Bubley and M. Dyer, Path coupling: A techque for proving rapid mixing in Markov chains, In 38th Anuual Symposium on Foundations of Computer Science (1997), 223-231.
  • E. Vigoda, Improved bounds for sampling colorings, J. Math. Phys. 41 No.3 (2000), 1555-1569 (In 40th Anuual Symposium on Foundations of Computer Science, 1999).
  • M. Dyer, C. Greenhill, M. Molloy, Very rapid mixing of the Glauber dynamics for proper colourings on bounded-degree graphs, Random Structures and Algorithms 20 (2002), 98-114.

SAT

  • C. Papadimitriou, On selecting a satisfying truth assignment, In Proceedings of the 32nd Annual IEEE FOCS, 163-169, 1991.
  • U. Schöning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, Proc. of the 40th IEEE FOCS, 410-414, 1999.

Rejection sampling

  • J. Fill, An Interruptible Algorithm for Perfect Sampling via Markov Chains, Annals of Applied Probability 8 (1998), 131-162.
  • J. Fill, M. Machida, D. Murdoch, and J. Rosenthal, Extension of Fill's Perfect Rejection Sampling Algorithm to General Chains, Random Structures & Algorithms 17 (2000), 290-316.

Coupling from the past

  • J. Propp and D. Wilson, Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics, Random Structures and Algorithms, volume 9 number 1&2 (1996), 223-252.
  • D. Wilson, How to Couple from the Past Using a Read-Once Source of Randomness, Random Structures and Algorithms Vol.16 No.1 (2000), 85-113.

Random planar graphs

  • C. McDiarmid, A. Steger and D. Welsh, Random planar graphs, manuscript, 2003.
  • A. Denise, M. Vasconcellos and D. Welsh, The random planar graph, Congr. Numerantium 113 (1996), 61-79.

Spanning trees

  • D. Aldous, The random walk construction of uniform spanning trees and uniform labelled trees, SIAM J. Discrete Math. 3 No.4 (1990), 450-465.
  • R. Pemantle, Uniform random spanning trees, Topics in contemporary probability and its applications (J.Snell ed.), Boca Raton, CRC Press, Probability and Stochastics Series (1995), 1-54.

Random walks on the cube

  • D. Aldous, Minimization algorithms and random walk on the d-cube, Ann. Probab. 11 (1983), 403-413.
  • P. Matthews, Mixing rates for a random walk on the cube, SIAM J. Algebraic Discrete Methods 8 (1987), 746-752.
  • D. Wilson, Random random walks on $Z_2^d$, Probab. Theory Relat. Fields 108 No.4 (1997), 441-457.

Matching

  • A. Sinclair, Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow, Combinatorics, Probability and Computing 1 (1992), 351-370.

Volume estimation

  • M. Dyer, A. Frieze, R. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, J. Assoc. Comput. Mach. 38 No.1 (1991), 1-17.
  • R. Kannan, L. Lovász, M. Simonovits, Random walks and an $O^*(n^5)$ volume algorithm for convex bodies, Random Struct. Algorithms 11 No.1 (1997), 1-50.
last modified 09/23/09 (alkox-www)