Title: A Matrix Expander Chernoff Bound,
Abstract: 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. Our proof is based on a new multi-matrix extension of the
Golden-Thompson inequality which improves in some ways the inequality of
Sutter, Berta, and Tomamichel, and may be of independent interest, as well as
an adaptation of an argument for the scalar case due to Healy. 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.