REPEATED AVERAGES ON GRAPHS

• 成果类型: Article
• 署名作者: Movassagh, Ramis; Szegedy, Mario; Wang, Guanyang
• 署名单位: Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/24-AAP2050
• 发表日期: 2024
• 页码: 3781-3819
• 关键词: quantum supremacy; random-walk; kacs walk; CONVERGENCE; consensus

摘要

Sourav Chatterjee, Persi Diaconis, Allan Sly, and Lingfu Zhang (Ann. Probab. 50 (2022) 1-17), prompted by a question of Ramis Movassagh, renewed the study of a process proposed in the early 1980s by Jean Bourgain. A state vector v is an element of R-n, labeled with the vertices of a connected graph, G, changes in discrete time steps following the simple rule that at each step a random edge (i, j) is picked and v(i) and v(j) are both replaced by their average (v(i) + v(j))/2. It is easy to see that the value associated with each vertex converges to Sigma(n)(i=1) v(i)/n. The question focused on understanding the time denoted as t(epsilon,1), which represents how quickly will v be epsilon-close to uniform in the L-1 norm in the case of the complete graph, K-n, when v is initialized as a standard basis vector that takes the value 1 on one coordinate, and zeros everywhere else. They have established a sharp cutoff of 1/2 log 2 n log n + O(n root log n). Our main result is to prove, that (1-epsilon)/2 log2 n log n - O(n) is a general lower bound for all connected graphs on n nodes. We also get sharp magnitude of t(epsilon,1) for several important families of graphs, including star, expander, dumbbell, and cycle. In order to establish our results we make several observations about the process, such as the worst case initialization is always a standard basis vector. Our results add to the body of work of (J. Theoret. Probab. 2 (1989) 91-100; Probab. Surv. 9 (2012) 90-102; Ann. Appl. Probab. 33 (2023) 936-971; Math. Methods Appl. Sci. 46 (2023) 3583-3596; SIAM J. Control Optim. 48 (2009) 33-55), and others. The renewed interest is partly due to an analogy to a question related to the Google's supremacy circuit. For the proof of our main theorem we employ a concept that we call augmented entropy function which may find independent interest in the probability theory and computer science communities.