Markov Processes, Mixing Times and Cutoff

Gaussian processes indexed by trees form an interesting class of correlated random fields where the structure of extremal processes can be studied. One popular example is Branching Brownian motion, which has received a lot of attention over the last decades, non the least because of its connection to the KPP equation. In this talk I review the construction of the extremal process of standard and variable speed BBM (with Arguin, Hartung, and Kistler)

Let $\pi$ denote the intractable posterior density that results when the likelihood from a multivariate linear regression model with errors from a scale mixture of normals is combined with the standard non-informative prior. There is a simple data augmentation (DA) algorithm and a corresponding Haar PX-DA algorithm that can be used to explore $\pi$. I will explain how the behavior of the mixing density near the origin is related to the rate at which the corresponding Markov chains converge. (This is joint work with Yeun-Ji Jung, Kshitij Khare and Qian Qin.)

Multi-marginal optimal transport with Coulomb cost arises as a dilute limit of density functional theory, which is a widely used electronic structure model. The number N of marginals corresponds to the number of particles. I will discuss the question whether “Kantorovich minimizers” must be “Monge minimizers” (yes for N = 2, open for N > 2, no for N =infinity), and derive the surprising phenomenon that the extreme correlations of the minimizers turn into independence in the large N limit. I will also discuss the next order term limit and the connection of the problem to Coulomb and Riesz gases. The talk is based on joint works with Gero Friesecke (TUM), Claudia Klueppelberg (TUM), Brendan Pass (Alberta) and Mircea Petrache.

Suppose $\Phi=C_1\wedge C_2\wedge \cdots \wedge C_m$ is a predicate on variables $X_1,\ldots,X_n$. The Lovász Local Lemma gives a lower bound on the probability that $\Phi$ is true in the situation where $X_1,\ldots,X_n$ are independent random variables with specified distributions. If this lower bound is greater than zero, then we are assured that there is some assignment to the variables that satisfies $\Phi$. Moser and Tardos described a polynomial-time algorithm for finding a satisfying assignment when the condition of the Lovász Local Lemma holds. It is natural to ask whether it is possible in polynomial time to sample an assignment from the conditional distribution of $(X_1,\ldots,X_n)$ given that $\Phi$ is true. We characterise the situations in which the Moser-Tardos approach – which we might describe as ``partial rejection sampling'' – does indeed output a sample from this conditional distribution. We then explore ways to extend partial rejection sampling to a wider range of examples. Based on joint work with Heng Guo (Queen Mary) and Jingcheng Liu (UC, Berkeley).

We prove that every random walk in a uniformly elliptic random environment satisfying the cone mixing condition and a non-effective polynomial ballisticity condition with high enough degree has an asymptotic direction. This is a joint work with Enrique Guerra.

Take a one-dimensional random walk with zero mean increments, and consider the sizes of its overshoots over the zero level. It turns out that this sequence, which forms a Markov chain, always has a stationary distribution of a simple explicit form. The questions of uniqueness of this stationary distribution and convergence towards it are surprisingly hard. We were able to prove only the total variation convergence, which holds for lattice random walks and for the ones whose distribution, essentially, has density. We also obtained the rate of this convergence under additional mild assumptions. We will also discuss connections to related topics: local times of random walks, stability of reflected random walks, ergodic theory, and renewal theory. This is joint work with Vlad Vysotsky.

