Spectral norm bounds for block Markov chain random matrices

Jaron Sanders and Senen–Cerda, Albert

Stochastic Processes and their Applications, 2023, vol. 158, issue C, 134-169

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 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(n2), then ‖Nˆ−E[Nˆ]‖=ΩP(Tn/n). We also prove that if Tn=Ω(nlnn), then ‖Nˆ−E[Nˆ]‖=OP(Tn/n) as n→∞; and if Tn=ω(n), a sparser regime, then ‖NˆΓ−E[Nˆ]‖=OP(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(Tn/n) for BMCs.

Keywords: Random matrices; Block Markov chains; Spectral norms; Asymptotic analysis; Sparse random graphs; Regularization (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414922002629
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:158:y:2023:i:c:p:134-169

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2022.12.004

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().