Probability, Operations, and Dynamics

Research

Research in the POD-group addresses all features of random phenomena – modelling, structuring, analysis, control, optimisation – and covers both fundamental and applied aspects.

Research combines ideas, methods and techniques from different parts of mathematics – including algebra, analysis, combinatorics, geometry, number theory and statistics – and builds bridges towards computer science, information science, network science, statistical physics and population genetics. Key challenges are:

– Clarify the links between structure and functionality of complex networks.
– Strengthen the fundamental role of Markov decision processes in reinforcement learning and modern algorithms.
– Elucidate the multiple relationships between analytic, geometric and stochastic properties of dynamical systems.
 

• Probability Theory
   Research concentrates on

•  Interacting stochastic systems
  (disordered systems, random polymers, metastability).
• Population genetics
  (spatial multi-type populations, evolution, seed-banks).
• Complex networks
  (random graphs, random processes on random graphs).

Key tools are large deviation theory, stochastic analysis and combinatorics. Research aims at understanding emergent phenomena.

Interacting stochastic systems consist of a large number of interacting ran- dom components. Even when the interaction is local and simple, such sys- tems typically exhibit complex global behaviour, resulting in critical behaviour and phase transitions. The challenge is to introduce paradigm models and unravel the complex random spatial structures arising in these models. Statistical physics provide the conceptual ideas, while probability theory provides the mathematical language and framework. Areas of focus have been random walks in random environments, random polymer chains, metastability for near-critical systems, percolation, intermittency, renormalisation, and breaking of ensemble equivalence.

Much of the knowledge that has been built up in statistical physics over the past decades is rapidly making its way into biology. One of the tasks is to help facilitate this cross-fertilisation and to address concrete biological questions at the interface. Population genetics analyses how genetic traits spread over a multi-type population via evolutionary forces like resampling, mutation, selection, migration and recombination. Epidemiology analyses how an infection spreads through a spatial population and how this spread can be minimised via invasive actions. Areas of focus have been immunology, dormancy, and synchronisation in the bio-clock.

Connectedness is the new paradigm of modern society. The goal is to analyse both the structure and the functionality of large real-world complex networks, by analysing models of random graphs and random processes evolving on them. The analysis of structural properties focusses on model selection, community detection and spectral distributions. The analysis of functional properties focusses on search algorithms, spread of information, metastability. Both static and dynamic networks are interesting. Areas of focus have been mixing for random walks on dynamic random graphs, random-access wireless networks, spectra of random graphs, random spanning forests, wavelets and multi-resolution analysis of networks.

Operations Research 
Research concentrates on

•  Markov decision processes
  (equilibrium, convergence, stability).
•  Markov games (conflicts, optimisation).
•  Machine learning (online learning).
•  Discrete optimisation (convexity).

Key tools are the theory of stochastic processes and combinatorics.  

In Markov decision processes one of the main issues concerns stability. How can stability be checked? If stable, then how fast does the network reach its stationary distribution? If unstable, then what does the quasi-stationary distribution look like? How can efficient algorithms be developed to control the network according to pre-set optimisation criteria? Are these algorithms amenable to practical implementation? What can be said about the structure of optimal policies? Which type of customer must be prioritised to optimise network performance? All these questions can be studied within the framework of Markov chain theory. In healthcare, for instance, Markov decision processes are crucial for the management of care for patients, with the goal to minimise healthcare cost and maximise patient utility.

In Markov games often the situation arises where there are conflicting interests, for instance, maximising server efficiency versus minimising customer dissatisfaction. They can also be used for auction models, where optimal policies are needed. If the problem of optimal bidding is under incomplete information for a firm that procures items to meet random demands, then optimisation and learning methods can be combined through participation in a finite sequence of auctions.
Applications also arise in  queueing theory. Examples are real-market pricing and capacity-allocation problems. Many contemporary enterprises, such as airlines, entertainment facilities, hotels, rental car companies or conference/event organizers, face the problem of restricted capacity and unevenly distributed demand between peak and off-peak periods. They sell a “perishable” product and cannot keep inventory to satisfy the demand on peak periods. Moreover, customer-willingness-to-pay varies according to the period of service. 

