Abstracts

Volker Betz
Spatial and non-spatial random permutations without long cycles

I will start by presenting the basic model and open questions of spatial random permutations. Next, I will report on some recent results (joint with Lorenzo Taggi) concerning the geometry of forced long cycles in a situation favouring short cycles. Finally, I will report on rather comprehensive results (joint with Helge Schäfer and Dirk Zeindler) about a model of non-spatial random permutations conditioned to have no long cycles.

Leonid Bogachev
Liouville-type theorems for the archetypal equation with rescaling

The archetypal equation is a linear functional-integral equation y(x) = E[y(α(x-β))] with random rescaling coefficients α, β. The talk concerns Liouville-type theorems asserting that any bounded continuous solution is constant; e.g., in the case α = 1 this is the celebrated Choquet–Deny theorem. Observing that solutions y(x) are harmonic functions of the associated Markov chain (Xn), the proofs are based on iterating the archetypal equation with suitable stopping time and using Doob's optional stopping theorem applied to the martingale y(Xn). [Joint work with Gregory Derfel (Beer Sheva) and Stanislav Molchanov (UNC-Charlotte).]

Matthew Dickson
Large Deviation Principles for Bosonic Random Permutations

Bosons are quantum particles whose wave-functions are symmetric under the transposition of particles. It is therefore natural that permutations, cycles and partitions play an important role in their behaviour. Here we use the Feynman-Kac representation of the ideal Bose gas to induce a probability measures on permutations. We will describe these measures using large deviation principles, and see how the famous Bose-Einstein condensation (BEC) phenomena manifests itself from this perspective. Large deviation techniques will also allow us to more easily consider some measures induced by interacting Bose gases, and how BEC manifests differently in these models. Joint work with Stefan Adams (University of Warwick).

Catherine Donati-Martin
Deformed models in random matrix theory (RMT) and free probability

In this talk, we analyse the spectrum of Hermitian random matrices of large size. After reviewing classical results (Wigner's theorem), we consider perturbations of well-known models in RMT. We focus on additive perturbation of Wigner matrices and show how we can describe the limiting spectral measure and extreme eigenvalues in terms of objects coming from free probability.

Alain Durmus
The Langevin MCMC: theory and methods

In machine learning and computational imaging 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. However, in order to perform more complex analyses, for example, uncertainty quantification or model selection, it is necessary to be able to simulate the density of interest and therefore computationally intensive techniques such as Markov chain Monte Carlo methods have to be used. The purpose of this talk is to understand how we can use ideas which have proven very useful in signal processing community to solve large scale (non-smooth) 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. This, of course, suggests studying methods derived from Euler discretization of the Langevin diffusion, which may be seen as a noisy version of the gradient descent. 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 a 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.

Jennie Hansen
From mappings to permutations

In this talk, we view random permutations as a particular example of random mappings with exchangeable in-degrees. From this perspective, a uniform random permutation is part of a continuum of random mappings with anti-preferential attachment and we are interested in the component structure of the mappings in this continuum as, in some sense, the mappings become more like permutations. The results presented are based on urn scheme arguments and calculus for random mappings with exchangeable in-degrees that have been developed in a series of papers by Hansen and Jerzy Jaworski, (Adam Mickiewicz University), who was supported by the Marie Curie Intra-European Fellowship No. 236845 (RANDOMAPP) within the 7th European Community Framework Programme.

Claus Koestler
Markovianity as a distributional symmetry

Exchangeability or spreadability are distributional symmetries of an infinite sequence of random variables which characterize the sequence to be conditionally independent and identically distributed. Related results of de Finetti type have recently been transferred to noncommutative probability. My talk will review some of these results and discuss ongoing research on the characterization of Markovianity as a distributional symmetry related to the Thompson group F.

Tor Lattimore
Learning to Rank

Ranking is the process of producing an ordered shortlist of K items from a larger collection. For example, choosing which movies to show on the homepage of a streaming service. The problem can be treated in a sequential setting where users are continuously requesting new rankings and the learning algorithm aims to maximise the quality of its shortlists based on feedback from the user. I will talk about what assumptions are necessary to make this problem tractable and present a simple algorithm and analysis.
This is based on joint work with Csaba Szepesvari.

Stephen Muirhead
The band structure of spatial random permutations

A spatial random permutation (SRP) is a model of random permutation that is biased towards the identity in some underlying geometry; well-known examples include the Mallows permutation and Feynman's representation of the Bose gas. SRPs are expected to exhibit certain universal phenomena, such as crossover behaviour in the mean displacement ("band structure") and the emergence of macroscopic cycles when the band exceeds a critical width. In this talk, we study the band structure of a Boltzmann model of SRP on a lattice in which the energy is equal to the total displacement. Our analysis rests on a surprising connection between random permutations and Gaussian processes, via the matrix permanent; even though this connection is well-known in other contexts, its application to random permutations is to the best of our knowledge novel. Joint work with Yan Fyodorov (King's College London).

