Probability - Summer School

Gulbenkian Foundation, LISBON — September 2 to 6, 2019



sketch for the panel Começar by José de Almada Negreiros - image reproduced with kind permission of the Gulbenkian Foundation

Program

This school comprises three lecture courses (in English) aimed at 1st- or 2nd-year undergraduate students of mathematics, complemented by problem sessions. The courses will begin at 10am on Monday September 2nd and end at 5pm on Friday September 6th. A detailed schedule will be posted by the end of June.

Courses

Shuffling cards and adding numbers: a peek at Markov chains

by Persi Diaconis (Stanford University)

Abstract: This course will study two real world problems: how many times should a deck of 52 cards be shuffled to mix it (answer 'about seven'). How do the 'carries' go when numbers are added in the usual way? Strangely, these problems are 'the same'. Showing and understanding this will be our project. Along the way, we will learn about Markov chains and techniques for studying their rates of convergence to stationarity. The subject will be developed from the beginning. A charming introduction to the subject of Markov chain mixing is in David Levin, Yuval Peres and Elizabeth Wilmer's Markov Chains and Mixing times . The first few chapters of this is more than adequate. Here is a tentative lecture plan:
  • Lecture 1: Introduction to shuffling cards and Markov chains
  • Lecture 2: The 'seven shuffles theorem'
  • Lecture 3: 'adding numbers (carries and cocycles)
  • Lecture 4: Generalization: random walk and hyperplane arrangements
  • Lecture 5: Where do we go from here(pointers and problems)
Prerequisites: It would help to have taken a first course on elementary probability.


Mixing times of Markov chains: famous problems and the techniques behind their solutions.

by Evita Nestoridi (Princeton University)

Abstract:This course will focus on presenting some popular techniques for bounding mixing times of Markov chains. We will then use them to study famous problems in card shuffling, urn models, and interacting particle systems. Here is a tentative lecture plan:
  • 1) Mixing times of Markov chains and strong stationary times.
  • 2) Mixing times of Markov chains and coupling techniques.
  • 3) Random walks on the chambers of a hyperplane arrangement.
  • 4) Wilson's lemma and some applications.
  • 5) The exclusion process and interchange process.


Random walks, electrical networks and uniform spanning trees

by Perla Sousi (University of Cambridge)

Abstract: A random walk is called recurrent if it returns to its starting point infinitely many times with probability one. Otherwise it is called transient. How do we determine whether a walk is transient or recurrent? One way is by viewing the graph as an electrical network and calculating effective resistances. This course will start by developing the theory of electrical networks and the connection to random walks. Kirchhoff in 1847 was the first one to find a connection of spanning trees to electrical networks. Spanning trees in a connected graph are basic objects of great interest in combinatorics and computer science. In this course we will study what a typical spanning tree looks like and we will discuss elegant sampling algorithms using random walks due to Aldous, Broder and Wilson from the 1990's. These connections have yielded many insights on the geometry of uniform spanning trees; this is a topic of intense current research. Here is a tentative lecture plan:
  • Lectures 1-2: Random walks and electrical networks
  • Lecture 3: Connection between electrical networks and uniform spanning trees
  • Lectures 4-5: Algorithms for sampling uniform spanning trees -- Uniform spanning forests


Monday, September 2 Tuesday, September 3 Wednesday, September 4 Thursday, September 5 Friday, September 6
9:45-10:00 opening
10:00-11:00 P. DIACONIS P. DIACONIS P. SOUSI E. NESTORIDI P. DIACONIS
11:00-11:30 coffee break coffee break coffee break coffee break coffee break
11:30-12:30 E. NESTORIDI E. NESTORIDI P. DIACONIS P. SOUSI E. NESTORIDI
12:30-14:00 lunch break lunch break P. DIACONIS
(until 13.30) 		lunch break lunch break
14:00-15:00 P. SOUSI E. NESTORIDI P. SOUSI P. SOUSI
15:00-15:30 coffee break coffee break coffee break coffee break
15:30-17:00 PROBLEM SESSION PROBLEM SESSION PROBLEM SESSION PROBLEM SESSION

Friday, September 6th at 5.30pm, after the problem session, there will be a meeting in the lecture room where the participants will be able to talk to the lecturers about academic life in a relaxed setting.

On Friday we will go out to dinner at 7.30pm to Restaurante Pano de Boca at Teatro Aberto, right next to the Gulbenkian Foundation.

Mini-conference

On Saturday, September 7th, there will be a student mini-conference in the same venue as the school where some of the participants in the undergraduate research program will present their projects. All school participants are invited to attend this mini-conference. Here is the schedule of the mini-conference.

Course assistant

Rodrigo Marinho ()

Venue

The school will take place at the headquarters of the Gulbenkian foundation with lectures and problem sessions in Sala 1. There is a map under Local Information.