References & Citations
Mathematics > Probability
Title: Concentration Inequalities for Sums of Markov Dependent Random Matrices
(Submitted on 3 Mar 2023 (v1), last revised 16 Oct 2023 (this version, v3))
Abstract: We give Hoeffding and Bernstein-type concentration inequalities for the largest eigenvalue of sums of random matrices arising from a Markov chain. We consider time-dependent matrix-valued functions on a general state space, generalizing previous that had only considered Hoeffding-type inequalities, and only for time-independent functions on a finite state space. In particular, we study a kind of noncommutative moment generating function, give tight bounds on it, and use a method of Garg et al. to turn this into tail bounds. Our proof proceeds spectrally, bounding the norm of a certain perturbed operator. In the process we make an interesting connection to dynamical systems and Banach space theory to prove a crucial result on the limiting behavior of our moment generating function that may be of independent interest.
Submission history
From: Robert Shi [view email][v1] Fri, 3 Mar 2023 18:57:56 GMT (65kb)
[v2] Mon, 6 Mar 2023 04:56:53 GMT (63kb)
[v3] Mon, 16 Oct 2023 19:07:27 GMT (63kb)
Link back to: arXiv, form interface, contact.