Random walks on random graphs in critical regimes

Random walks on random graphs have in recent decades been studied from a number of different perspectives. Many of these have arisen in the physical sciences or computer science, where a suitably representative random walk on a random graph can offer an insight into the transport properties of a disordered medium or a complex network. The models proposed to understand these systems are often simple to define mathematically, but nonetheless have, in several particularly important cases, been shown to lead to a rich array of behaviour, which is sometimes rather counterintuitive. Although the situation in some of these fundamental examples is becoming increasingly well understood, the random walks on the random graphs in question continue to present deep challenges for mathematicians. This is particularly the case for random walks on random graphs in critical regimes, where a 'fractal' structure often makes the objects that arise difficult to analyse. The proposed research aims to tackle a number of key problems in this area.

To begin with, in studying the dynamical properties of random graphs, there is a particular focus at the moment on determining the effect of an external field, that is, a bias that makes a random walk on the graph more likely to jump in a particular direction on each step. Indeed, some notable results have been proved in this area. For instance, it has been shown for certain supercritical models that the dead-ends of the random environment create traps which become stronger as the bias is increased, so that when the bias is set above a certain critical value, the speed of the biased random walk is zero. This is a striking contrast to the case of a random walk on a regular lattice, where it is easily shown that the speed increases monotonically with the bias strength. In critical regimes, one would expect more extreme trapping behaviour - not only because the dead-ends are typically larger, but also because the asymptotic shapes of the sparse paths in the graph will themselves have an impact on the rate of escape of a biased random walk. Describing these effects will be the first aim of this project.

Secondly, a natural property of a random walk on a finite graph to study is its cover time, that is, the number of steps it takes until the random walk has visited every vertex of the graph. As well as being a focus of attention for probabilists and combinatorialists, this quantity is of interest to theoretical computer scientists seeking to answer such questions as: 'How long should a randomised algorithm be run until it has explored the entire state space?'. It has recently been shown that there is a precise link between the expected cover time and a mathematical structure called the 'Gaussian free field' that, for certain sequences of graphs, has given a great insight into the asymptotic growth rate of cover times. However, many critical graphs do not fall into the class of graphs where these Gaussian free field estimates will yield optimal results, including in particular the critical version of the 'Erdos-Renyi random graph', which is a fundamental building block in theories of complex networks. This project will seek to provide alternative techniques for dealing with these cases

Finally, in order to further understand random walks on random graphs, it can be extremely informative to study the properties of their diffusion scaling limits. In the case when the random graph falls into a critical regime, it is routinely the case that these diffusions will have complex random fractal state-spaces, and behave anomalously - typically, sub-diffusively. The third part of this project will involve identifying 'new' types of behaviour that arise as a result of the interplay between the random processes considered and the irregularity of the media they traverse.

Random walks on random graphs offer an extremely attractive area of research for mathematicians - both in terms of identifying new phenomenon and in extending existing analytic techniques. To begin with, even simple examples of random walks on random graphs often lead to a rich array of behaviour, which is sometimes surprising when juxtaposed with classical examples of random walks on graphs. Moreover, their study demands the development of robust analytic techniques that do not rely on exact symmetries the underlying space. This being the case, work in this area can help mathematicians distil their understanding of the connections between geometrical properties of a space and the stochastic processes defined upon it, and it is consequently not surprising that so many probabilists have chosen to focus their research efforts upon it.

The anticipation is that the current project will benefit the above-mentioned group of researchers by not only increasing the understanding of random motions in random environments, but also by providing new tools for studying them. It is further hoped that the PI's analysis of the limiting diffusions will benefit the growing number of mathematicians researching stochastic processes on fractals. Additionally, it is likely that, although not a direct focus of the project, the PI's results will have an impact for researchers working on the geometry of random graphs and branching processes. He will reach these audiences by appropriate dissemination of the results, and through well-chosen collaborations (details of these activities can be found on the pathways to impact statement).

Beyond the mathematical community, there is potential for the current investigation to provide results of interest to physicists and computer scientists looking to model the dynamical properties of disordered media and complex networks. Whilst the PI does not expect to have direct contact on this project with applied practitioners of these disciplines, he does intend to disseminate parts of the project in a way that will reach theorists in them. Such communication will help enrich the theoretical underpinnings of these areas by clearly explaining when sometimes anomalous phenomena can be expected to occur. In the longer-term, this could contribute to the development of more robust network-based algorithms, for example.