Online learning is an area of machine learning. A typical setting is that of a controlled stochastic system for which the laws of evolution are either partially or completely unknown to the decision maker. The estimation of these laws must be incorporated into the problem of optimal control of the system in an efficient manner. One application concerns individuals or firms making decisions in the face of both risk (i.e., stochastic behaviour) and uncertainty (i.e., lack of information). Another application is multi-armed bandit problems, which concern sequential sampling from populations with unknown parameters. The sampling cost may prohibit the use of populations with high outcomes because their sampling cost may be too high. The decision maker must identify the populations with the best balance, and allocate the sampling effort in an optimal manner. Examples include situations where limited resources (such as production or storage capacities, capital, etc.) must be efficiently allocated under partial information. The decision maker must design online learning and control policies that ensure efficient learning at as low a cost as possible.

Discrete optimisation is particularly important for models where it is hard to verify convexity or even midpoint convexity. A new class of discrete optimisation problems are the so-called Ameso problems. Examples concern generalisation and relaxation of midpoint convexity, for which algorithms are proposed that employ the proximity framework while using descent algorithms for discrete midpoint convex functions. Markov theory can be applied to inventory management, where optimal solutions (profit maximisation, cost minimisation) are explored for multi-product models with demand substitution and unknown problem parameters (learning). Another aspect is approximation of complex models. For instance, for call centers with a call-back option it is difficult to develop analytical solutions, but accurate estimates through approximation are possible. 

Ergodic Theory & Dynamical Systems
Research concentrates on

• Stochastic dynamics
  (Gibbs-non-Gibbs transitions, hidden Markov chains, sandpiles).
•  Infinite ergodic theory (mixing, intermittency).
•  Interval maps (number expansions).

Stochastic dynamics studies transfer operators describing the evolution of densities under the dynamics. Their eigenfunctions correspond to invariant densities. Spectral properties of transfer operators help to understand basic quantitative and qualitative properties. Particularly interesting are transfer operators of random dynamical systems (skew products), where at each time instance a point is transformed by one of several maps, chosen randomly. Novel aspects arise for random mixtures of hyperbolic and non-hyperbolic maps. Hyperbolic maps are known to lead to transfer operators with strong contraction properties (spectral gap), while non-hyperbolic maps typically do not possess such properties. An interesting phenomenon is that mixed transfer operators are almost as good as hyperbolic transfer operators: many have smooth invariant densities. There is an interesting link between algebraic dynamical systems and solvable models of statistical physics. It turns out that entropies of apparently different systems often coincide, and that this `mere' coincidence is not accidental.

The theory of random processes with heavy tails is a well-developed tool to describe extreme events in a variety of applications (including financial mathematics, risk analysis, statistical physics). However, its theoretical basis is largely restricted to processes with so-called regularly varying tails. Infinite ergodic theory can be viewed as the “deterministic dynamical systems” analogue of the latter. As opposed to the finite measure-preserving setting, in the infinite measure-preserving setting there is no convergence of Birkhoff averages in the classical way (at best only in the sense of convergence in distribution), and a range of different stochastic laws may apply to them. In particular, the notion of mixing is delicate, and quantitative estimates are the subject of recent progress obtained by exploiting spectral properties of transfer operators. Quantitative mixing for key systems of physical interest (variants of intermittent maps and Lorentz gases) are still open.

The interaction between ergodic theory and number theory has a long and fruitful history. An interesting focus is on the relation between number expansions, including but not limited to integer-based and non-integer-based expansions and continued fractions, and the dynamics of deterministic and random interval maps. Such number expansions play a role in various digital technologies, such as analog-to-digital converters, cryptosystems, and pseudo-random number generators. The statistical properties of these number expansions, such as digit frequencies and recurring patterns, form an important ingredient and can be obtained from the long-term behaviour of typical orbits in the corresponding dynamical system. Further interest concerns the properties of numbers with exceptional expansions, which ties in with a branch of fractal geometry.