Review for NeurIPS paper: A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices

Summary and Contributions: This paper establishes a concentration inequality in operator norm for the sample co-occurrence matrix C of a regular finite-state Markov chain. This is the matrix whose (i,j) entry counts the fraction of times states i and j co-occur within a time window of fixed size T, with a potential weighting by the difference of their occurrence times. The probability that C-E[C] exceeds eps is shown to be exponentially small in eps 2 * L, where L is the sample size (i.e. the total length of the chain). This concentration inequality is established as a corollary of a general result for the concentration of sample averages for a bounded symmetric-matrix-valued function applied to samples from an ergodic Markov chain. This general result is of independent interest.