Topics in random graphs and discrete snakes

Networks are a simple yet effective way of representing the interaction of a large number of components in a system. With applications in science, technology, and social studies, their relevance today is paramount. More specifically, as large datasets become increasingly commonplace, various disciplines face the challenge of interpreting data originating from large networks.

In mathematics, networks are modelled by graphs. The topic of random graphs is an active area of research, and while the study of random graphs has high cross disciplinary impact, it also comprises of interesting mathematical problems for probabilists and combinatorialists alike.

In recent years, much work has been conducted on the topic of the scaling limits of random graphs. Central to this study is the Continuum Random Tree (CRT), introduced by Aldous in the early 1990s. To be brief, the CRT is a continuous tree-like structure which appears as the scaling limit of certain size-conditioned Bienaymé trees. Since the work of Aldous, many have drawn on the CRT to study the scaling limits of various discrete structures.

This project aims to do the same, and build on this theory with a focus on the scaling limits of discrete snakes on random trees. Informally, this is branching structure where in addition to having a genealogy, each node has an associated trajectory. In the limit, the snake structure combines the continuous structure of the CRT with independent spatial motions governed by a Markov process.

The applications of discrete snakes are again varied. As discussed by Le Gall, snakes have connections to partial differential equations. On the other hand, snakes are often employed to study the convergence of random planar maps. See for example the works of Miermont, and Le Gall, on the scaling limits of uniform random plane quadrangulations, as well as that by Addario-Berry and Albenque concerning the scaling limits of random simple triangulations and quadrangulations of the sphere.

The convergence of discrete snakes has been studied in many settings. Together, Janson and Marckert studied the convergence of discrete snakes on size conditioned Bienaymé trees with offspring distribution having finite exponential moments, where the displacements are i.i.d, mean zero, and satisfy certain moment conditions. Marzouk later established convergence results for similar discrete snakes on size conditioned critical Bienaymé trees whose offspring distribution belongs to the domain of attraction of a stable law. Of perhaps highest relevance to this project, in 2008, Marckert proved convergence of globally centred snakes on critical Bienaymé trees whose offspring distribution have bounded support. This result is particularly powerful, as it allows one to consider a wider class of displacement distributions, including deterministic displacements. This can serve as a strong tool when using snakes to understand properties of random graphs.

One specific avenue for exploration in this project is to build on the work of Marckert to determine the scaling limit of certain globally centred snakes on critical Bienaymé trees with offspring distribution having unbounded support. As a first step, we intend to focus our attention to discrete snakes on trees with Poisson(1) offspring distribution.

This project falls within the EPSRC Mathematical Analysis, Statistics and Applied Probability, and Logic and Combinatorics research areas, and is supervised by Professor Christina Goldschmidt.

Probabilistic modelling permeates the Financial services, healthcare, technology and other Service industries crucial to the UK's continuing social and economic prosperity, which are major users of stochastic algorithms for data analysis, simulation, systems design and optimisation. There is a major and growing skills shortage of experts in this area, and the success of the UK in addressing this shortage in cross-disciplinary research and industry expertise in computing, analytics and finance will directly impact the international competitiveness of UK companies and the quality of services delivered by government institutions.
By training highly skilled experts equipped to build, analyse and deploy probabilistic models, the CDT in Mathematics of Random Systems will contribute to
- sharpening the UK's research lead in this area and
- meeting the needs of industry across the technology, finance, government and healthcare sectors

MATHEMATICS, THEORETICAL PHYSICS and MATHEMATICAL BIOLOGY

The explosion of novel research areas in stochastic analysis requires the training of young researchers capable of facing the new scientific challenges and maintaining the UK's lead in this area. The partners are at the forefront of many recent developments and ideally positioned to successfully train the next generation of UK scientists for tackling these exciting challenges.
The theory of regularity structures, pioneered by Hairer (Imperial), has generated a ground-breaking approach to singular stochastic partial differential equations (SPDEs) and opened the way to solve longstanding problems in physics of random interface growth and quantum field theory, spearheaded by Hairer's group at Imperial. The theory of rough paths, initiated by TJ Lyons (Oxford), is undergoing a renewal spurred by applications in Data Science and systems control, led by the Oxford group in conjunction with Cass (Imperial). Pathwise methods and infinite dimensional methods in stochastic analysis with applications to robust modelling in finance and control have been developed by both groups.
Applications of probabilistic modelling in population genetics, mathematical ecology and precision healthcare, are active areas in which our groups have recognized expertise.

FINANCIAL SERVICES and GOVERNMENT

The large-scale computerisation of financial markets and retail finance and the advent of massive financial data sets are radically changing the landscape of financial services, requiring new profiles of experts with strong analytical and computing skills as well as familiarity with Big Data analysis and data-driven modelling, not matched by current MSc and PhD programs. Financial regulators (Bank of England, FCA, ECB) are investing in analytics and modelling to face this challenge. We will develop a novel training and research agenda adapted to these needs by leveraging the considerable expertise of our teams in quantitative modelling in finance and our extensive experience in partnerships with the financial institutions and regulators.

DATA SCIENCE:

Probabilistic algorithms, such as Stochastic gradient descent and Monte Carlo Tree Search, underlie the impressive achievements of Deep Learning methods. Stochastic control provides the theoretical framework for understanding and designing Reinforcement Learning algorithms. Deeper understanding of these algorithms can pave the way to designing improved algorithms with higher predictability and 'explainable' results, crucial for applications.
We will train experts who can blend a deeper understanding of algorithms with knowledge of the application at hand to go beyond pure data analysis and develop data-driven models and decision aid tools
There is a high demand for such expertise in technology, healthcare and finance sectors and great enthusiasm from our industry partners. Knowledge transfer will be enhanced through internships, co-funded studentships and paths to entrepreneurs