NeurIPS 2020 | 清华大学、腾讯量子实验室等马尔科夫链上的矩阵Chernoff Bound和它在共现矩阵中应用
在 NeurIPS 2020 上,清华大学,微软雷德蒙德研究院,腾讯量子实验室和佐治亚理工的团队证明了一个马尔科夫链上的矩阵 Chernoff Bound,并介绍了它在共现矩阵收敛速度分析中应用。这项研究为分析马尔科夫链上的随机矩阵均值的特征值提供了有力的工具,被收录为 NeurIPS2020 的 poster。Chernoff Bound 是一个重要的概率论工具,它刻画了样本均值的尾数概率随着样本数量增加而指数衰减的现象,在计算机科学的各个领域都有应用。Garg 等人在 STOC 18 的工作将 Chernoff Bound 扩展到了马尔科夫相关的矩阵随机变量上。受到这个工作的启发,我们开始研究马尔科夫链上随机矩阵的 Chernoff Bound。我们证明了,给定一个有限状态马尔科夫链和一个把马尔科夫链的状态映射到埃尔米特(Hermitian)矩阵的函数。当我们在这个马尔科夫链上进行采样,并且计算采样得到的矩阵的均值时。矩阵均值的最大最小特征值的尾数概率依然随着样本数量增加而指数衰减。