Fastest random walk on a path |
| |
Authors: | Onur Cihan Mehmet Akar |
| |
Affiliation: | 1. Department of Electrical and Electronics Engineering, Marmara University, Istanbul, Turkey;2. Department of Electrical and Electronics Engineering, Bogazici University, Istanbul, Turkey |
| |
Abstract: | In this paper, we consider two convex optimisation problems in order to maximise the mixing rate of a Markov chain on an undirected path. In the first formulation, the holding probabilities of vertices are identical and the transition probabilities from a vertex to its neighbours are equal, whereas the second formulation is the more general reversible Markov chain with the same degree proportional stationary distribution. We derive analytical results on the solutions of the optimisation problems and compare the spectra of the associated transition probability matrices. |
| |
Keywords: | Markov chains fastest mixing second largest eigenvalue modulus graph theory |
|
|