EPSRC Reference: 
EP/J009180/1 
Title: 
Probabilistic coupling: coadaptedness, maximality and efficiency 
Principal Investigator: 
Connor, Dr SB 
Other Investigators: 

Researcher CoInvestigators: 

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: 

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 cardshuffling 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 coadapted  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 coadapted 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 coadapted couplings can be for these types of Markov chain, and how this is related to the underlying structure of the statespace. 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 coadapted 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 coadapted 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 nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

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 