Singular value distribution of dense random matrices with block Markovian dependence

Jaron Sanders; Alexander Van Werde

doi:10.1016/j.spa.2023.01.001

Singular value distribution of dense random matrices with block Markovian dependence

Jaron Sanders, Alexander Van Werde (Corresponding author)

Stochastic Operations Research

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

23 Downloads (Pure)

Abstract

A block Markov chain is a Markov chain whose state space can be partitioned into a finite number of clusters such that the transition probabilities only depend on the clusters. Block Markov chains thus serve as a model for Markov chains with communities. This paper establishes limiting laws for the singular value distributions of the empirical transition matrix and empirical frequency matrix associated to a sample path of the block Markov chain whenever the length of the sample path is Θ(n2) with n the size of the state space.

The proof approach is split into two parts. First, we introduce a class of symmetric random matrices with dependent entries called approximately uncorrelated random matrices with variance profile. We establish their limiting eigenvalue distributions by means of the moment method. Second, we develop a coupling argument to show that this general-purpose result applies to the singular value distributions associated with the block Markov chain.

Original language	English
Pages (from-to)	453-504
Number of pages	52
Journal	Stochastic Processes and their Applications
Volume	158
DOIs	https://doi.org/10.1016/j.spa.2023.01.001
Publication status	Published - 1 Apr 2023

Funding

This work is part of the project Clustering and Spectral Concentration in Markov Chains with project number OCENW.KLEIN.324 of the research programme Open Competition Domain Science – M which is partly financed by the Dutch Research Council (NWO) . We would like to thank Sem Borst, Martijn Gösgens, Gianluca Kosmella, Albert Senen–Cerda and Haodong Zhu for providing feedback on a draft of this manuscript.

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek

Keywords

Approximately uncorrelated
Block Markov chains
Poisson limit theorem
Random matrices
Variance profile

Access to Document

10.1016/j.spa.2023.01.001

pdfFinal published version, 2.45 MBLicence: CC BY

Cite this

@article{41e34b3ba77f49229d637e3ba5318c08,

title = "Singular value distribution of dense random matrices with block Markovian dependence",

abstract = "A block Markov chain is a Markov chain whose state space can be partitioned into a finite number of clusters such that the transition probabilities only depend on the clusters. Block Markov chains thus serve as a model for Markov chains with communities. This paper establishes limiting laws for the singular value distributions of the empirical transition matrix and empirical frequency matrix associated to a sample path of the block Markov chain whenever the length of the sample path is Θ(n2) with n the size of the state space.The proof approach is split into two parts. First, we introduce a class of symmetric random matrices with dependent entries called approximately uncorrelated random matrices with variance profile. We establish their limiting eigenvalue distributions by means of the moment method. Second, we develop a coupling argument to show that this general-purpose result applies to the singular value distributions associated with the block Markov chain.",

keywords = "Approximately uncorrelated, Block Markov chains, Poisson limit theorem, Random matrices, Variance profile",

author = "Jaron Sanders and {Van Werde}, Alexander",

year = "2023",

month = apr,

day = "1",

doi = "10.1016/j.spa.2023.01.001",

language = "English",

volume = "158",

pages = "453--504",

journal = "Stochastic Processes and their Applications",

issn = "0304-4149",

publisher = "Elsevier",

}

TY - JOUR

T1 - Singular value distribution of dense random matrices with block Markovian dependence

AU - Sanders, Jaron

AU - Van Werde, Alexander

PY - 2023/4/1

Y1 - 2023/4/1

N2 - A block Markov chain is a Markov chain whose state space can be partitioned into a finite number of clusters such that the transition probabilities only depend on the clusters. Block Markov chains thus serve as a model for Markov chains with communities. This paper establishes limiting laws for the singular value distributions of the empirical transition matrix and empirical frequency matrix associated to a sample path of the block Markov chain whenever the length of the sample path is Θ(n2) with n the size of the state space.The proof approach is split into two parts. First, we introduce a class of symmetric random matrices with dependent entries called approximately uncorrelated random matrices with variance profile. We establish their limiting eigenvalue distributions by means of the moment method. Second, we develop a coupling argument to show that this general-purpose result applies to the singular value distributions associated with the block Markov chain.

AB - A block Markov chain is a Markov chain whose state space can be partitioned into a finite number of clusters such that the transition probabilities only depend on the clusters. Block Markov chains thus serve as a model for Markov chains with communities. This paper establishes limiting laws for the singular value distributions of the empirical transition matrix and empirical frequency matrix associated to a sample path of the block Markov chain whenever the length of the sample path is Θ(n2) with n the size of the state space.The proof approach is split into two parts. First, we introduce a class of symmetric random matrices with dependent entries called approximately uncorrelated random matrices with variance profile. We establish their limiting eigenvalue distributions by means of the moment method. Second, we develop a coupling argument to show that this general-purpose result applies to the singular value distributions associated with the block Markov chain.

KW - Approximately uncorrelated

KW - Block Markov chains

KW - Poisson limit theorem

KW - Random matrices

KW - Variance profile

UR - http://www.scopus.com/inward/record.url?scp=85147247312&partnerID=8YFLogxK

U2 - 10.1016/j.spa.2023.01.001

DO - 10.1016/j.spa.2023.01.001

M3 - Article

SN - 0304-4149

VL - 158

SP - 453

EP - 504

JO - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

ER -

Singular value distribution of dense random matrices with block Markovian dependence

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this