Sums of a geometrically distributed number of IID random variables occur in applications in many areas, including insurance, queueing theory and statistics. In this talk we will consider several settings in which random variables of interest may be successfully approximated by such geometric sums. In each case, we will give explicit error bounds (derived using Stein's method) to quantify the approximation results. Our main application is to passage times for stationary Markov chains. We will also demonstrate how our error bounds may be simplified under certain assumptions on the structure of the underlying random variables. This is illustrated by a brief look at approximation results for some performance measures for the M/G/1 queueing model.

A discrete-time Markov chain on the nonnegative integers (assumed to be homogeneous, irreducible and aperiodic, but not necessarily stochastic) with matrix $P^{(n)}$ of $n$-step transition probabilities is said to have the strong ratio limit property (SRLP) if there exist positive constants $R$, $\mu(i)$ and $f(i)$ such that \[ \lim_{n \to \infty} \frac{P^{(n+m)}(i,j)}{P^{(n)}(k,l)} = R^{-m} \frac {f(i)\mu(j)}{f(k)\mu(l)}, \quad i,j,k,l \in \mathbb{N}_0,~m \in \mathbb{Z}. \] (Under suitable circumstances the constants $\mu(i)$ may be normalized to constitute a quasistationary distribution.) The SRLP was enunciated in the setting of recurrent Markov chains by Orey (1961) and introduced in the more general setting at hand by Pruitt (1965). Since then the problems of finding necessary and/or sufficient conditions on $P = P^{(1)}$ for the corresponding Markov chain to possess the SRLP, and of identifying the constants, has received quite some attention in the literature, albeit mainly in the literature of the 20th century. The most general results to date have been obtained by Kesten (1995) and Handelman (1999).

In the talk I will give some information on the history of these problems, and discuss their solutions in the setting of discrete-time birth-death processes. I will then show that by suitably interpreting the necessary and sufficient condition for the SRLP in the birth-death setting, a condition emerges which, in a wider setting, is meaningful and conjectured to be a necessary condition for the SRLP to prevail. The conjecture involves the concept of asymptotic period of a Markov chain, which coincides with the period of the chain if it is recurrent, but may be larger than the period if the chain is transient.

Consider a separable Banach space $W$ supporting a non-trivial Gaussian measure $\mu$. Then there exist (almost surely) successful couplings of two W-valued Brownian motions $B$ and $B'$ begun at starting points $B(0)$ and $B'(0)$ if and only if the difference $B(0) - B'(0)$ of their initial positions belongs to the Cameron-Martin space $H$ of $W$ corresponding to $\mu$.

For more general starting points, can there be a “coupling at time infinity”, such that almost surely $\|B(t) - B'(t)\|$ goes to $0$ as $t$ goes to infinity? We propose (and discuss some partial answers to) the question, to what extent can one express the probabilistic Banach space property “Brownian coupling at time infinity is always possible” purely in terms of Banach space geometry?

Usually acceptance/rejection (AR) is woefully slow for Markov Random Fields (MRF) unless the interaction parameters are weak on a global scale. Other perfect simulation algorithms such as Coupling From the Past (CFTP) can deliver perfect samples in time O(d ln(d)) where d is the dimension of the MRF in the case that the parameters are locally weak. Here I will present a variant of AR called Cluster Partially Recursive Acceptance Rejection (CPRAR) that can generate samples recursively in O(d) time when the parameters are locally weak. Unlike CFTP, the method can automatically be applied in continuous settings as well.

Planar random growth processes occur widely in the physical world. Examples include diffusion-limited aggregation (DLA) for mineral deposition and the Eden model for biological cell growth. One approach to mathematically modelling such processes is to represent the randomly growing clusters as compositions of conformal mappings. In 1998 Hastings and Levitov proposed one such family of models and conjectured that this family exhibits a phase transition from clusters that converge to disks to clusters that converge to random irregular shapes. In this talk we will discuss ongoing work on a natural extension of the Hastings-Levitov family. For this model, we are able to prove that both singular and absolutely continuous scaling limits can occur. Specifically, we can show that for certain parameter values, the resulting cluster can be shown to converge to a randomly oriented one-dimensional slit, whereas for other parameter values the scaling limit is a deterministically growing disk. This is based on work in progress with Alan Sola (Stockholm) and Fredrik Viklund (KTH).

We discuss an interesting an interesting class of random walks on the symmetric group

Coupling is a way of constructing Markov processes with prescribed laws on the same space. The coupling is called Markovian if the coupled processes are co-adapted to the same filtration. We will first investigate Markovian couplings of elliptic diffusions and demonstrate how the rate of coupling (how fast you can make the coupled processes meet) is intimately connected to the geometry of the underlying space. Next, we will consider couplings of hypoelliptic diffusions (diffusions driven by vector fields whose Lie algebra span the whole tangent space). Constructing successful couplings (where the coupled processes meet almost surely) for these diffusions is a much more subtle question as these require simultaneous successful coupling of the driving Brownian motions as well as a collection of their path functionals. We will construct successful Markovian couplings for a large class of hypoelliptic diffusions. We will also investigate non-Markovian couplings for some hypoelliptic diffusions, namely the Kolmogorov diffusion and Brownian motion on the Heisenberg group, and demonstrate how these couplings yield sharp estimates for the total variation distance between the laws of the coupled diffusions when Markovian couplings fail. Furthermore, we will demonstrate how non-Markovian couplings can be used to furnish purely analytic gradient estimates of harmonic functions on the Heisenberg group by purely probabilistic means, providing yet another strong link between probability and geometric analysis. This talk is based on joint works with Wilfrid Kendall, Maria Gordina and Phanuel Mariano.

The last few years have seen much progress in the area of perfect simulation algorithms for multi-server queueing systems, allowing us to sample from the exact equilibrium distribution of the Kiefer-Wolfowitz workload vector. This talk will review some recent work on designing a so-called “omnithermal" algorithm for M/G/c queues, which allows us to sample simultaneously from the equilibrium distributions for a range of c (the number of servers), for relatively little additional computational cost.

I will consider the convergence rate of Gibbs samplers for a Bayesian linear model. The convergence rate will be connected to a principled approach to output analysis. In particular, I will describe a problem-independent lower bound on effective sample size that can be used to terminate the simulation and illustrate its use in the Gibbs sampler.

Adaptive MCMC algorithms are designed to self tune for optimal sampling performance, and hence they change the transition kernel of the underlying Markov chain as the simulation progresses, and characteristics of the target distribution are being revealed. This strategy breaks Markovianity, and while hugely successful in applications, these algorithms are notoriously difficult to analyse theoretically. We introduce a class of Adaptive Increasingly Rarely Markov Chain Monte Carlo (AIRMCMC) algorithms where the underlying Markov kernel is allowed to be changed based on the whole available chain output but only at specific time points separated by an increasing number of iterations. The main motivation is the ease of analysis of such algorithms. Under assumption of either simultaneous or (weaker) local simultaneous geometric drift condition, or simulta- neous polynomial drift we prove the Strong and Weak Laws of Large Numbers (SLLN, WLLN), and discuss how our approach extends the existing results. We argue that many of the known Adaptive MCMC may be transformed into an AIR version and provide an empirical evidence that the performance of the AIR version stays virtually the same.

We consider a stochastic aggregation model on Z^d. Start with an infinite collection of particles located at the vertices of the lattice, with at most one particle per vertex, and initially distributed according to the product Bernoulli measure with parameter $\mu\in(0,1)$. In addition, there is an aggregate, which initially consists of only one particle placed at the origin. Non-aggregated particles move as continuous time simple symmetric random walks obeying the exclusion rule, whereas aggregated particles do not move. The aggregate grows indefinitely by attaching particles to its surface whenever a particle attempts to jump onto it. Our main result states that if on Z^d, d at least 2, the initial density of particles \mu is large enough, then with positive probability the aggregate grows with positive speed. This is a joint work with Vladas Sidoravicius.

The convergence of Markov processes to stationary distributions is a basic topic of introductory courses in stochastic processes, and the theory has been thoroughly developed. What happens when we add killing to the process? The process as such will not converge in distribution, but the survivors may; that is, the distribution of the process, conditioned on survival up to time t, converges to a "quasistationary distribution" as t goes to infinity. I present an analogue of the transience-recurrence dichotomy for killed one-dimensional diffusions. Under fairly general conditions, a killed one-dimensional diffusion conditioned to have survived up to time t either escapes to infinity almost surely (meaning that the probability of finding it in any bounded set goes to 0) or it converges to the quasistationary distribution, whose density is given by the top eigenfunction of the adjoint generator. Killing may be assumed to happen at fairly general rates everywhere on the domain, in contrast to earlier methods that depended on killing happen only on the boundary. The rate of internal killing is found to play a complex role in determining the convergence in situations where the underlying motion is not positive recurrent. These theorems arose in resolving part of a longstanding problem in biological theories of ageing, concerning the conditions under which mortality rates level out at advanced age. The same formal analysis turns out to play a key role in other problems in population biology, the effect of unequal damage inheritance on population growth rates. Generalisations of this work turn out to provide a basis for a novel MCMC algorithm (that will be the topic of a later talk by Andi Wang). The talk is based on collaborations with Steve Evans and with Martin Kolb.

We will consider the problem of optimally stopping a function of a general Markov process (and suitable path functionals) in continuous time. We will show under very general conditions that if the gain function is in the domain of the martingale generator then so is the optimal payoff. We will give applications to the so-called smooth pasting condition and to the dual problem.

We introduce a natural extension of the exclusion process to hypergraphs and prove an upper bound for its mixing time. In particular we show the existence of a constant C such that for any connected hypergraph G within some class (which includes regular hypergraphs), the ε-mixing time of the exclusion process on G with any feasible number of particles can be upper-bounded by CT_EX(2,G)log(|V|/ε), where |V| is the number of vertices in G and T_EX(2,G) is the 1/4-mixing time of the corresponding exclusion process with two particles. The proof involves an adaptation of the chameleon process, a technical tool invented by Morris and developed by Oliveira for studying the exclusion process on a graph. This is joint work with Stephen Connor.

We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at $q = 2$ is bounded by a polynomial in the size of the underlying graph. As a consequence the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature also has a polynomial mixing time bound. Joint work with Mark Jerrum

The utility of a Markov chain Monte Carlo algorithm is, in large part, determined by the spectral gap of the corresponding Markov operator. However, calculating the spectral gaps of practical Monte Carlo Markov chains in statistics has proven to be an extremely difficult task, especially when these chains move on continuous state spaces. We develop a method for spectral gap estimation for general state space Markov chains whose operators are non-negative and trace-class. The method is based on the fact that the second largest eigenvalue (and hence the spectral gap) of such operators can be bounded above and below by simple functions of the power sums of the eigenvalues. These power sums often have nice integral representations. A classical Monte Carlo method is proposed to estimate these integrals, and a simple sufficient condition for finite variance is provided. This leads to asymptotically valid confidence intervals for the second largest eigenvalue (and the spectral gap) of the Markov operator. (This is joint work with James P. Hobert and Kshitij Khare.)

Kac's walks on the sphere and on the special orthogonal group, introduced in 1953 and 1970, have long histories in the statistical physics and computational statistics literatures. I will describe the history of these walks and review some of the many results on the mixing properties of these processes. I then present some recent work of myself and Pillai, which uses connections to random matrix theory to obtain substantially improved bounds on the mixing times of these two walks.

We consider the scaling limits of randomly trapped random walks on the integers and graphs with fractal structure. The Bouchaud trap model and random walk among heavy tailed random conductances both converge to a Fonte-Isopi-Newman (FIN) diffusion on the reals or the fractal. We study the heat kernel for this process and establish estimates in both the quenched and annealed cases. These are novel even in the case of the one-dimensional FIN diffusion. This is joint work with David Croydon and Takashi Kumagai.

The connections between random walks and electrical networks are well-known. As a recent result in this area, I will explain how convergence of a a sequence of spaces equipped with "resistance metrics" and measures converge with respect to the Gromov-Hausdorff-vague topology, and a certain non-explosion condition is satisfied, then the associated stochastic processes also converge. This result generalises previous work on trees, fractals, and various models of random graphs. I further conjecture that it will be applicable to the random walk on the incipient infinite cluster of critical bond percolation on the high-dimensional integer lattice. This is partly joint with Ben Hambly (Oxford) and Takashi Kumagai (Kyoto).

We consider the degree distributions of preferential attachment random graph models with choice similar to those considered in recent work by Malyshkin and Paquette and Krapivsky and Redner. In these models a new vertex chooses $r$ vertices according to a preferential rule and connects to the vertex in the selection with the $s$th highest degree. For meek choice, where $s>1$, we show that both double exponential decay of the degree distribution and condensation-like behaviour are possible, and provide a criterion to distinguish between them. For greedy choice, where $s=1$, we confirm that the degree distribution asymptotically follows a power law with logarithmic correction when $r=2$ and shows condensation-like behaviour when $r>2$.

Ever since the early days of computers, probability has been challenged by Markov process questions motivated by Monte Carlo problems. In this series of talks I will take a look at some (mostly) modern examples of this phenomenon mostly emanating from Markov chain Monte Carlo or one of its variants. Included in this whistle stop tour will be a look at high-dimensional limits of certain MCMC methods and their associated optimisation results, analysis of simulated tempering and other related algorithms designed for exploring multi-modal distributions; and convergence for adaptive MCMC methods. Regarding new Monte Carlo schemes, I will take a look at non-reversible MCMC methods and quasi-stationary MCMC; and also explore the MEXIT optimal coupling problem.

This talk will introduce novel methodologies for exploring posterior distributions by modifying methodology for exactly (without error) simulating diffusion sample paths. The methodologies discussed have found particular applicability to "Big Data" problems. We begin by presenting the Scalable Langevin Exact Algorithm (ScaLE) and recent methodological extensions (including Re-ScaLE, which avoids the need for particle approximation in ScaLE), which has remarkably good scalability properties as the size of the data set increases (it has sub-linear cost, and potentially no cost as a function of data size). ScaLE has particular applicability in the “single-core” big data setting - in which inference is conducted on a single computer. In the second half of the talk we will present methodology to exactly recombine inferences on separate data sets computed on separate cores - an exact version of “divide and conquer". As such this approach has particu lar applicability in the “multi-core” big data setting. We conclude by commenting on future work on the confluence of these approaches. Joint work with Hongsheng Dai, Paul Fearnhead, Adam Johansen, Divakar Kumar, Gareth Roberts.

Markov chains in continuous time were advocated by McKendrick (1914, 1926) as models for the evolution of the numbers of individuals of different kinds in interacting biological populations, but it was only in the early 1950s that Bartlett, Kendall, Bailey and others began to use them systematically. Much of the early work centred around attempts to solve the Kolmogorov equations exactly, which was possible only for a few examples. However, Kurtz (1970, 1971) showed that, if the transition rates are functions only of the densities of the populations, then limit theorems as the typical population size N increases can be established, at least over finite time intervals. These take the form of a deterministic fluid limit, around which there are Gaussian fluctuations.

In these lectures, we start with Kurtz's theory, and then progress to a study of behaviour over increasingly long time intervals. A main concern is with equilibrium behaviour, one of the most important features for biology. Many such models have an absorbing state representing extinction, in which there are no individuals left in any of the populations. However, it is often the case in these models that the (random) time needed to reach extincion is incredible long, and that, in the interim, the chain fluctuates around an `effective' equilibrium. We show how to use Bartlett's `return process', both as a theoretical and as a computational tool, to describe such quasi-equilibria. We then consider the speed of convergence to quasi-equilibrium. In typical scenarios, the time taken to reach equilibrium, as described in terms of total variation distance, is of the order of the logarithm of N; however, the distance from equilibrium changes from almost 1 to almost 0 over an interval whose length is asymptotically constant as N increases. If time permits, we may also describe how such processes escape from the neighbourhood of an absorbing boundary --- again, this typically takes a time of order log N.

As illustration, we shall use the Hamer--Soper--Bartlett model of a recurrent epidemic.

A move towards the decarbonisation of power networks is leading to increased variability and uncertainty on the both the demand and supply side. In this talk we will introduce the audience the power network, and differences to other well studied networks. As part of this we will describe a set of open problems on a range of scales from microgrids to transmission networks.

Public Health England undertakes modelling to prepare for, and respond to, bio-terrorism and emerging disease threats. In the Emergency Response Department a wide variety of modelling approaches are used to cover a range of topics. This talk presents a selection of models to consider topics related to contingency planning and outbreak support, including: pandemic influenza preparedness; individual host response; Ebola virus disease screening logistics.

Lasers can be used in a wide variety of applications such as range-finding, LIDAR, target identification and laser communication. However, the performance of a laser beam projected through the atmosphere can be badly affected by optical turbulence. Lightwave radiation passing through an optically-turbulent atmosphere encounters regions of differing refractive index, which act like weak lenses causing an apparently random distortion of the advancing wave-front and a corresponding deterioration in the quality of any projected image. Optical turbulence is characterised as a random process. The physics of wave-front propagation through a turbulent atmosphere is complex and is strictly applicable to weak turbulence regimes only. Computer simulation is a cost-effective alternative to expensive field trials, but the output requires to be validated against observed experimental data. This discussion provides a short overview of the relevant physics and of the problems to be encountered when devising a suitable statistical analysis of scintillated beam profiles for validation purposes.

Markov chains in continuous time were advocated by McKendrick (1914, 1926) as models for the evolution of the numbers of individuals of different kinds in interacting biological populations, but it was only in the early 1950s that Bartlett, Kendall, Bailey and others began to use them systematically. Much of the early work centred around attempts to solve the Kolmogorov equations exactly, which was possible only for a few examples. However, Kurtz (1970, 1971) showed that, if the transition rates are functions only of the densities of the populations, then limit theorems as the typical population size N increases can be established, at least over finite time intervals. These take the form of a deterministic fluid limit, around which there are Gaussian fluctuations.

In these lectures, we start with Kurtz's theory, and then progress to a study of behaviour over increasingly long time intervals. A main concern is with equilibrium behaviour, one of the most important features for biology. Many such models have an absorbing state representing extinction, in which there are no individuals left in any of the populations. However, it is often the case in these models that the (random) time needed to reach extincion is incredible long, and that, in the interim, the chain fluctuates around an `effective' equilibrium. We show how to use Bartlett's `return process', both as a theoretical and as a computational tool, to describe such quasi-equilibria. We then consider the speed of convergence to quasi-equilibrium. In typical scenarios, the time taken to reach equilibrium, as described in terms of total variation distance, is of the order of the logarithm of N; however, the distance from equilibrium changes from almost 1 to almost 0 over an interval whose length is asymptotically constant as N increases. If time permits, we may also describe how such processes escape from the neighbourhood of an absorbing boundary --- again, this typically takes a time of order log N.

As illustration, we shall use the Hamer--Soper--Bartlett model of a recurrent epidemic.

Motivated by applications to posterior sampling for Bayesian models involving discrete parameters, we consider the problem of designing local Metropolis-Hastings proposals that incorporate information from the target. In particular: given a fixed neighbourhood and given point-wise evaluations of the target density in all neighbouring states, what is the optimal Metropolis-Hastings proposal? Under regularity assumptions on the target, we derive the class of asymptotically optimal proposal distributions, which we call locally-balanced proposals. Such proposals are asymptotically maximal elements, in terms of Peskun ordering, among proposals obtained as pointwise transformation of the target density. In continuous frameworks, this class of proposals includes the Langevin MCMC scheme and can be seen as a generalization of gradient-based methods to discrete frameworks. We discuss asymptotic analysis, applications to statistical models with discrete parameters and connections to Multiple-Try Metropolis-Hastings.

A sequence of ergodic finite Markov chains exhibits a cutoff if the distance to stationarity decreases from near 1 to near 0 in a small window around the mixing time. Proving cutoff in specific models can be a challenge, requiring sharp upper and lower bounds on the mixing time. In the past decade, cutoff has been established for many families of chains, but many open problems remain. In these lectures, we survey many of the proof techniques and examples of cutoff.

Ever since the early days of computers, probability has been challenged by Markov process questions motivated by Monte Carlo problems. In this series of talks I will take a look at some (mostly) modern examples of this phenomenon mostly emanating from Markov chain Monte Carlo or one of its variants. Included in this whistle stop tour will be a look at high-dimensional limits of certain MCMC methods and their associated optimisation results, analysis of simulated tempering and other related algorithms designed for exploring multi-modal distributions; and convergence for adaptive MCMC methods. Regarding new Monte Carlo schemes, I will take a look at non-reversible MCMC methods and quasi-stationary MCMC; and also explore the MEXIT optimal coupling problem.

In machine learning literature, a large number of problems amount to simulate a density which is log-concave (at least in the tails) and perhaps non smooth. Most of the research efforts so far has been devoted to the Maximum A posteriori problem, which amounts to solve a high-dimensional convex (perhaps non smooth) program. The purpose of this lecture is to understand how we can use ideas which have proven very useful in machine learning community to solve large scale optimization problems to design efficient sampling algorithms, with convergence guarantees (and possibly « usable » convergence bounds »). In high dimension, only first order method (exploiting exclusively gradient information) is a must. Most of the efficient algorithms know so far may be seen as variants of the gradient descent algorithms, most often coupled with « partial updates » (coordinates descent algorithms). This of course suggests to study methods derived from Euler discretization of the Langevin diffusion, which may be seen as a noisy version of the gradient descent. Partial updates may in this context as « Gibbs steps » where some components are frozen. This algorithm may be generalized in the non-smooth case by « regularizing » the objective function. The Moreau-Yosida inf-convolution algorithm is an appropriate candidate in such case, because it does not modify the minimum value of the criterion while transforming a non smooth optimization problem in a smooth one. We will prove convergence results for these algorithms with explicit convergence bounds both in Wasserstein distance and in total variation.

Let each site of the square lattice $\mathbb{Z}^2$ be declared "closed" with probability $p$, a "target" with probability $q$, and "open" with probability $1-p-q$, where $0 \le p \le p+q \le 1$. Different sites are independent.

Consider the following game: a token starts at the origin, and the two players take turns to move it from its current site $x$ to a site in $\{x+(0,1),x+(1,0)\}$. A player moving to a closed site loses immediately. A player moving to a target site wins immediately. Otherwise, the game continues.

Is there positive probability that the game is drawn with best play - i.e. that neither player can force a win? We show that this question is equivalent to the question of ergodicity of a certain elementary one-dimensional probabilistic cellular automaton (PCA). We prove that the PCA is ergodic whenever $p+q<1$, and correspondingly that the game on $\mathbb{Z}^2$ has no draws.

On the other hand, we prove that for $q=0$ and $p$ sufficiently small, the analogous game does exhibit draws on various directed graphs in dimension $d \ge 3$. This is proved via a dimension reduction to a hard-core lattice gas in dimension $d−1$. We show that draws occur whenever the corresponding hard-core model has multiple Gibbs distributions. We conjecture that draws occur also on the standard oriented lattice $\mathbb{Z}^d$ for $d \ge 3$, but here our method encounters a fundamental obstacle.

If time permits, I will mention related games on trees or on undirected lattices.

We give an upper bound on the mixing time of finite reversible Markov chains using sequences of bottlenecks. We then use the geometric nature of this bound to look at how robust the mixing time is to small changes to the Markov chain.

Markov chains in continuous time were advocated by McKendrick (1914, 1926) as models for the evolution of the numbers of individuals of different kinds in interacting biological populations, but it was only in the early 1950s that Bartlett, Kendall, Bailey and others began to use them systematically. Much of the early work centred around attempts to solve the Kolmogorov equations exactly, which was possible only for a few examples. However, Kurtz (1970, 1971) showed that, if the transition rates are functions only of the densities of the populations, then limit theorems as the typical population size N increases can be established, at least over finite time intervals. These take the form of a deterministic fluid limit, around which there are Gaussian fluctuations.

In these lectures, we start with Kurtz's theory, and then progress to a study of behaviour over increasingly long time intervals. A main concern is with equilibrium behaviour, one of the most important features for biology. Many such models have an absorbing state representing extinction, in which there are no individuals left in any of the populations. However, it is often the case in these models that the (random) time needed to reach extincion is incredible long, and that, in the interim, the chain fluctuates around an `effective' equilibrium. We show how to use Bartlett's `return process', both as a theoretical and as a computational tool, to describe such quasi-equilibria. We then consider the speed of convergence to quasi-equilibrium. In typical scenarios, the time taken to reach equilibrium, as described in terms of total variation distance, is of the order of the logarithm of N; however, the distance from equilibrium changes from almost 1 to almost 0 over an interval whose length is asymptotically constant as N increases. If time permits, we may also describe how such processes escape from the neighbourhood of an absorbing boundary --- again, this typically takes a time of order log N.

As illustration, we shall use the Hamer--Soper--Bartlett model of a recurrent epidemic.

We study the behaviour of random walk on dynamical percolation. In this model, the edges of a graph are either open or closed and refresh their status at rate μ, while at the same time a random walker moves on G at rate 1, but only along edges which are open. On the d-dimensional torus with side length n, when the bond parameter is subcritical, the mixing times for both the full system and the random walker were determined by Peres, Stauffer and Steif. I will talk about the supercritical case, which was left open, but can be analysed using evolving sets (joint work with Y. Peres and J. Steif).

The first lecture will provide a gentle introduction, to be followed by examples in the second and third lectures. Some material will be drawn from the listed papers.
I Fluid limits in a Markovian framework – a general quantitative theory [3,4]
II Examples from population processes [1,2,3]
III An example from gas dynamics [4]

[1] Basdevant, Anne-Laure; Goldschmidt, Christina. Asymptotics of the allele frequency spectrum associated with the Bolthausen-Sznitman coalescent. Electron. J. Probab. 13 (2008), no. 17, 486–512.
[2] Darling, R. W. R. and Norris, J. R. (2008). Differential equation approximations for Markov chains. Probab. Surv. 5 37–79.
[3] Luczak, M. J.; Norris, J. R. Averaging over fast variables in the fluid limit for Markov chains: application to the supermarket model with memory. Ann. Appl. Probab. 23 (2013), no. 3, 957–986.
[4] Norris, James. A consistency estimate for Kac's model of elastic collisions in a dilute gas. Ann. Appl. Probab. 26 (2016), no. 2, 1029–1081.

A sequence of ergodic finite Markov chains exhibits a cutoff if the distance to stationarity decreases from near 1 to near 0 in a small window around the mixing time. Proving cutoff in specific models can be a challenge, requiring sharp upper and lower bounds on the mixing time. In the past decade, cutoff has been established for many families of chains, but many open problems remain. In these lectures, we survey many of the proof techniques and examples of cutoff.

The recent Scalable Langevin Exact (ScaLE) Algorithm of Pollock et. al. (2016) is a novel algorithm for efficiently performing exact Bayesian inference in a `Big Data' setting. The theory underpinning the convergence of ScaLE is in fact the theory of killed diffusions and convergence to quasistationary. In my talk I will give some foundational results in the application of quasistationarity to Monte Carlo inference. Firstly, I will give natural conditions for the quasilimiting distribution of a killed diffusion to coincide with a target density of interest, and secondly, quantifying the rate of convergence to quasistationarity by relating the killed process to an appropriate Langevin diffusion. (Joint work with Martin Kolb, Gareth Roberts and David Steinsaltz.)

Ever since the early days of computers, probability has been challenged by Markov process questions motivated by Monte Carlo problems. In this series of talks I will take a look at some (mostly) modern examples of this phenomenon mostly emanating from Markov chain Monte Carlo or one of its variants. Included in this whistle stop tour will be a look at high-dimensional limits of certain MCMC methods and their associated optimisation results, analysis of simulated tempering and other related algorithms designed for exploring multi-modal distributions; and convergence for adaptive MCMC methods. Regarding new Monte Carlo schemes, I will take a look at non-reversible MCMC methods and quasi-stationary MCMC; and also explore the MEXIT optimal coupling problem.

The first lecture will provide a gentle introduction, to be followed by examples in the second and third lectures. Some material will be drawn from the listed papers.
I Fluid limits in a Markovian framework – a general quantitative theory [3,4]
II Examples from population processes [1,2,3]
III An example from gas dynamics [4]

[1] Basdevant, Anne-Laure; Goldschmidt, Christina. Asymptotics of the allele frequency spectrum associated with the Bolthausen-Sznitman coalescent. Electron. J. Probab. 13 (2008), no. 17, 486–512.
[2] Darling, R. W. R. and Norris, J. R. (2008). Differential equation approximations for Markov chains. Probab. Surv. 5 37–79.
[3] Luczak, M. J.; Norris, J. R. Averaging over fast variables in the fluid limit for Markov chains: application to the supermarket model with memory. Ann. Appl. Probab. 23 (2013), no. 3, 957–986.
[4] Norris, James. A consistency estimate for Kac's model of elastic collisions in a dilute gas. Ann. Appl. Probab. 26 (2016), no. 2, 1029–1081.

We consider a simple stochastic model for the spread of a disease caused by two virus strains in a closed homogeneously mixing population of size N. In our model, the spread of each strain is described by the stochastic logistic SIS epidemic process in the absence of the other strain, and we assume that there is perfect cross-immunity between the two virus strains, that is, individuals infected by one strain are temporarily immune to re-infections and infections by the other strain. For the case where one strain has a strictly larger basic reproductive ratio than the other, and the stronger strain on its own is supercritical (that is, its basic reproductive ratio is larger than 1), we derive precise asymptotic results for the distribution of the time when the weaker strain disappears from the population, that is, its extinction time. We further consider what happens when the difference between the two reproductive ratios may tend to 0. This is joint work with Fabio Lopes.

Ordering the performance of Markov chain Monte Carlo algorithms based on reversible processes is rather well understood, and provides users with simple criteria allowing them to make design choices. In this talk we will show how these ideas can be extended to the non-reversible scenario and continuous time Markov Process Monte Carlo.

Coalescing random walks is a fundamental stochastic process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of $\log^2 n$), the coalescence time of $n$ random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. Finally, we will briefly discuss some results relating the coalescence time to the hitting time.

The first lecture will provide a gentle introduction, to be followed by examples in the second and third lectures. Some material will be drawn from the listed papers.
I Fluid limits in a Markovian framework – a general quantitative theory [3,4]
II Examples from population processes [1,2,3]
III An example from gas dynamics [4]

[1] Basdevant, Anne-Laure; Goldschmidt, Christina. Asymptotics of the allele frequency spectrum associated with the Bolthausen-Sznitman coalescent. Electron. J. Probab. 13 (2008), no. 17, 486–512.
[2] Darling, R. W. R. and Norris, J. R. (2008). Differential equation approximations for Markov chains. Probab. Surv. 5 37–79.
[3] Luczak, M. J.; Norris, J. R. Averaging over fast variables in the fluid limit for Markov chains: application to the supermarket model with memory. Ann. Appl. Probab. 23 (2013), no. 3, 957–986.
[4] Norris, James. A consistency estimate for Kac's model of elastic collisions in a dilute gas. Ann. Appl. Probab. 26 (2016), no. 2, 1029–1081.

The parabolic Anderson problem is the Cauchy problem for the heat equation on the integer lattice with random potential. It describes the mean-field behaviour of a continuous-time branching random walk. It is well-known that, unlike the standard heat equation, the solution of the parabolic Anderson model exhibits strong localisation. In particular, for a wide class of iid potentials it is localised at just one point. In the talk, we discuss a natural modification of the parabolic Anderson model on Z, where the one-point localisation breaks down for heavy-tailed potentials and remains unchanged for light-tailed potentials, exhibiting a range of phase transitions. This is a joint work with Stephen Muirhead and Richard Pymar.

A sequence of ergodic finite Markov chains exhibits a cutoff if the distance to stationarity decreases from near 1 to near 0 in a small window around the mixing time. Proving cutoff in specific models can be a challenge, requiring sharp upper and lower bounds on the mixing time. In the past decade, cutoff has been established for many families of chains, but many open problems remain. In these lectures, we survey many of the proof techniques and examples of cutoff.

We use the eigenvalues of the random-to-random card shuffle to prove a sharp upper bound for the total variation mixing time. Combined with the lower bound due to Subag, we prove that this walk exhibits cutoff at 3/4nlogn, answering a conjecture of Diaconis.

Recently Lubetzky and Peres showed that simple random walks on a sequence of d-regular Ramanujan graphs of increasing sizes exhibit cutoff in total variation. In this talk, an extremely simple alternative argument will be presented, under the assumption that for some r(n)≫1 the maximal number of simple cycles in a ball of radius r(n) in bounded.

Consider a deck of n cards, where each card is assigned a weight. Pick a card according to the weight distribution and move it to the top. This is the famous card shuffle, known as the Tsetlin library. We will discuss cutoff for this model and explain that it falls in a wider category of walks on the chambers of hyperplane arrangements. Then, we will introduce an optimal strong stationary time for a class of hyperplane arrangement walks, which will allow for the first time to talk about lower bounds and cutoff for the separation distance mixing time.

Motivated by the need to understand better the behaviour of geodesics on scale-invariant random spatial networks (SIRSN), I have been studying random scattering processes on the Poisson line SIRSN. This has led me to an axiomatization of abstract scattering processes -- Markov chains which algebraically look like scattering processes. I will discuss this axiomatization and its application to random processes on SIRSN.