Clustering in block Markov chains

DOI10.1214/19-AOS1939zbMath1461.62108arXiv1712.09232OpenAlexW3006667237MaRDI QIDQ1996780

Jaron Sanders, Se-Young Yun, Alexandre Proutiere

Publication date: 26 February 2021

Published in: The Annals of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1712.09232

zbMATH Keywords

Markov chainsclusteringasymptotic analysisinformation theorychange of measurecommunity detectionmixing times

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Statistical aspects of information-theoretic topics (62B10)

Related Items (3)

A low-rank spectral method for learning Markov models ⋮ Spectral norm bounds for block Markov chain random matrices ⋮ Singular value distribution of dense random matrices with block Markovian dependence

Cites Work

• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Consistency thresholds for the planted bisection model
• Semicircle law for a matrix ensemble with dependent entries
• Adaptive aggregation for reinforcement learning in average reward Markov decision processes
• Reconstruction and estimation in the planted partition model
• Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
• On the distribution of the roots of certain symmetric matrices
• Asymptotically efficient adaptive allocation rules
• Semicircle law for generalized Curie-Weiss matrix ensembles at subcritical temperature
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Spectrum of large random reversible Markov chains: two examples
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Exact Recovery in the Stochastic Block Model
• Markov Chains
• Sixty years of moments for random matrices
• Least squares quantization in PCM
• Community detection thresholds and the weak Ramanujan property
• Spectral techniques applied to sparse random graphs
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• An Introduction to Matrix Concentration Inequalities

This page was built for publication: Clustering in block Markov chains