Denys Wilkinson Building, Department of Physics, University of Oxford, Keble Road, Oxford OX1 3RH

Prof. Werner Krauth

Ecole Normale Superieure Paris and Rudolf Peierls Centre for Theorectial Physics, Oxford University

Werner Krauth

Times and dates: weeks 1-8 of HT 2024, Tue 14:00-16:00 in the Fisher Room

These public lectures introduce to the vast field of algorithms and computing from the view- point of theoretical physics and its interface with statistics. It is also a practical, example- based, primer on subjects such as Markov chains, molecular dynamics, phase transitions, path integrals, superfluids and Bose-Einstein condensation, among others. The lectures stress the rigorous foundations and modern developments in mathematics (mixing, non-reversibility, perfect sampling,... ) and physics (entropic phase transition, Kosterlitz-Thouless physics, cold atoms,... ), yet is entirely based on miniature Python programs. It will prepare advanced undergraduates in physics/math for the requirements of modern-day research across many fields, with the huge role played by algorithmic thinking, its power, paradoxes and intricacies.

Contents:

**Sampling, Markov chains**

– Direct Sampling: From basic rejection sampling to Walker’s method of aliases.

– Reversible and non-reversible Markov chains: One-dimensional motion.

– Mixing and relaxation times, the cutoff phenomenon.

– Perfect sampling: Stopping rules, Coupling from the past.

– Data analysis: From the strong law of large numbers to the ergodic theorem for Markov chains.

**Classical hard disks and hard spheres**

– Molecular dynamics: From Alder and Wainwright (1957) to modern heap-based scheduling.

– Hard-sphere Monte Carlo: From Metropolis et al. (1953) to the event-chain Monte Carlo.

– Entropic phase transitions: melting.

– One-dimensional simple exclusion models.

**Quantum Monte Carlo**

– Density matrices and path integrals.

– Superfluidity and condensate fractions: a path-integral point of view.

– Sampling of path integrals: the L ́evy construction (Gaussian bridge).

– Ideal bosons from a path-integral perspective.

– Path integrals and random manifolds. Roughness exponents, fractional Brownian motion.

**Spin systems: samples and exact solutions**

– Ising Markov chains: from Glauber dynamics to modern cluster algorithms.

– Mixing and relaxation times: modern mathematics and cutting-edge algorithms.

– 2D XY model and the harmonic model: Reversible and non-reversible Markov-chain algorithms. Kosterlitz- Thouless physics.

– Perfect sampling: semi-order

– Modern sampling algorithms derived from the Onsager solution.

**From Monte Carlo sampling to Machine learning – Inference and Bayesian statistics**

– Learning and classification

Literature:

- W. Krauth, ”Statistical Mechanics, Algorithms and Computations” (Oxford University Press, 2006; Second edition: 2024)
- D. A. Levin and Y. Peres, ”Markov Chains and Mixing Times (Second Edition)” (AMS, 2017)
- L. Wasserman, ”All of Statistics, A Concise Course in Statistical Inference” (Springer, 2005)