Asymptotics for Pull on the Complete Graph

DOI10.1016/J.SPA.2023.01.017MaRDI QIDQ6380614arXivFDO

Authors Konstantinos Panagiotou, Simon Reisser

Publication date 18 October 2021

Full work available at URL https://doi.org/10.1016/J.SPA.2023.01.017

Applications of graph theory (05C90) Numerical solutions to stochastic differential and integral equations (65C30) Randomized algorithms (68W20)

arXiv classification

math.PR

Abstract: We study the randomized rumor spreading algorithm emph{pull} on complete graphs with

n

vertices. Starting with one informed vertex and proceeding in rounds, each vertex yet uninformed connects to a neighbor chosen uniformly at random and receives the information, if the vertex it connected to is informed. The goal is to study the number of rounds needed to spread the information to everybody, also known as the emph{runtime}. In our main result we provide a description, as

n

gets large, for the distribution of the runtime that involves a martingale limit. %We provide a description of the distribution of the runtime in terms of a limit of a sequence of martingales. This allows us to establish that in general there is no limiting distribution and that convergence occurs only on suitably chosen subsequences

(n_{i})_{i i n m a t h b b N}

of

m a t h b b N

, namely when the fractional part of

(l o g_{2} n_{i} + l o g_{2} l n n_{i})_{i i n m a t h b b N}

converges.

This page was built for publication: Asymptotics for Pull on the Complete Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6380614)