Random MAX SAT, random MAX CUT, and their phase transitions
Don Coppersmith, David Gamarnik, et al.
SODA 1998
A classical result of Wolfowitz states that an inhomogeneous Markov chain is weakly ergodic if the transition matrices are drawn from a finite set of indecomposable and aperiodic matrices and the products of transition matrices are also indecomposable and aperiodic. Since products of indecomposable and aperiodic matrices can be decomposable, any finite set of indecomposable and aperiodic transition matrices does not guarantee weak ergodicity. We present conditions for weak ergodicity which are simpler to verify and are related to properties of the graph of the transition matrices. © 2008 Elsevier B.V. All rights reserved.
Don Coppersmith, David Gamarnik, et al.
SODA 1998
Hui Liu, Ming Cao, et al.
ISCAS 2013
Chai Wah Wu
American Mathematical Monthly
Vidya Muthukumar, Tejaswini Pedapati, et al.
CVPRW 2019