We have submitted Spectral norm bounds for block Markov chain random matrices, and it is currently under review. This is joint work between Albert Senen-Cerda and myself. A preprint is available on arXiv.
This paper quantifies the asymptotic order of the largest singular value of a centered random matrix built from the path of a Block Markov Chain (BMC). In a BMC there are n labeled states, each state is associated to one of K clusters, and the probability of a jump depends only on the clusters of the origin and destination. Given a path X0, X1, …, XTn started from equilibrium, we construct a random matrix N that records the number of transitions between each pair of states. We prove that if ω(n)=Tn=o(n*n), then ∥N−E[N]∥=ΩP(sqrt(Tn/n)). We also prove that if Tn=Ω(nlnn), then ∥N−E[N]∥=OP(sqrt(Tn/n)) as n→∞; and if Tn=ω(n), a sparser regime, then ∥NΓ−E[N]∥=OP(sqrt(Tn/n)). Here, NΓ is a regularization that zeroes out entries corresponding to jumps to and from most-often visited states. Together this establishes that the order is ΘP(sqrt(Tn/n)) for BMCs.