2017/09/04 by Anna Ben-Hamou, Ben-Hamou, Anna, Roberto I. Oliveira +3
Computer Science · Mathematics · #05C85 #60J10 #62M05 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed systems and fault tolerance #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistics Theory (math.ST) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1709.00869
openalex publication_date 2017/09/04 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
An algorithm observes the trajectories of random walks over an unknown graph G, starting from the same vertex x, as well as the degrees along the trajectories. For all finite connected graphs, one can estimate the number of edges m up to a bounded factor in O(trel3/4√(m/d)) steps, where trel is the relaxation time of the lazy random walk on G and d is the minimum degree in G. Alternatively, m can be estimated in O(tunif +trel5/6√(n)), where n is the number of vertices and tunif is the uniform mixing time on G. The number of vertices n can then be estimated up to a bounded factor in an additional O(tunif(m)/(n)) steps. Our algorithms are based on counting the number of intersections of random walk paths X,Y, i.e. the number of pairs (t,s) such that Xt=Ys. This improves on previous estimates which only consider collisions (i.e., times t with Xt=Yt). We also show that the complexity of our algorithms is optimal, even when restricting to graphs with a prescribed relaxation time. Finally, we show that, given either m or the mixing time of G, we can compute the "other parameter" with a self-stopping algorithm.