Analysis and Applications of Markov Chains

The project is motivated by the need for high efficiency Markov chain Monte Carlo methods in various scenarios. We are given a target distribution on a large discrete state space to sample from. Additionally, a graph provides the abstract description of allowable minor perturbations on the state space.
The goal is to choose the probability structure for the perturbations so that the resulting random walk approaches the target distribution quickly. Our primary interest is the finite time behavior captured by the mixing time, followed by the asymptotic rate of convergence.

The goals of the project can be partitioned into the following directions:
- Search for the optimal Markov chain without assuming a symmetry of transition probabilities (reversibility), unlocking extra degrees of freedom leading to increased efficiency.
- Stretch the baseline framework by introducing new edges in various ways, understand the achievable additional gain by these extensions.
- Translate results to applications, in particular for consensus on networked systems, taking into account possibly asynchronous communication.

In all these directions examples demonstrate the viability of the endeavor. In line with the nature of the problems, the objective of analytical understanding is complemented by the intention for the applicability of the results.