Phd Thesis Defense : Unimodularity in Random Networks: Applications to the Null Recurrent Doeblin Graph and Hierarchical Clustering

Speaker : Sayeh Khaniha
INRIA
Date: 26/09/2023
Time: 3:00 pm - 5:00 pm
Location: Inria, salle Philippe Flajolet

Abstract

This thesis is based on the notion of unimodularity in the context of random networks and explores two domains of application: Coupling from the Past in the null recurrent case based on the associated Doeblin Graphs and unsupervised classification based on hierarchical clustering on point processes. The first part of this thesis focuses on the properties of a specific random graph called the Doeblin Graph, which is associated with the Coupling from the Past algorithm used for perfect sampling of the stationary distribution of a Markov Chain. In the irreducible, aperiodic, and positive recurrent case, it is known that the Bridge Doeblin Graph, a subgraph of the Doeblin Graph, is an infinite tree that is unimodularizable and contains a unique biinfinite path. This bi-infinite path plays a crucial role in constructing a perfect sample of the stationary state of the Markov chain. This thesis extends the study to the null recurrent case, where it is shown that the Bridge Doeblin Graph is either an infinite tree or a forest composed of a countable collection of infinite trees. In the former case, the infinite tree possesses a single end, is not generally unimodularizable, but exhibits local unimodularity. These properties are leveraged to investigate the stationary regime of measure-valued random dynamics on the Bridge Doeblin Tree, particularly the taboo and potential random dynamics. The second part of this thesis introduces a novel hierarchical clustering model tailored for unsupervised classifications of datasets which are countably infinite. Clustering, a widely used technique in unsupervised learning, aims to identify groups within a dataset based on element similarities. The proposed algorithm employs multiple levels of clustering, constructing clusters at each level using nearest-neighbor chains of points or clusters. This algorithm is applied to the Poisson point process, and it is proven that the clustering algorithm defines a phylogenetic forest on the Poisson point process, which is a factor of the point process and is therefore unimodular. Various properties of this random forest, such as the mean sizes of clusters at each level or the mean size of the cluster of a typical node, are examined.