Nina Snaith
Random Matrix Theory here, there and everywhere

Eigenvalues of Hermitian and unitary random matrices display distinctive behaviour that we see mirrored in many places in mathematics and the wider world. This talk will discuss the application of random matrix theory to number theory and to other situations, probing its ubiquitousness.

Henning Schomerus
Zero modes in random matrices - robust features against a random background

I review the classification of random-matrix ensembles with topological features, resulting from eigenvectors with eigenvalue pinned to zero. In physics, these zero modes appear as robust features of the hermitian Hamiltonian, for which a complete classification in terms of universality classes exists. This classification also carries over to unitary matrices (describing transport) and Wishart-type matrices (describing dynamics). I also discuss the consequences of broken hermiticity, realised in physics by loss and gain in optical systems, for which a systematic classification remains challenging.

Csaba Szepesvari
On Completing the Classification of Adversarial Partial Monitoring Games

Imagine that you are playing the game of penny matching in an adversarial setting where information is costly: The environment, your adversary, secretly picks a finite sequence of heads and tails. Your aim is to figure out whether the sequence has more heads or tails. The game proceeds in a sequential fashion: In each round, you can decide whether you want to bet (by saying heads or tails) on the next outcome of the environment's choice, or you are seeking information. You pay one pound for each error, and you pay a predetermined c>0 pounds each time you seek information You will only learn about the environment's choice for that round if you sought for information. Your performance is measured against the single best bet (heads or tails) of the omniscient oracle that knows the whole sequence. If information is free (c=0), the game is trivial, if information is relatively cheap (c<1/2), the regret, the difference between the loss of the learner and the omniscient oracle, apart from logarithmic factors grows as n^1/2, while if information is expensive, c>1/2, the regret grows as n^2/3, where n is the sequence length. This problem is a special subclass of finite partial monitoring where a learner needs to solve an explore-exploit dilemma with a rich feedback structure. The classification problem is concerned with characterizing the set of possible finite partial monitoring problems from the point of view of how fast the regret of an optimal learner grows as the number of rounds. Previous work that involved the speaker gave a partial solution to this question: In particular, it was shown that the regret is either zero, grows linearly, or it grows like n^1/2 or n^2/3 (up to logarithmic factors), except that the classification theorem ruled out certain games which were seen as corner cases. As it turns out, penny matching when c=1/2 is an example of such a corner case. In this talk I will sketch how this gap can be closed, thus, making the classification of all adversarial partial monitoring games complete.

Nicolas Vayatis
Diffusion phenomena in networks: virality, influence and control

In this talk, a unified framework is proposed to characterize contagion phenomena in three different fields: SIR epidemics, bond percolation and information cascades. In particular, a phase transition phenomenon is described for the behaviour of the influence under the assumption of a locally positively correlated random graph which involves spectral characteristics of the underlying network. In the second part of the talk, the question of controlling SIS epidemics will be tackled under two different strategies: one based on dynamic allocation of treatments with the idea of seeking for the largest reduction in the amount of infectious edges, and the second based on a priority planning for which tight bounds on the epidemic threshold and the extinction time are provided. All strategies have been tested numerically for a variety of network models and diffusion/recovery rates.