2017/04/12 by Ankit Garg, Yin Tat Lee, Garg, Ankit +5
Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1704.03864
openalex publication_date 2017/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.