We prove deviation bounds for the random variable @math in which @math is a Markov chain with stationary distribution and state space @math , and @math . Our bound improves upon previously known bounds in that the dependence is on @math rather than @math We also prove deviation bounds for certain types of sums of vector--valued random variables obtained from a Markov chain in a similar manner. One application includes bounding the expected value of the Schatten @math -norm of a random matrix whose entries are obtained from a Markov chain.
In work by Garg, Lee, Song and Srivastava @cite_13 , a version of Eq. was proved for Markov chains when the Banach space is the set of @math matrices under the Schatten @math -norm, generalizing a result first shown by Ahlswede and Winter @cite_17 (see also the monograph by Tropp @cite_9 ). Note that the Schatten @math -norm of a @math matrix is up to constant factors equal to the Schatten @math -norm of that matrix, and the modulus of uniform smoothness of the set of @math matrices under the Schatten @math -norm is @math . Thus in this case the left-hand side of Eq. is bounded above by @math . Garg, Lee, Song and Srivastava showed that for a Markov chain @math and functions @math such that @math ,
@cite_9 @cite_13 @cite_17
2964089577 2797316125 2134348739
Random matrices now play a role in many areas of theoretical, applied,and computational mathematics. Therefore, it is desirable to have toolsfor studying random matrices that are flexible, easy to use, and powerful.Over the last fifteen years, researchers have developed a remarkablefamily of results, called matrix concentration inequalities, that achieveall of these goals.This monograph offers an invitation to the field of matrix concentrationinequalities. It begins with some history of random matrix theory;it describes a flexible model for random matrices that is suitablefor many problems; and it discusses the most important matrix concentrationresults. To demonstrate the value of these techniques, thepresentation includes examples drawn from statistics, machine learning,optimization, combinatorics, algorithms, scientific computing, andbeyond. We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a random walk on an expander, confirming a conjecture due to [Wigderson and Xiao 06]. Our proof is based on a new multi-matrix extension of the Golden-Thompson inequality which improves upon the inequality in [Sutter, Berta and Tomamichel 17], as well as an adaptation of an argument for the scalar case due to [Healy 08]. Our new multi-matrix Golden-Thompson inequality could be of independent interest. Secondarily, we also provide a generic reduction showing that any concentration inequality for vector-valued martingales implies a concentration inequality for the corresponding expander walk, with a weakening of parameters proportional to the squared mixing time. We present a simple proof of the strong converse for identification via discrete memoryless quantum channels, based on a novel covering lemma. The new method is a generalization to quantum communication channels of Ahlswede's (1979, 1992) approach to classical channels. It involves a development of explicit large deviation estimates to the case of random variables taking values in self-adjoint operators on a Hilbert space. This theory is presented separately in an appendix, and we illustrate it by showing its application to quantum generalizations of classical hypergraph covering problems.