Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - DYNAMICMARCH (Dynamics of Multiple, Interacting and Concurrent Markov Chains)

Teaser

Markov chains are fundamental processes and have been studied in nearly every scientic discipline in the past 100 years. In computer science, reversible Markov chains, also known as random walks, form the basis of many ecient randomised algorithms which have been successfully...

Summary

Markov chains are fundamental processes and have been studied in nearly every scientic discipline in the past 100 years. In computer science, reversible Markov chains, also known as random walks, form the basis of many ecient randomised algorithms which have been successfully applied to a variety of complex sampling, learning and optimisation problems. The goal of this proposal is to develop a systematic and rigorous study of multiple random walks. First, we will analyse this random process via commonly used metrics such as hitting times, cover times, mixing times as well as new quantities which are unique to multiple random walks. Then we will connect these quantities to structural properties of the underlying graph. Finally, these insights will be applied to the design of algorithms for problems such as clustering, information spreading and load balancing.

The proposed project addresses fundamental questions of Markov chains, whose solution will have a wide impact in computer science and mathematics. In the long term, we would also expect the results to impact other natural sciences, and create further synergies with seemingly disparate areas. For instance, stochastic Petri nets are a classical model in semantics, but only recently quantitative aspects such as hitting times and speed-ups have been studied. Quantum computing is another field where recently parallel algorithms based on multiple quantum walks have been investigated.

Work performed

*** WP1: Foundations of Independent and Homogeneous Multiple Random Walks ***

The goal of this work package is to investigate fundamental quantities such as hitting times, cover times and mixing time of multiple random walks. We are especially interested in the speed-up of multiple random walks over single random walks.

-In [IKPS17], which was accepted at STACS\'17, we derived several lower and upper bounds on the hitting times and cover times of random walks. A particular focus of this project was on basic networks such as paths as well two- or higher-dimensional grids/tori. We also established tight connections between discrete-time and continuous-time random walks, which might be very helpful to analyse other variants of random walks such as PageRank. As part of future work, we are planning to find a more general characterisation of the speed-up (applicable to a larger class of graphs) by capturing how well multiple random walks mix.

*** WP2: Foundations of Dependent and Inhomogeneous Random Walks ***

The goal of this work package is to study more complex (and somewhat more realistic) variants of multiple random walks. Examples include multiple random walks with interactions or correlations as well as multiple random walks on dynamically changing graphs.

-In [RSSS19], which is to appear in SPAA\'19, we investigated random processes on an $n$-vertex graph inspired by the internal diffusion limited aggregation (IDLA) model. In these processes, n particles start from an arbitrary but fixed origin. Each particle performs a simple random walk until first encountering an unoccupied vertex, and at which point the vertex becomes occupied and the random walk terminates. This process is quite natural and can be regarded as a simple distributed algorithm to spread a flow of incoming jobs (=particles) to servers (=vertices). We derived several tight lower and upper bound it takes for slowest particle to settle. We also established some interesting connections between a sequential and parallel (synchronous) variant of the process.

-In [KMS19], which was accepted at SODA\'19, we obtained several new results on coalescing random walks. Coalescing random walks is a fundamental stochastic process on connected and undirected graphs. The process begins with
particles on some subset of the nodes in the graph. At discrete time-steps, every particle performs one step of an independent random walk. Whenever two or more particles arrive at the same node at the same time-step,
they merge into a single particle and continue as a single random walk. The coalescence time is defined as the first time-step when only one particle remains. We derived several new results on the coalescence time in terms of easier quantities such as the hitting time, mixing time (which are quantities of single random walks) or the meeting time (which is a quantity involving two random walks). Due to the well-known duality between the voter model (a basic model for the spread of opinions in networks) and the coalescing random walk process, our results apply to the voter model, too.

-In [SZ19], which was accepted at ICALP\'19, we derived several new results for random walks on dynamic graphs. For example, we established that the well-known worst-case bounds of O(n^2) for mixing and hitting on regular graphs extend to random walks of dynamic graphs. Here, the dynamic graph sequence (G_1,G_2,...) can change arbitrarily as long as the vertex set is fixed and the edge set is so that the stationary distribution is the same in each iteration. A corresponding but slightly weaker holds for non-regular graphs. We also established two refined bounds, one involving the isoperimetric dimension of the graph and a second one involving the spectral gap of the average matrix. The former result can be even applied to graph sequences where every graph in the sequence itself may be disconnected. As a by-product, our methods also improve the state-of-the-art of random walk on static graphs.

Final results

Progress beyond the state of the art was made to a large extent through our 70-page article on coalescing random walks. The results improved the state of the art of what was known for coalescing random walks, but the techniques also helped us to derive several new results for single random walks (for example, we improved on a bound by Broder and Karlin on the hitting time/cover time of single random walks which hadn\'t been improved since 1988).

We have also made progress on the relatively recent topic of random walks on dynamic graphs. We proved that under some mild conditions, many worst case bounds for random walks for static graphs generalise to dynamically changing graphs, where the vertex set is fixed but the edge set is allowed to change (almost) arbitrarily.