Probabilistic coupling and nilpotent diffusions

Lead Research Organisation: University of Warwick
Department Name: Statistics

Abstract

A major theme of modern probability is that one can discover much about a random system by comparing the behaviour of two copies of the system, based on different but inter-related sources of randomness. The simplest example is that of a symmetric random walk, as might arise in a fair coin-tossing game. The random walk moves independently up or down with equal probability. Consider two such random walks, begun at time 0 at heights -k and k respectively. Suppose their randomness is interrelated by reflection, so that one moves up as the other moves down, and vice versa. Very simple arguments show that the two walks must almost surely eventually meet ("couple"); and they will do so when they first (and simultaneously) visit height 0.

This so-called reflection coupling can be vastly generalized: to more general kinds of random walks, to interacting particle systems, to many sorts of discrete random system using a technique called path-coupling, and to continuous random systems using stochastic calculus. It turns out that the method delivers powerful techniques for analyzing these systems. For example, rate of convergence to stochastic equilibrium (a crucial question in many applications) is controlled by the rate at which coupling occurs.

The project concerns a generalization of this question. Can we couple not only the system, but also and simultaneously some functionals of the system? In the random walk example, one might ask whether we can couple not only the random walks, but also the (signed) areas under their trajectories? Knowing a general answer to this question would substantially increase the possibilities for using the coupling technique to analyze random systems. The difficulty is that the functional is not subject to the same kind of direct control as is the system itself. The jumps of the random walks can be correlated or anti-correlated directly. The areas under the trajectories can only be affected indirectly. The problems that arise are very similar to those that occur when one tries to park a car in a confined parking slot: one would like to move the car sideways (analogous to directly controlling the areas under the trajectories), but can only alter the forwards-and-backwards motion of the car, together with some slight changes in direction (analogous to controlling the correlation between the jumps).

We now know a number of cases in which the answer is that we can couple functionals. For example, taking the case of continuous systems as a clean technical case, we now know how to control areas under trajectories. The aim of this project is to extend this to cover the most general possible case in which the answer might be expected to be yes, at least in the case of continuous systems: namely the case of so-called nilpotent diffusions. A priori this seems very ambitious; one might suppose it more likely that the options to control implicitly sets of extra functionals are very limited. But it now seems very likely that the answer is yes, based on a number of key examples in which coupling has been established, and based on the techniques adopted when doing this, and we have been able to set down a programme by which a proof may be found. This project is about proving the general result, estimating the rate at which the resulting coupling will occur, and relating the result both to other areas of mathematics and to applications in optimal transportation (how to move volumes of material efficiently from one set of locations to another), to statistical simulation (important in the study of randomized computer algorithms and in modern statistical estimation), stochastic dynamical systems (as arise for example in global meteorology and ocean dynamics), and the theory of rough paths.

Planned Impact

The primary impact of this project will be on probability and applied probability. Results from this work will extend the range of the important technique of probabilistic coupling to cover hypoelliptic and well as elliptic stochastic differential systems. This will greatly enhance the possibilities of application of coupling, and will also substantially influence our understanding of the evolution of stochastic dynamical systems. This impact will be international in scale, helping to maintain and to extend the UK's very strong reputation for innovation in this area of science.

Further impact in mathematical science will be on workers in related areas: mathematical analysts working on hypoelliptic partial differential equations (for whom this will offer a new methodological tool); Lie algebraists (who will discover a new application of their important subject); and control theorists (for whom this will represent an example of a nonstandard and singular control problem).

Benefits beyond mathematical science are longer term, but will include instances in which random dynamical systems play an important role (eg, global meteorology, ocean dynamics).

The project will also deliver significant contributions in terms of training of skilled personnel, both in training the RA to be an international research expert in an important probability concept, and in associated PhD projects in probability. As noted in the 2011 International Review of Mathematics, probability is pervasive throughout modern science and technology, and the supply of capable researchers is limited. Thus these training opportunities will result in high national impact.

Publications

10 25 50
publication icon
Zanella G (2017) A Dirichlet form approach to MCMC optimal scaling in Stochastic Processes and their Applications

publication icon
Zanella G (2017) A Dirichlet form approach to MCMC optimal scaling in Stochastic Processes and their Applications

publication icon
Kendall, W S (2014) Lines and networks in Markov Processes and Related Fields

publication icon
Kendall Wilfrid Stephen (2019) Rayleigh Random Flights on the Poisson line SIRSN in arXiv e-prints

publication icon
Kendall W (2020) Rayleigh Random Flights on the Poisson line SIRSN in Electronic Journal of Probability

