The Matrix Chernoff Bound asserts that a sum of independent bounded random matrices concentrates around its mean. We prove a conjecture of Wigderson and Xiao, asserting that the same conclusion is true when the matrices are not independent, but sampled according to a random walk on a Markov chain with a spectral gap (i.e., an expander graph). This implies a black-box derandomization of many applications of the matrix Chernoff bound. A key ingredient in the proof is a multi-matrix extension of the Golden-Thompson inequality, based on the work of Sutter et al., which relates the trace of the matrix exponential of a sum of many matrices to a the trace of the product of their exponentials.

Joint work with Ankit Garg, Yin Tat Lee, and Zhao Song.