Spectral norm bounds for block Markov chain random matrices

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 X₀,X₁,…,X_Tn 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)=T_n=o(n²), then ‖Nˆ−E[Nˆ]‖=Ω_P(T_n/n). We also prove that if T_n=Ω(nlnn), then ‖Nˆ−E[Nˆ]‖=O_P(T_n/n) as n→∞; and if T_n=ω(n), a sparser regime, then ‖Nˆ_Γ−E[Nˆ]‖=O_P(T_n/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(T_n/n) for BMCs.