Browse Theses

This thesis is devoted to the study of stochastic processes on graphs, which is a system of random variables that evolve over time while undergoing probability fluctuations according to probabilistic rules. We study four discrete stochastic processes throughout this thesis. In the first process, we investigate the Best-of-3 voting dynamics for two colours (or opinions) in a class of non-complete graphs. As the main result, we show that if the graph has minimum degree nΩ(1/loglogn) , and each vertex is initially coloured red with probability 1/2+δ , blue otherwise, then the dynamics converges to a monochromatic red configuration within O(log log n) + O(log δ−1) steps with high probability. This, for sufficiently large δ , implies a doubly logarithmic convergence time in sufficiently dense graphs. The main purpose of this model is to close the gap between Best-of-3 and Best-of-5 in terms of consensus time, as it was known from precious work that both 2-majority and 3-majority take O(log n) time while 5-majority takes O(log log n) time. While there has been a rich line of research concerning majority consensus population protocols, we consider a diversity or task allocation population protocol, as many real-world systems evolve in an opposite way to reaching consensus: they converge to a state of diversity. In the second process - Diversification protocol, there are n agents each with one of k colours, and each colour i has an associated weight wi > 1 . The main goal is to achieve diversity such that the system has roughly nwi/w agents with colour i at any given time, where w is the sum of the weights of all k colours. This protocol converges to an approximately balanced state in O(w2n log n) steps, which is optimal up to the w term, according to the lower bounds of rumour spreading. In the third process, we study two switch Markov chains, called Triangle-switch processes, for sampling random regular graphs that favour triangles, in which local edge transformations are applied by choosing a pair of distinct edges xy and ab of the graph uniformly at random, and replacing with a uniformly chosen perfect matching of the vertices {x, y, a, b} to create or remove triangles in the graph. Note that the degree of any vertex is preserved in each switch move. With restricted attention to 2-regular graphs, we analyse the properties of the transition matrix of the chain and investigate the spectral properties and conductance in order to have a deeper insight on the mixing time of the associated random walk. As for the last process, we propose three models for generating random spanning trees, which can be considered as a type of random recursive forest and we call it the Permutation forest. A permutation forest is produced by first randomly ordering the vertices of the underlying graph G . For each vertex u we check all its neighbours higher than itself in the permutation ordering and choose the first, or the last, or a random neighbour according to three protocols: Pick-First, Pick-Last, and Pick-UAR, respectively. If no neighbour appears after u , then u becomes the root of a tree. We study the structure of the random forests generated under these tree protocols from an Erd˝os R´enyi random graph G(n, p), and provide analytical results for various properties, namely, the number of of components, maximum component size and maximum tree height. It is worth mentioning that the expected number of components in a permutation forest depends only on the degree sequence, and not on the structure of the underlying graph.