EPSRC logo

Details of Grant 

EPSRC Reference: EP/J009180/1
Title: Probabilistic coupling: co-adaptedness, maximality and efficiency
Principal Investigator: Connor, Dr SB
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Mathematics
Organisation: University of York
Scheme: First Grant - Revised 2009
Starts: 27 February 2012 Ends: 26 February 2014 Value (£): 54,667
EPSRC Research Topic Classifications:
Mathematical Analysis Statistics & Appl. Probability
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
05 Sep 2011 Mathematics Prioritisation Panel Meeting September 2011 Announced
Summary on Grant Application Form
My proposed research programme concerns the idea of coupling of Markov chains. Markov chains are random processes which satisfy the appealing quality that predictions about the future behaviour of the chain only depend upon its present state - knowing extra information about where the chain has been in the past does not help us to better predict the future. Markov chains have been intensely studied during the past hundred years, and are now used in a multitude of applications including weather forecasting, the analysis of card-shuffling techniques, and the PageRank method used by Google.

This investigation concerns the problem of constructing two copies of the same chain, started from different locations, so that once the two processes meet one another they stay together from that time onwards: this is known as a 'coupling' of the two chains. There is a range of possible coupling constructions available to us, and so a natural question to ask is how quickly it is possible to make the two chains meet. As well as being an interesting mathematical question, answers to this problem have significant implications for problems in theoretical computer science and statistical physics. The fastest couplings are known as 'maximal' couplings: we know that these couplings exist for a wide range of processes, but they are almost always difficult (if not impossible) to compute explicitly. This problem usually arises because the maximal coupling is often not co-adapted - loosely speaking, one chain has to use information about the future behaviour of the other in order to determine the next step of its trajectory. This makes co-adapted couplings (ones where no such 'cheating by looking into the future' is allowed) much more widely used in applications, but little is known about how good such couplings can be.

My proposed plan of research will investigate this problem, looking first of all at a particular class of Markov chains called random walks on groups. These random walks have a lot of nice structure, which can often be exploited to enable explicit computations to be performed. I will look at how good co-adapted couplings can be for these types of Markov chain, and how this is related to the underlying structure of the state-space. Another major objective of the project to is to look at maximal couplings in a more general setting, and try to understand when such couplings can be constructed in a co-adapted manner. The final aim of the proposal is to investigate the implications of the above results for 'perfect simulation' algorithms, many of which make use of co-adapted couplings to produce random samples from the exact stationary distribution of a Markov chain.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.york.ac.uk