Limiting behaviour of combinatorial Markov chains
Lead Research Organisation:
University of Oxford
Department Name: Statistics
Abstract
Project description: Rémy (1985) introduced a random tree-growth process for uniform binary
leaf-labelled trees with n leaves at step n. Aldous (2000) and Schweinsberg (2002) studied a treevalued
up-down Markov chain with uniform stationary distribution, by combining, for each step,
the uniform removal of a leaf (down-step) by Rémy's growth step (up-step). Ford (2006), Dong,
Goldschmidt and Martin (2006), Marchal (2008), Chen et al. (2009) and Pitman and Winkel (2009)
generalised Rémy's tree-growth process to larger classes of tree-growth processes with some
recursive structure. These references include studies of the asymptotics in n, establishing limiting
continuum random trees in the sense of Aldous (1991). Key ingredients are more elementary
combinatorial structures such as partition- and composition-valued Chinese Restaurant Processes
(see e.g. Pitman (2006) and Pitman and Winkel (2009)). Forman et al. (2016) and Rogers and
Winkel (work in progress) are studying limiting evolutions of composition-valued down-up Markov
chains. This is part of a wider collaborative project to understand the limiting evolution of Aldous's
tree-valued down-up chain, ultimately aiming to establish the existence of a diffusive scaling limit
as conjectured by David Aldous.
The purpose of this project is to explore generalisations of Aldous's tree-valued down-up Markov
chain to the context of the one- and two-parameter classes of tree-growth processes referred to
above. Avenues to explore include basic structural properties of the Markov chain including
stationary distributions and asymptotic properties such as mixing times and relaxation times as
studied by Aldous and Schweinsberg in their special case. Further directions include asymptotic
studies alongside the wider collaborative project mentioned above or wider/related classes of
Markov chains models on combinatorial structures such as partitions, compositions, trees and more
general connected graphs such as sparse connected graphs with surplus edges etc.
This project is situated at the Probability side of the general research theme of
"Statistics and Applied Probability", with some interaction with the Combinatorics side of "Logic
and Combinatorics" and with "Mathematical Analysis".
References:
- Aldous (1991) The Continuum Random Tree I. Ann. Probab., 19(1):1-28
- Aldous (2000) Mixing time for a Markov chain on Cladograms. Combin. Probab. Comput.,
9(3):191-204
- Chen, Ford and Winkel (2009) A new family of Markov branching trees: the alpha-gamma
model. Elec. J. Prob. 14, 400-430
- Dong, Goldschmidt and Martin (2006) Coagulation-fragmentation duality, Poisson-
Dirichlet distributions and random recursive trees. Ann. Appl. Probab. 16(4): 1733-1750
- Ford (2006) Probabilities on cladograms: introduction to the alpha model. Ph.D. thesis,
Stanford University, 241p.
- Forman, Pal, Rizzolo and Winkel (2016) Diffusions on a space of interval partitions with
Poisson-Dirichlet stationary distributions. ArXiv:1609.06706
- Forman, Pal, Rizzolo and Winkel (work in progress) Aldous diffusion.
- Marchal (2008) A note on the fragmentation of a stable tree. In Fifth Colloquium on Math.
and Comp. Sci., Discr. Math. Theor. Comput. Sci. Proc., AI, pages 489-499
- Pitman (2006) Combinatorial Stochastic Processes, volume 1875 of LNM. Springer Berlin
- Pitman and Winkel (2009) Regenerative tree growth: binary self-similar continuum random
trees and Poisson-Dirichlet compositions. Ann. Probab. 37(5), 1999-2041
- Rémy (1985) Un procédé itératif de dénombrement d'arbres binaires et son application à
leur génération aléatoire. RAIRO Inform. Théor., 19(2):179-195
- Rogers and Winkel (work in progress) Chinese Restaurants from a Lévy process
- Schweinsberg (2002) An O(n2) bound for the relaxation time of a Markov chain on
cladograms. Random Structures Algorithms, 20(1):59-70
leaf-labelled trees with n leaves at step n. Aldous (2000) and Schweinsberg (2002) studied a treevalued
up-down Markov chain with uniform stationary distribution, by combining, for each step,
the uniform removal of a leaf (down-step) by Rémy's growth step (up-step). Ford (2006), Dong,
Goldschmidt and Martin (2006), Marchal (2008), Chen et al. (2009) and Pitman and Winkel (2009)
generalised Rémy's tree-growth process to larger classes of tree-growth processes with some
recursive structure. These references include studies of the asymptotics in n, establishing limiting
continuum random trees in the sense of Aldous (1991). Key ingredients are more elementary
combinatorial structures such as partition- and composition-valued Chinese Restaurant Processes
(see e.g. Pitman (2006) and Pitman and Winkel (2009)). Forman et al. (2016) and Rogers and
Winkel (work in progress) are studying limiting evolutions of composition-valued down-up Markov
chains. This is part of a wider collaborative project to understand the limiting evolution of Aldous's
tree-valued down-up chain, ultimately aiming to establish the existence of a diffusive scaling limit
as conjectured by David Aldous.
The purpose of this project is to explore generalisations of Aldous's tree-valued down-up Markov
chain to the context of the one- and two-parameter classes of tree-growth processes referred to
above. Avenues to explore include basic structural properties of the Markov chain including
stationary distributions and asymptotic properties such as mixing times and relaxation times as
studied by Aldous and Schweinsberg in their special case. Further directions include asymptotic
studies alongside the wider collaborative project mentioned above or wider/related classes of
Markov chains models on combinatorial structures such as partitions, compositions, trees and more
general connected graphs such as sparse connected graphs with surplus edges etc.
This project is situated at the Probability side of the general research theme of
"Statistics and Applied Probability", with some interaction with the Combinatorics side of "Logic
and Combinatorics" and with "Mathematical Analysis".
References:
- Aldous (1991) The Continuum Random Tree I. Ann. Probab., 19(1):1-28
- Aldous (2000) Mixing time for a Markov chain on Cladograms. Combin. Probab. Comput.,
9(3):191-204
- Chen, Ford and Winkel (2009) A new family of Markov branching trees: the alpha-gamma
model. Elec. J. Prob. 14, 400-430
- Dong, Goldschmidt and Martin (2006) Coagulation-fragmentation duality, Poisson-
Dirichlet distributions and random recursive trees. Ann. Appl. Probab. 16(4): 1733-1750
- Ford (2006) Probabilities on cladograms: introduction to the alpha model. Ph.D. thesis,
Stanford University, 241p.
- Forman, Pal, Rizzolo and Winkel (2016) Diffusions on a space of interval partitions with
Poisson-Dirichlet stationary distributions. ArXiv:1609.06706
- Forman, Pal, Rizzolo and Winkel (work in progress) Aldous diffusion.
- Marchal (2008) A note on the fragmentation of a stable tree. In Fifth Colloquium on Math.
and Comp. Sci., Discr. Math. Theor. Comput. Sci. Proc., AI, pages 489-499
- Pitman (2006) Combinatorial Stochastic Processes, volume 1875 of LNM. Springer Berlin
- Pitman and Winkel (2009) Regenerative tree growth: binary self-similar continuum random
trees and Poisson-Dirichlet compositions. Ann. Probab. 37(5), 1999-2041
- Rémy (1985) Un procédé itératif de dénombrement d'arbres binaires et son application à
leur génération aléatoire. RAIRO Inform. Théor., 19(2):179-195
- Rogers and Winkel (work in progress) Chinese Restaurants from a Lévy process
- Schweinsberg (2002) An O(n2) bound for the relaxation time of a Markov chain on
cladograms. Random Structures Algorithms, 20(1):59-70
Organisations
People |
ORCID iD |
| Matthias Winkel (Primary Supervisor) | |
| Frederik Soerensen (Student) |
Publications
Sørensen F
(2023)
A down-up chain with persistent labels on multifurcating trees
in Random Structures & Algorithms
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509711/1 | 01/10/2016 | 30/09/2021 | |||
| 1930434 | Studentship | EP/N509711/1 | 01/10/2017 | 30/09/2020 | Frederik Soerensen |
| Description | The project has been focused on developing mathematical processes inspired by tree-type structures found in e.g. phylogenetics. Results previously only known in the context of binary trees have been extended to multifurcating trees. This in particular includes the limiting behavior of these processes. In the process, intimate links to other combinatorial processes have been discovered and described. Lastly, a new and richer class of 'semi-planar trees' have been constructed, mitigating some of the difficulty in proving many of the mathematical results that have been uncovered. Research is ongoing. |
| Exploitation Route | This can in large part be viewed as a small project that feeds into the larger project of settling a mathematical conjecture posed by David Aldous in 1992. Much effort is currently being put into settling this conjecture in a special case, and the research described above can in large part be seen as the first step in the direction of settling a generalized version of the conjecture. Thus it could be important for mathematical / probabilistic research related to this area. |
| Sectors | Other |
| Description | Academic Seminars at St Edmund Hall |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Postgraduate students |
| Results and Impact | In November 2018 and November 2019 I gave two 15 minute talks, followed by 10 minute Q&A sessions, at the Graduate Seminar for the postgraduate community at St Edmund Hall, Oxford. The audience at these events are 20 postgraduate student from a wide range of subjects both within and outside of the life sciences. The seminar consists of three talks all given by postgraduate research students at St Edmund Hall. The other talks at the seminars were from postgraduate students in immunology, engineering, and public policy making, respectively. The purpose of the seminars is to exchange ideas across different research subjects whilst also contributing to the sharing of knowledge outside of ones field of expertise. Several of the postgraduate students in immunology and biology expressed interest in the type of models that is a part of this research project and engaged in a fruitful discussion about possible applications of the class of parametric models. |
| Year(s) Of Engagement Activity | 2018,2019 |
| URL | http://mcr.seh.ox.ac.uk/graduate-life/academic-support-at-the-college/ |
| Description | St Edmund Hall Maths Talk |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Undergraduate students |
| Results and Impact | In February 2020 I gave a talk to all students and faculty doing mathematical subjects (Mathematics / Statistics / Physics / Engineering etc.) at St Edmund Hall, University of Oxford. The talk was well attended with about 20 people from various different mathematical backgrounds, and at different levels within the University. The talk revolved around my most recent research, and sparked interesting discussions as the audience had various inputs from their respective areas of mathematics. |
| Year(s) Of Engagement Activity | 2020 |