论文标题
在图表上重复平均值
Repeated Averages on Graphs
论文作者
论文摘要
Sourav Chatterjee，Persi Diaconis，Allan Sly和Lingfu Zhang在Ramis Movassagh的问题上提示，重新研究了Jean Bourgain在1980年代初提出的一项过程。一个状态矢量$ v \ in \ mathbb r^n $，标有连接图的顶点，$ g $，遵循一个简单规则的离散时间步骤的变化，即在每个步骤中选择一个随机边缘$（i，j）$，而$ v_i $和$ v_i $和$ v_j $均由其平均$（v_i+v_i+v_j Jj）代替。很容易看出，与每个顶点相关的值收敛到$ 1/n $。问题是，在完整图的情况下，$ v $ be $ v $ be $ε$ - $ close在$ l^{1} $ norm中均一均匀，$ k_ {n} $，当$ k_ {n} $，当$ v $初始化为标准基础向量，该标准基础向量在一个坐标上以一个协调为单位，以及其他任何地方。他们已经建立了$ \ frac {1} {2 \ log 2} n \ log n + o（n \ sqrt {\ log n}）$的急剧截止。我们的主要结果是证明，$ \ frac {（1-ε）} {2 \ log2} n \ log n-o（n）$是$ n $ nodes上所有连接的图形的一般下限。对于几个重要的图形系列，我们还获得了$ t_ {ε，1} $的清晰幅度，包括星，expander，哑铃和循环。为了确定我们的结果，我们对该过程进行了一些观察，例如最坏的情况初始化始终是标准基础向量。我们的结果增加了Aldous，Aldous和Lanoue，Quattropani和Sau，Cao，Olshevsky和Tsitsiklis等的工作。新的兴趣是由于与与Google至高无上巡回赛有关的问题的类比。为了证明我们的主要定理，我们采用了一个我们称为“增强熵函数”的概念，该概念可能会发现对计算机科学和概率理论社区的独立兴趣。
Sourav Chatterjee, Persi Diaconis, Allan Sly and Lingfu Zhang, 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 \in \mathbb 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 $1/n$. The question was how quickly will $v$ be $ε$-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 $\frac{1}{2\log 2}n\log n + O(n\sqrt{\log n})$. Our main result is to prove, that $\frac{(1-ε)}{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_{ε,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 Aldous, Aldous and Lanoue, Quattropani and Sau, Cao, Olshevsky and Tsitsiklis, and others. The renewed interest is 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 computer science and probability theory communities.
