| 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: |
|
|
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
|
|
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 |