publication icon
Kendall W (2015) Coupling, local times, immersions in Bernoulli

publication icon
Kendall W (2016) Return to the Poissonian city in Journal of Applied Probability

publication icon
Kendall W (2017) From random lines to metric spaces in The Annals of Probability

publication icon
Ernst, PA (2018) MEXIT: Maximal un-coupling times for Markov processes in Stochastic Processes and their Applications

publication icon
Ernst P (2019) MEXIT: Maximal un-coupling times for stochastic processes in Stochastic Processes and their Applications

 
Description We have established that maximal probabilistic couplings for smooth elliptic diffusions can only be Markovian in very special cases (state-space has to be simply connected and of constant curvature, drift has to derive from rotational symmetries or -- in the Euclidean case -- dilations). This is a striking result that shows the importance of developing good understanding of non-maximal but otherwise efficient couplings.
We have also investigated probabilistic couplings for the Kolomogorov diffusion (the simplest nilpotent diffusion). We have shown that in this case the class of Markovian couplings cannot be efficient (in a specific technical sense), but we have exhibited an efficient non-Markovian coupling. This case study adds significantly to the knowledge base of what kinds of couplings can be derived in various circumstances. In particular it raises an important open question, namely how to characterize situations in which modest amounts of non-Markovian construction can lead to efficient couplings.
Developing the work on the Kolmogorov diffusion, we have now established how to couple finite sets of polynomial stochastic integrals for two-dimensional diffusions, using only reflection and synchronous couplings (Banerjee and Kendall, 2018). While we have not yet attained the full objective (to exhibit couplings for general nilpotent diffusions), we believe that the two-dimensional result sets the template for future work in which we plan together to attack and then exploit this full objective. (Banerjee working with Gordina and Mariano has already now used these techniques to establish useful gradient bounds for the Heisenberg group using non-Markovian methods.) With separate collaborators, the PI is now writing up similar results relating to continuous-time random walks and Lévy processes,
The question of coupling in infinite-dimensional situations has been studied in a collaboration between PI and Dr Candellero. This has links with the work on Kolmogorov diffusion coupling, and makes intriguing links with Banach-space geometry. This may turn out to have useful links with the collaboration of the PI with Zanella and Bedard listed below.
Other work includes:
Work of the PI with Connor on perfect simulation (an important coupling technique) for multi-server queues. Our work provides the first application of perfect simulation for a general M/G/c queue, and has already stimulated further investigations by other workers.
Very recent work by the PI and others has established a general context for maximal (not necessarily Markovian) couplings in a reverse-time context (hence described as "un-coupling", maximal exit, or MEXIT) and has shown a variety of applications to statistics and particularly Markov chain Monte Carlo.
Finally the work of the PI with Bedard and Zanella (who was partly funded by this grant) shows how to use stochastic analysis methods to address optimal scaling for Markov chain Monte Carlo. This is now a fully-fledged research programme in its own right, funded by EPSRC (EP/R022100/1).
Exploitation Route We expect this theoretical context for probabilistic coupling techniques to have a significant influence on the development of probabilistic methodology, therefore influencing the very wide range of applications of probability theory. For example, there is potential indirect relevance to work in electronics, where probabilistic techniques are often relevant, and to digital / communication / information technologies, where probabilistic methods impact on design and analysis of algorithms.
Sectors Digital/Communication/Information Technologies (including Software),Electronics

URL http://www2.warwick.ac.uk/fac/sci/statistics/staff/academic-research/kendall/personal/nilpotent
 
Description The research team have discovered a strikingly simple characterization of maximal Markovian coupling for regular elliptic diffusions in terms of an intrinsic Riemannian geometry of the underlying diffusion. A follow-on paper investigates similar issues in a case study of a particular hypoelliptic diffusion. Other outputs are: use of coupling methods in the investigation of a particularly symmetric construction of a random metric space, an initial detailed case-study of optimal coupling for Brownian motion and local time, and an application of the coupling technique to perfect simulation for multi-server queues, joint between the PI and Stephen Connor. These outputs are an initial substantiation of the hopes for structure waiting to be discovered in probabilistic coupling, and, in the case of the queueing paper, a complete solution to an open problem concerning the simulation of queues whose structure is too difficult to allow for analytical evaluation. The queueing application is expected to find application in electronics and communication; it is still much too early to see a developed application of this foundational work, however the results of the paper have been taken up and extended by various workers in operations research in the USA.
First Year Of Impact 2020
Sector Financial Services, and Management Consultancy
Impact Types Economic