Spectral norm bounds for block Markov chain random matrices

Abstract

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_0,X_1,\dots ,X_{T_n}$ started from equilibrium, we construct a random matrix $\hat{N}$ that records the number of transitions between each pair of states. We prove that if $\omega (n)=T_n=o(n^2)$, then $\Vert \hat{N}-\mathbb{E}[\hat{N}]\Vert ={\Omega }_{\mathbb{P}}(\sqrt{T_n/n})$. We also prove that if $T_n=\Omega (n\ln n)$, then $\Vert \hat{N}-\mathbb{E}[\hat{N}]\Vert =O_{\mathbb{P}}(\sqrt{T_n/n})$ as $n\to \infty$; and if $T_n=\omega (n)$, a sparser regime, then $\Vert {\hat{N}}_{\Gamma }-\mathbb{E}[\hat{N}]\Vert =O_{\mathbb{P}}(\sqrt{T_n/n})$. Here, ${\hat{N}}_{\Gamma }$ is a regularization that zeroes out entries corresponding to jumps to and from most-often visited states. Together this establishes that the order is ${\Theta }_{\mathbb{P}}(\sqrt{T_n/n})$ for BMCs.

30 pages, 1 figure

Cited by in corpus (1)

• Singular value distribution of dense random matrices with block Markovian dependence