Robust metropolis-hastings algorithm for safe reversible Markov chain synthesis

This paper presents a new method to synthesize safe reversible Markov chains via classical Metropolis-Hastings (M-H) algorithm. Classical M-H algorithm does not impose safety constraints on the probability vector for the resulting Markov chain. This paper provides a convex synthesis method that incorporates the safety constraints via proper choice of the proposal matrix for the M-H algorithm. The resulting proposal matrix is a stochastic matrix that ensures safety for a nominal stationary distribution. Then it is shown that the M-H algorithm with this proposal matrix, robust M-H algorithm, also ensures safety for a well-characterized convex set of stationary distributions, which also includes the nominal stationary distribution. We also present a convex synthesis method for the proposal matrix to maximize the size of this resulting set of feasible stationary distributions for the robust M-H algorithm. Simulation results are also provided to demonstrate that there is no tradeoff between the speed of convergence and the robustness.