论文标题
渐近学用于全图
Asymptotics for Push on the Complete Graph
论文作者
论文摘要
我们研究流行的随机谣言传播方案推动。最初，图中的节点具有一些信息，然后以圆形的方式扩展。在每个回合中，每个知情节点在其邻居之一中均匀地选择，并将信息传递给它。要调查的中心数量是运行时，即，在每个节点收到信息之前，所需的回合数。 广泛研究了推动方案及其变化。在这里，我们研究了基础图的案例，其中包括$ n $ nodes。即使在这个最基本的环境中，自引入协议以来，指定运行时的限制分布以及确定相关数量（例如其期望）仍然是空旷的问题。 在我们的主要结果中，我们描述了运行时的限制分布。我们表明它不会收敛，并且在适当的归一化之后，它变成了$ \ log_2n $以及$ \ ln n $ scale上的渐变周期性。特别是，只有当我们将自己限制为$ \ mathbb n $的适当子序列时，限制分布才会收敛，其中同时$ \ log_2 n- \ lfloor \ log_2n \ rfloor \ rfloor \ to x $和$ \ \ ln n- \ lfloor \ ln- \ ln n n n n \ ln n \ rfloor \ y $在这样的子序列中，我们表明预期的运行时为$ \ log_2 n+\ ln n+h（x，y）+o（1）$，其中明确给出了$ h $，并且数值$ | \ sup h- \ sup h- \ inf h- | \大约2 \ CDOT 10^{ - 4} $。
We study the popular randomized rumour spreading protocol Push. Initially, a node in a graph possesses some information, which is then spread in a round based manner. In each round, each informed node chooses uniformly at random one of its neighbours and passes the information to it. The central quantity to investigate is the Runtime, that is, the number of rounds needed until every node has received the information. The Push protocol and variations of it have been studied extensively. Here we study the case where the underlying graph is complete with $n$ nodes. Even in this most basic setting, specifying the limiting distribution of the runtime as well as determining related quantities, like its expectation, have remained open problems since the protocol was introduced. In our main result we describe the limiting distribution of the runtime. We show that it does not converge, and that it becomes, after the appropriate normalization, asymptotically periodic both on the $\log_2n$ as well as on the $\ln n$ scale. In particular, the limiting distribution converges only if we restrict ourselves to suitable subsequences of $\mathbb N$, where simultaneously $\log_2 n-\lfloor\log_2n\rfloor\to x$ and $\ln n-\lfloor\ln n\rfloor\to y$ for some fixed $x,y\in [0,1)$. On such subsequences we show that the expected runtime is $\log_2 n+\ln n+h(x,y)+o(1)$, where $h$ is explicitly given and numerically $|\sup h - \inf h| \approx 2\cdot 10^{-4}$.
